A traditional way of proving the aperiodicity of a tiling is to show that a tiling can be "deflated" so that groups of smaller tiles are converted into a larger, single tile from the prototile set.

People then go on to say that "Since symmetries of a tiling apply also to its deflations, translational symmetries should apply to deflations of a tiling." So, if some translational symmetry works by moving every tile in some direction by some specific amount, they say that you can deflate the tiling until two of the points being translated fall within the same tile and since this isn't (trivially) a symmetry, the tiling is aperiodic. For example, they do it here, when proving the aperiodicity of an outstounding tiling.

Why is "symmetries of a tiling apply also to its deflations" true? For example, imagine a regular square lattice and I choose a translational symmetry of this (of which there are an infinite) where every square is moved to the one just right of it. But then, I deflate the tiling by repeatedly grouping four adjacent tiles into larger 2x2 squares until there are two points which are moved by the translation which stay within the same square. This would suggest, by the logic above, that the original translation was contradictory and thus that square lattices are aperiodic (they are clearly not).

What am I failing to understand?


The property that hasn't been explicitly mentioned (and is necessary for precisely the reason you mention) is what is called recognisability or the unique composition property. That is, there exists a radius $R$ such that for any patch of tiles admitted by the inflation rule of radius at least $R$, there is exactly one way to 'recognise' into which inflated supertiles the patch can be decomposed.

Your square example is a standard one which shows that, if this property fails (there are always exactly four ways to decompose any admitted patch in inflated supertiles for any given $R$), then the tiling must have a period.

The idea is the following: Suppose $T$ is a tiling admitted by our inflation rule $\phi$ which has a period $x \neq 0$ so that $T = T+x$. Suppose that $\phi$ is also recognisable, with recognisability radius $R$. For simplicity, suppose that $R$ is much larger than $x$, which we can happily do as if $\phi$ is recognisable with radius $R$, then it is certainly recognisable with radius $R'>R$.

Let $P$ be a patch of tiles in $T$ with radius $R+x$. Then by recognisability, there exists a unique way to decompose the patch $P$ into a patch of supertiles $P^{(1)}$. But note that the patch of supertiles $P^{(1)} + x$ must also be a decomposition of (some slightly smaller, but still of radius $R$ sub-patch of) $P$, and so we potentially have a problem, as this would imply that the patch is not recognisable.

We need to be careful though as it is possible that $P^{(1)}$ and $P^{(1)} +x$ actually coincide as patches of supertiles on their overlap, in which case we haven't yet found a contradiction. In such a case, we instead look at iterating the inflation rule, and so look at $\phi^n$ for some large enough $n$. As long as $n$ is large enough, we can be sure that all supertiles of level $n$ have inner-radius larger than $x$, and hence it is impossible for $P^{(1)}$ and $P^{(1)} +x$ to coincide on the slightly smaller subpatch, meaning we really have found a way of decomposing the subpatch into more than one patch of inflated supertiles - contradicting recognisability.

I should mention that this is the easy direction. Boris Solomyak proved that the converse also holds in a very general setting in his paper

Solomyak B., Nonperiodicity implies unique composition for self-similar translationally finite Tilings, Discrete Comput Geom (1998) 20: 265.

Theorem: A finite local complexity inflation rule is recognisable if and only if all tilings admitted by the inflation rule have trivial group of translational symmetries.

(Example 1 in his paper is exactly the square lattice substitution you mention.)

  • $\begingroup$ This was very helpful, thank you! $\endgroup$ – Isky Mathews Nov 23 '17 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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