What is the Hausdorff dimension of the subset $$F := \{ x = \sum^\infty_{n=1} \frac{2 x_n}{3^n} \in [0,1] : x_n \in \{ 0 , 1 \} , x_n = 1 \Rightarrow x_{n+1}=0 \}$$ of the Cantor set? Is it known already?

As far as I know, this set can be corresponded to a binary tree related to the Fibonacci sequence. (I don't know how to call that tree.)

  • 2
    $\begingroup$ Presumably, the subscript $n$ on the last $x$ should be $n+1$. Then, at stage $n$ of the usual middle-thirds construction of the Cantor set, when you have $2^n$ intervals of length $1/3^n$ each, the number of those intervals that meet $F$ is the $n$-th Fibonacci number (if you index the Fibonacci numbers appropriately), which is asymptotically a constant time $\phi^n$, where $\phi$ is the golden ratio $(1+\sqrt 5)/2$. So I'd expect the Hausdorff dimension of $F$ to be $(\ln\phi)/(\ln 3)$. $\endgroup$ Commented Feb 15, 2012 at 23:31
  • 4
    $\begingroup$ If so, then you can brake your set in two parts, those which start with $1,0$ and the rest. These parts are rescalings of the original set with coefficients $\tfrac19$ and $\tfrac13$ therefore dimension is the number $\alpha$ such that $$\tfrac 1{3^\alpha}+\tfrac1{9^\alpha}=1.$$ $\endgroup$ Commented Feb 15, 2012 at 23:35
  • $\begingroup$ Edit: $x_n=1 \Rightarrow x_{n+1}=0$. $\endgroup$ Commented Feb 15, 2012 at 23:59
  • $\begingroup$ See related math.SE question: math.stackexchange.com/questions/73547/… $\endgroup$ Commented Feb 16, 2012 at 1:43
  • $\begingroup$ Thanks for your replies~ @Anton, I'm still uncertain about one point. At step n+1, the part starting with 1 doesn't seem to be exactly a self-similar part of the set at step n. And why is the ratio $\frac{1}{9}$ for this part? $\endgroup$ Commented Feb 16, 2012 at 4:19

1 Answer 1


The comments by Andreas and Anton give you the answer already to your specific question. Let me give a more general answer, since your question is very representative of a whole class of examples.

The condition that $x_n = 1 \Rightarrow x_{n+1} = 0$ is a Markov condition: the value of $x_{n+1}$ is restricted by the value of $x_n$. In your case you are considering all sequences in $\{0,1\}^\mathbb{N}$ such that the symbol $1$ cannot follow itself; one could also consider more symbols and more complicated restrictions, such as "every occurrence of $2$ can only be followed by $0$ or $2$, but not $1$". See http://en.wikipedia.org/wiki/Subshift_of_finite_type for more details.

Subshifts of finite type (abbreviated SFTs) are also called topological Markov chains, and can be presented in terms of a transition matrix, as described in that Wikipedia article. The logarithm of the largest eigenvalue of the transition matrix is an important quantity called the topological entropy of the SFT.

When you construct a subset of the Cantor set as in your question, the topological entropy turns out to be directly related to the Hausdorff dimension: namely Hausdorff dimension is topological entropy divided by $\log \lambda$, where $\lambda$ is the contraction ratio at each step of the construction of the Cantor set.

We wrote a more detailed description of this in Pesin & Climenhaga, "Lectures on fractal geometry and dynamical systems", or you can find many parts of it in most standard textbooks on dynamical systems.

  • $\begingroup$ Would you mind clarifying whether the set $F$ is self-similar or not? $\endgroup$ Commented Feb 25, 2012 at 4:53

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.