MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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)$. – Andreas Blass Feb 15 '12 at 23:31
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.$$ – Anton Petrunin Feb 15 '12 at 23:35
Edit: $x_n=1 \Rightarrow x_{n+1}=0$. – MichaelNgelo Feb 15 '12 at 23:59
See related math.SE question:… – Joel David Hamkins Feb 16 '12 at 1:43
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? – MichaelNgelo Feb 16 '12 at 4:19
up vote 6 down vote accepted

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

share|cite|improve this answer
Thanks for putting things into a broader perspective~ – MichaelNgelo Feb 16 '12 at 4:21
Would you mind clarifying whether the set $F$ is self-similar or not? – MichaelNgelo Feb 25 '12 at 4:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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