# What is the Hausdorff dimension of this fractal?

Let $\sum_{i=h}^\infty d_i/b^i$ be the base $b$ representation of $x \geq 0,$ where $b>1$ and the $d_i$ are uniquely determined by the greedy algorithm. For fixed $c>1,$ let $f(x)= \sum_{i=h}^\infty d_i/c^i .$ Since $cf(x)=f(bx),$ the graph of $f$ is self-similar; e.g., its shape is the same on $[0,b^k]$ for all integers $k$. What is its Hausdorff dimension?

The graph shares some characteristics with some fractals in Wikipedia's List of fractals by Hausdorff dimension. For $(b,c)=(3,2)$, it looks like so:

Strictly speaking, the graph is not self-similar. It is (nearly) self-affine. More precisely, if $b>1$ is an integer and $c>1$ is real, then the graph $G$ of $f$ over the interval $[0,b]$ agrees with the invariant set $K$ of an iterated function system containing $b$ affine functions up to a countable set. Specifically, $$K=\bigcup_{i=1}^b T_i(K),$$ where $$T_i(\pmb{x}) = \left( \begin{array}{cc} 1/b & 0 \\ 0 & 1/c \end{array}\right) + \left( \begin{array}{c} i-1 \\ i-1 \end{array}\right),$$ for $i=1,\ldots,b$. Furthermore, the graph $G=K \setminus C$, where $C$ is countable; thus, conclusions about the dimension of $K$ can be extended to the dimension of $G$ for any $\sigma$-stable notion of dimension, such as Hausdorff dimension or modified box-counting dimension.

Here's an illustration for $(b,c)=(3,2)$.

The three smaller rectangles indicate the action of the IFS on the larger rectangle. The invariant set $K$ of that IFS is, by definition, compact. The graph $G$ of the function $f$ is not closed, however, as $f$ is not continuous; I think it's a mistake to connect the dots as in your linked image. The points of discontinuity are exactly those that have multiple base $b$ representations. The set $K$ contains points with both possible $y$ values but, again those countably many points won't affect the dimension.

Falconer has a formula to compute an estimate to the dimension of a self-affine set that often yields the exact result. It's quite a bit more complicated than the corresponding result for strictly self-similar sets and there are special cases where it gives only an upper bound. For a set in the plane whose dimension is known to be at least 1, we use the so-called singular value function:

$$\varphi ^s(f) = \alpha \beta ^{s-1},$$

where $\alpha \geq \beta$ are the singular values of the linear part of $f$.

Let $J_k$ denote the set of all sequences of integers chosen from $\{1,\ldots ,m\}$. Thus if $\left(i_1,\ldots ,i_k\right)$ is such a sequence then $f_{i_1}\circ \text{$\cdots $f}_{i_k}(E)$ is a small copy of $E$ and the set of all such sets covers $E$ with small sets. Falconer proved that there is a unique number $s$ so that

$$\lim_{k\to \infty } \left(\underset{\left(i_1,\ldots ,i_k\right)\in J_k}{\sum }\phi ^s\left(f_{i_1}\circ \cdots \circ f_{i_k}\right)\right){}^{1/k}=1$$

and, furthermore, that this number $s$ is an upper bound for the box dimension of the set $E$. In the case we have here, the expression inside the limit on the left simplifies considerably, since all the functions have the same, diagonalizable linear part. In fact, it's just $$\left(b^k/\left(c^kb^{k(s-1)}\right)^{1/k}=b\left/\left(c b^{s-1}\right)\right.\right..$$ Setting this equal to one and solving for $s$ we get $s=2-\log(c)/\log(b)$, in agreement with Martin's answer.

Recall that the singular values satisfied $\alpha \geq \beta$. That is, they are ordered. Thus, an implicit assumption here was that $b\geq c$. Otherwise, the formula returns a result smaller than 1, which is clearly incorrect. In the case where $b<c$, the function $f$ is strictly increasing so it has bounded variation. The dimension of the graph must be exactly 1. Here's an illustration for $(b,c)=(2,3)$.

Finally, I think the situation might be more difficult when $b$ is not an integer. Here's an illustration for $(b,c)=(\pi,2)$.

The three boxed parts are indeed affine images of the whole but there's a small part left over. I believe that the remaining small part together with the whole form a digraph fractal pair. I haven't bothered proving this, though, since a major problem is likely to arise due to the introduction of a new affine transformation with radically different linear part from the others.

Given the result in "The Lyapunov dimension of a nowhere differentiable attracting torus" by Kaplan, Mallet-Paret and Yorke, the natural conjecture for the Hausdorff dimension of the graph of $f$ would be $2 - \log(c)/\log(b)$ (take $q(t) = \lfloor t\,\text{mod}\, b\rfloor$ in their introduction).

• Your $q(t)$ returns real numbers in $[0,1)$, but we want digits. I think your idea is right but that $q(t)=\sum_{k=0}^{\infty} \left\lfloor(\left(b^k x\right) \bmod \lfloor b\rfloor)\right\rfloor/c^k$ is the correct function to use. I don't think that either function meets the hypotheses outlined in the paper, but it does seem to work. – Mark McClure Feb 27 '15 at 1:48
• You are right, it should have been $\lfloor t \,\text{mod}\, b\rfloor$, I fixed that, thanks. – Martin Hairer Feb 28 '15 at 10:27