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:

enter image description here


2 Answers 2


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)$.

enter image description here

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)$.

enter image description here

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

enter image description here

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).

  • $\begingroup$ 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. $\endgroup$ Commented Feb 27, 2015 at 1:48
  • $\begingroup$ You are right, it should have been $\lfloor t \,\text{mod}\, b\rfloor$, I fixed that, thanks. $\endgroup$ Commented Feb 28, 2015 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.