# On the boundary of the twindragon

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\}.$$

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

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.

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:

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


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:

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.

• This is a very nice answer, thanks! – Nikita Sidorov Jan 30 '15 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.

Edit:

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.

• 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. – Nikita Sidorov Jan 27 '15 at 12:57
• $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$. – user38477 Jan 27 '15 at 17:27
• 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. – user38477 Jan 29 '15 at 8:57