Computing admissible patches of a substitution

Question

I have been recently trying to look at substitution tilings with finite local complexity by examining their admissible patch\pattern atlas, which is sometimes called their language. I have also seen the term dictionary used.

To the best of my understanding, given a finite collection of proto-tiles $\mathcal{P}'$ and a substitution rule $S$ defined on these proto-tiles, an admissible patch\pattern $Q$ is a partial tiling that occurs in $S^n(P)$ for some $P\in \mathcal{P'}$ and $n\in \mathbb{N}$. This is at least the case when the substitution is symbolic and the prototiles are the letters of the alphabet.

From what I searched so far, I have not seen many give the way to compute these atlases\langauges, although I have seen people write them partially in some cases. Therefore I was wondering about a method or algorithm that people are using implicitly without mentioning.

I have only found two references for the computation of a language, for symbolic substitutions in $1$-dimension, in algorithm 3 of Grout: A 1-Dimensional Substitution Tiling Space Program and in section 3.2 of the paper Computations for symbolic substitutions, by Dan Rust and Scott Balchin.

My question is whether a variation of this algorithm is what people are using implicitly when giving admissible patches for general substitutions? For example in the book by Baake and Grimm, Aperiodic order, Volume 1: A Mathematical Invitation, when they talk about block substitutions in section 4.9 and inflation tilings in section 6?

I would appreciate any input on this question, and also corrections to any incorrect statements I may have made.

Answer 1

The higher dimensional situation isn't very different to the one-dimensional situation. Of course, there are probably quicker ways to do it than the following, but this at least works and is reasonably fast for most purposes. Also, keep in mind that this method is to check a single word/patch to see if it's legal. If you want to build the set of all legal words/patches of a particular size, then there are faster methods that 'build the language up' and let you use the fact that you know all patches of size at most $N$ to build the patches of size $N+1$.

Method

I think the method that Scott and I gave in that paper is a bit naïve and very much brute-force. There are faster methods.

In one dimension, for any legal word $u$, there must exist a partition $u_1u_2 = u$ and a power $p$ such that $u_1$ is a suffix of a word of the type $S^p(a_1)$ and $u_2$ is a prefix of a word of the type $S^p(a_2)$ (of course $u_1$ or $u_2$ may be empty). This just comes from the definition of a word being legal.

There are obviously only finitely many pairs of letters to consider and there are only finitely many prefix/suffix pairs of words of the form $S^p(a)$, so this is a finite check. How finite? Well bounds exist, and they come from the fact that for a primitive substitution $S$, there are constants $c, C$ so that for all $a \in \mathcal{A}$, $$c \lambda^k < |S^k(a)| < C \lambda^k,$$ where $\lambda$ is the Perron--Frobenius eigenvalue of the substitution matrix $M$ (and these constants can be calculated in an algorithmic fashion if required). The lower bound means that we just need to pick $k$ so that $c\lambda^k > |u|$ and then check the pairs $S^{k+i}(a)$ where $i \in \{0,1,\ldots, \#\mathcal{A}-1\}$ (in the worst case, you may have to go all the way to $i = \#\mathcal{A}-1$).

Higher dimensions

The same kind of argument works in higher dimensions, you just need to consider partitions into more than just a pair of patches. For instance, in a block substitution in 2d, maybe your legal patch comes from the meeting of four corners of large supertiles, so you need to partition your patch into four rectangles. This is where the geometry plays a role in higher dimensions. Thankfully though, for true inflation rules (not weird ones where some tiles don't grow under substitution), all supertiles are eventually larger than any particular ball, and so you just need to consider how tiles can surround a vertex/edge/face/etc., for which there are only finitely many possibilities (assuming FLC).

If you know that your substitutions is recognisable (which by Mossé/Solomyak is true for any aperiodic primitive substitution), that can also help immensely, as recognisability implies local recognisability, so up to the boundary of your patch, if your patch is legal, then there is a unique way to partition your patch into super-tiles, then super-super-tiles, etc., and so the only difficult work then is checking the boundaries, which can possibly introduce some choices that all need to be checked. In practice, this is the fastest method.

Example

For instance, let's check if the word $u = bbaababbabaababbaabbabaa$ is legal for the Thue-Morse substitution $S \colon a\mapsto ab, b\mapsto ba$. The Thue-Morse substitution is recognisable, so let's start cutting up into super-tiles then super-supertiles... (notice that we get more boundary problems to account for at every iteration)

$b(ba)(ab)(ab)(ba)(ba)(ab)(ab)(ba)(ab)(ba)(ba)a$ is the only legal way to cut $u$ into super-tiles.

$b(baab)(abba)(baab)(abba)(abba)(ba)a$ is the only legal way to cut $u$ into super-super-tiles.

$b(baababba)(baababba)(abba)(ba)a$ is the only legal way to cut $u$ into super${}^3$-tiles

We can't cut it up any more as there doesn't exist an internal super${}^4$-tile. What we can do now though is use the fact that we just need to find a four-letter legal word $v$ that has $u$ as a subword of its third substitutive image and we also know that the middle two letters have to be $b$s because $baababba = S^3(b)$. Well, there's only one such four-letter legal word and that's $abba$. And indeed, if we check $S^3(abba)$ we get $abbabaa |bbaababbabaababbaabbaba |ab$, which contains our word $u$ (between the bars).

If a word is not legal, then some part of the above process would have failed.

In higher dimensions, the process works exactly the same.