Let $\mathcal T$ be the famous twindragon, i.e., $$ \mathcal T=\left\{\sum_{n=0}^\infty a_n\left(\frac{1+i}2\right)^n : a_n\in\{0,1\}\right\}. $$

enter image description here

Then, as is well known, $\mathcal T$ has a non-empty interior, whereas $\partial\mathcal T$ is indeed a fractal whose Hausdorff dimension is known as well - see, e.g., this survey (it's on the Heighway dragon, but the twindragon is just two of those placed back to back).

Now let $X\subset\{0,1\}^{\mathbb N}$ be defined as follows: $$ \partial \mathcal T=\left\{\sum_{n=0}^\infty b_n\left(\frac{1+i}2\right)^n : b_n\in X\right\}. $$ Clearly, $X$ is a subshift.

QUESTION. Is there a closed description of $X$? In particular, is $X$ a sofic subshift (or even a subshift of finite type)?

The closed formula for its dimension - $\log\lambda/\log\sqrt2$ with $\lambda$ being a root of $2x^3-x+1$ - suggests so. The proof from the link uses the Hutchinson formula for some self-similar IFS whose attractor is precisely $\partial\mathcal T$, which is nice, but I'd like it to be in the form $h(X)/\log\sqrt2$, where $h(X)$ is the topological entropy of the subshift $X$.


2 Answers 2


The link that you refer to does not describe the boundary as the attractor of a simple IFS, rather it describes a collection of portions of the boundary as the invariant list of a digraph IFS - or directed graph iterated function system. I am not an expert on sofic systems, but I believe that an analysis of that digraph IFS yields the type of description that you want.

Also, I can't agree with your dimension computation as your polynomial factors $$2 x^3-x+1=(x+1) \left(2 x^2-2 x+1\right)$$ revealing only one real root, which is negative. The analysis below computes the dimension using something that looks like an entropy computation.

Digraph self-similarity

Here's an image of the twin dragon surrounded by 6 copies of itself.

enter image description here

The boundary consists of 6 parts, each of which is an intersection between the original twin dragon and one of the translated copies. That collection of 6 sets is exactly the invariant list of the following digraph IFS:

enter image description here

Thus, for example, the second piece consists of one copy of itself together with two copies of the first. To each edge corresponds one of two possible functions, namely $$f_0(z)=\frac{1+i}{2}z \: \text{ or } \: f_1(z)=\frac{1+i}{2}(z + 1).$$

To compute the dimension of the boundary, we count the number $N_n$ of walks of length $n$ through the graph. The graph is strongly connected so it's adjacency matrix is irreducible. The Perron-Frobenius theorem guarantees that there is a positive eigenvalue $\lambda$ that is strictly larger than the absolute values of all the other eigenvalues. Furthermore, $N_n$ grows like $\lambda^n$. The size of a neighborhood generated by a path of length $n$ is $2^{-n/2}$. The dimension of the boundary is then given by $$\lim_{n\rightarrow\infty}\frac{\log(N_n)}{\log(2^{n/2})} = 2\frac{\log(\lambda)}{\log(2)}.$$ The characteristic polynomial of the adjacency matrix is $$\lambda ^6-2 \lambda ^5+\lambda ^4-4=(\lambda +1) \left(\lambda ^2-2 \lambda +2\right) \left(\lambda ^3-\lambda ^2-2\right).$$ The largest root of the characteristic polynomial coincides with the largest root of $\lambda^3-\lambda ^2-2$ and is approximately $\lambda=1.69$. The dimension of the boundary is $$2\frac{\log(\lambda)}{\log(2)} \approx 1.52363.$$

As a sanity check, we should be able to generate a portion of the boundary using your formulation. It takes just a few lines of Mathematica code to do so and it seems worth a look.

Here's the whole set:

n = 15;
TPic = ListPlot[{Re[#], Im[#]} & /@ 
  (Tuples[{0, 1}, n].Table[((1 + I)/2)^k, {k, 0, n - 1}]),
  PlotStyle -> RGBColor[1/5, 1/3, 4/5]]

enter image description here

Note that Tuples[{0, 1}, n] generated a list of all tuples of zeros and ones of length $n$. We then took a dot product of that with a list of powers of $(1+i)/2$. Let's now try to do the same thing but, rather than using all tuples, we'll use only those tuples generated by a walk through the directed graph above starting at position 6. The code is a bit more involved than I should post here but that's the basic idea behind how I generated the the following pic:

enter image description here

Looks promising.

The description of the boundary of a self-similar tile as a collection of digraph self-similar sets was formulated the paper of Strichartz and Wang below. I wrote an exposition with Mathematica implementation here.

Strichartz, R. and Wang, Y. Geometry of self-affine tiles I. Indiana University Mathematics Journal. 1999 . 7:1-2 3.

  • $\begingroup$ This is a very nice answer, thanks! $\endgroup$ Jan 30, 2015 at 16:51

I you use the definition: $$\mathcal T=\left\{\sum_{n=0}^\infty a_n\left(\frac{1-i}2\right)^n : a_n\in\{0,1\}\right\}$$ it seems that the words on the boundary are exactly those recognized by the automaton (e.g.) in [https://www.ricam.oeaw.ac.at/publications/reports/06/rep06-02.pdf] (Figure 2). For your definition, it seems that we have to complement every letter in odd position.


If you take the automaton of https://www.ricam.oeaw.ac.at/publications/reports/06/rep06-02.pdf (6 states) and you complement every one-in-two letter, you get a 12 states automaton, which can be simplified to a 6 states automaton. If you construct the transducer I gave in comment (which is potentially infinte) and you take the (non trivial) strongly connected component, you get the following 6 states transuducer (which is the same automaton if you forget the "output", i.e. the part after ':' in the arrows):

(Note : $x = (1+i)/2$)

If X is the set of all words accepted by the previous transducer (all states are initial states), you get the set in white:

There are 6 neightboor tiles, each one corresponds to a translation which corresponds to a state.

  • 1
    $\begingroup$ This is a bit vague. I thought for a simple case like this one could tell precisely what the set of forbidden words for the subshift $X$ is. $\endgroup$ Jan 27, 2015 at 12:57
  • $\begingroup$ $X$ is recognizable by an automaton. The basic idea to construct the automaton is the following: $\mathcal T$ periodicaly tile the plane with the translations "vectors" 1 and $i$. A binary word $w$ corresponds to a complex point $x$ in $\mathcal T$ : $w$ is the fractionnal digits in the (1+i)/2-base of $x$. $x$ is on the boundary if $x+a$ is also in $\mathcal T$ for integer complex a $\ne 0$. Now, since $\alpha=(1+i)/2$ is a root of $2*X^2=2*X-1$, one can encode the addition on binary words by a transducer. E.g. from the state $+1$ and we read $1$, we write $0$ and go to the state $+2-\alpha$. $\endgroup$
    – user38477
    Jan 27, 2015 at 17:27
  • $\begingroup$ Little correction: $i$ is not a translation vector of the tilling. But we can use e.g. $1$ and $2\alpha$. And thus $a$ has to be a integer combinaison of $1$ and $2\alpha$. Note: I start the sum in the definition of $\mathcal T$ at 1 and not 0. $\endgroup$
    – user38477
    Jan 29, 2015 at 8:57

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.