Result about Aperiodic Tilings for Finite Sets of Prototiles - and MathJax test

This is a quick blog post to accomplish two things:
  1. Get some content up on the blog, finally...
  2. Test some \(\rm\LaTeX\) code...
So, to get things rolling, here's a brief result from my thesis that is kind of cute.

Definitions and Preliminaries

So, first up we need the following notation:
  • Let \( \varphi_e \) be the \(e^{th}\) Turing Machine under some effective enumeration of all possible Turing Machines - some Gödel coding of all 5-tuples of all possible TM states.
  • If a machine \(e\) on input \(x\) halts, then we write \(\varphi_e(x) \downarrow\).
  • For a set \(A\) we notate the complement of \(A\) (that is, everything not in \(A\)) by \(\overline{A}\).
  • A formula \(\phi\) is in \(\Sigma^0_1\) if it is of the form \( \exists x \, ( \psi(x) ) \) where \(\psi\) is a formula without any free (read: only bounded) quantifiers over any other variables.
  • A formula \( \phi \) is \( \Pi^0_1\) if it is of the form \( \forall x \, ( \psi(x) ) \) that is, it is the complement of a \(\Sigma^0_1\) defined set.
These definitions are fairly standard in modern logic - we use this Kleene-Mostowski ('Clean-ee Moz-tov-skee') very liberally. There is one important fact we shall need in our proof:

Fact: Something is \(\Sigma^0_1\) iff it is computably enumerable.

For some set \(A\) to be 'computably enumerable' means that there is a Turing Machine that enumerates every member of \(A\). A formula is computably enumerable if there is a Turing Machine that halts precisely when the formula is true given some 'input' into its free variables. This result is very famous - and is exact, meaning that everything in \(\Sigma^0_1\) has some Turing Machine that halts when the formula is true, and vice versa.

The key takeaway here is that if something is 'computable' then it is \(\Sigma^0_1\). This is really due to the fact that if for some machine \(e\) and stage \(s\) of a computation (the initial stage being stage 0), if \(\varphi_{e,s}(x) \downarrow\)  then we can write this as \[ \exists s \, ( \varphi_{e,s}(x) \downarrow ) \] or in words "there exists a stage \(s\) at which \(\varphi_e(x)\) halts".

Tilings and Tiling Problems

Let a tiling be some covering of the plane \(\mathbb{R}^2\) using polygons such that every point is either to the interior of at most one polygon, or is on the edge joining two polygons. There is a lot to explore in this definition, but we're not that interested in that here - but I have lengthy discussions available.

We also need to define some tiling problems - specifically, the following problems:
  • A tiling is periodic if there is some non-zero shift vector \(\mathbf{v}\) such that for a given tiling \(T\) it holds that \( T = \mathbf{v}T \) - that is, if you shift a planar tiling \(T\) by the vector \(\mathbf{v}\) then you get back your original tiling \(T\).
  • A tiling is aperiodic if there is no such vector existing. 

This may seem like a bit of a cop out - but these definitions are quite old (see Grunbaum and Shepard, 1987). The idea is that aperiodicity is quite easy to achieve manually... take a tiling that is just white squares, and then bisect one square. You now have a tiling with no non-zero shift vector \(\mathbf{v}\) existing, so it's aperiodic.

Whilst examples like this one are not that interesting, there are plenty of interesting aperiodic prototile sets - such as Penrose Tilings, or a very exciting recent result due to Jeandel and Rao that shows that there are no possible sets of aperiodic Wang tiles with fewer than 11 prototiles.

Proving a prototile set is aperiodic is, however, very tricky. There are two main techniques:
  1. Prove that it reduces to a transducer or Turing Machine of an aperiodic computation.
  2. Showing that the tile set can simulate itself - leading to an inflation/deflation argument that then results in a lack of periodicity.
Examples of one include ideas such as such as computing Champernowne's Constant in a tiling, or as Kari and Culik showed, computing some non-repeating real.

However the second technique listed here is the original one used by Penrose to prove that the Penrose rhombi tilings were aperiodic. We'll give an example of this now, because it's a fun proof.

Aperiodicity through self-similarity

There is an easy way to represent this argument - taken from a paper by Shen, Durand, and Romashchenko that details the argument very well. First we need the following definitions. We fix our 'tiling world' as Wang prototiles - as such, given two sets of tiles \(A\) and \(B\):
  • We say \(A\) implements \(B\) if there is some way of splitting an \(A\)-tiling into pieces such that the resulting split is akin to a \(B\)-tiling. 
    • In the paper, the tiles in \(B\) are called 'macro' tiles.
  •  If \(A\) is isomorphic to \(B\) then we say that \(A\) is self-similar.
The following theorem and proof are taken from the paper above (https://arxiv.org/pdf/1003.2801.pdf), p.3. 

Theorem (S-D-R, 2010) - any set of prototiles \(A\) that is self-similar has only aperiodic tilings.

Proof - Suppose for contradiction that we let \(p \in \mathbb{N}\) be the period of some \(A\)-tiling \(T\). Given \(T\) is self-similar, then it has a split into macro tiles, each split block of tiles therefore being isomorphic to a tile in \(A\).

Now, a shift vector \(\mathbf{v}\) must respect this splitting, so if we replace every block of tiles with the corresponding tile in \(A\) and then 'zoom out' (rescale) our tiling then we have an \(A\)-tiling with a \(\mathbf{v} / p \) shift vector.

If we repeat this \(k\)-many times (for \(k \in \mathbb{N} \)) then we have a shift vector \(\mathbf{v} / p^k \). Given we can keep on doing this replacement and rescaling argument infinitely often, it becomes apparent that our shift vector becomes smaller and smaller and after doing this infinitely often is a zero vector, which is a contradiction (as a periodic tiling has a non-zero shift vector). \(\Box\)

Now that we've had our first Halmos Tombstone, we can carry on.

Logical Complexity of Aperiodicity of Finite sets of Prototiles

Let the following definitions be given
\begin{align*}
PTile_{FIN} = \{ e : & \, \varphi_e \text{ is the characteristic function} \\
& \text{for a finite set of prototiles that is periodic} \} \\
ATile_{FIN} = \{ e : & \, \varphi_e \text{ is the characteristic function} \\
& \text{for a finite set of prototiles that is aperiodic} \}
\end{align*}
With these defined, we will use the second one and show that the following is true:

Theorem: (C. 2019) \[ ATile_{FIN} \in \Pi^0_1 \] Proof - Let \(S\) be a finite prototile set, and define the following set: \[ EPTile_{FIN} = \{ e : \text{ there exist periodic tilings given by } \varphi_e \} \] Given it is equivalent to the halting state of a TM that finds the period of some \(S\)-tiling $T$, specifically \[ \psi(S) = \exists s ( s \text{ is the period of an $S$-tiling } T ) \] it naturally follows that \[ EPTile_{FIN} \in \Sigma^0_1 \] Note that this computable search across all possible tilings can proceed iteratively along a sequence of \(S\)-tilings, which are enumerable given \(S\) is finite, given by \[ T_0, T_1, T_2, \ldots \] We only require that our search stops once for \(S\) to be in \(EPTile_{FIN}\).

We now note that \(\neg \psi(S)\) is equivalent to saying that our periodicity finding machine will not halt for any \(S\)-tiling, noting that this does not require set comprehension. Thus, \[\neg \psi(S) \in \Pi^0_1\] and given this is equivalent to saying every \(S\)-tiling is aperiodic, the theorem follows by: \[ ATile_{FIN} = \overline{EPTile_{FIN}} \] \(\Box\)

Other results 

In my thesis, I proved a number of other theorems and lemmas. The title is 'Computability and Tiling Problems' and covers quite a few fun bits of how these two areas relate and interact. Specifically I worked on what happens if you ask questions of the form 'does it tile the plane?' or 'does it have only periodic/aperiodic tilings?' but to infinite sets of prototiles.

Spoiler - basically, most things lift from the arithmetical hierarchy to the analytic/inductive hierarchy... they go from \(\Pi^0_1\) to \(\Pi^1_1\).


Comments

Popular posts from this blog

Decrypting config.bin files for TP-Link WR841N, WA855RE, and probably more…

How to Break XOR Encryption with just 20 Million USD of Quantum Computer!

Aperiodic Tilings