# An aperiodic set of 11 Wang tiles

Emmanuel Jeandel and Michael Rao

###### Abstract

A new aperiodic tile set containing 11 Wang tiles on 4 colors is presented.
This tile set is minimal in the sense that no Wang set with less than 11 tiles
is aperiodic, and no Wang set with less than 4 colors is aperiodic.

Wang tiles are square tiles with colored edges. A tiling of the plane by Wang
tiles consists in putting a Wang tile in each cell of the grid $\mathbb{Z}$ so
that contiguous edges share the same color. The formalism of Wang tiles was
introduced by Wang [Wan61] to study decision procedures for a specific
fragment of logic (see section 1.1 for details).

Wang asked the question of the existence of an aperiodic tile set: A set of
Wang tiles which tiles the plane but cannot do so periodically. His student
Berger quickly gave an example of such a tile set, with a tremendous number of
tiles. The number of tiles needed for an aperiodic tileset was reduced during
the years, first by Berger himself, then by others, to obtain in 1996 the
previous record of an aperiodic set of 13 Wang tiles. (see section 1.2 for an
overview of previous aperiodic sets of Wang tiles).

While reducing the number of tiles may seem like a tedious exercise in itself,
the articles also introduced different techniques to build aperiodic tilesets,
and different techniques to prove aperiodicity.

A few lower bounds exist on the number of Wang tiles needed to obtain an
aperiodic tile set, the only reference [GS87] citing the impossibility to have
one with 4 tiles or less. On the other hand, recent results show that an
aperiodic set of Wang tiles need to have at least 4 different colors [CHLL14].

In this article, we fill all the gaps: We prove that there are no aperiodic
tile set with less than 11 Wang tiles, and that there is an aperiodic tile set
with 11 Wang tiles and 4 colors.

The discovery of this tile set, and the proof that there is no aperiodic tile
set with a smaller number of tiles was done by a computer search: We generated
in particular all possible candidates with 10 tiles or less, and prove they
were not aperiodic. Surprisingly it was somewhat easy to do so for all of them
except one. The situation is different for 11 tiles: While we have found an
aperiodic tileset, we also have a short list of tile set for which we do not
know anything. The description of this computer search is described in section
3 of the paper, and can possibly be skipped by a reader only interested in the
tile set itself. This section also contains a result of independent interest:
the tile set from Culik with one tile omitted does not tile the plane.

The tile set itself is presented in section 4, and the remaining sections
prove that it is indeed an aperiodic tileset.

##  1 Aperiodic sets of Wang tiles

Here is a brief summary of the known aperiodic sets of Wang tiles.
Explanations about some of them may be found in [GS87]. We stay clear in this
history about aperiodic sets of geometric figures, and focus only on Wang
tiles.

###  1.1 Wang tiles and the $\forall\exists\forall$ problem

Wang tiles were introduced by Wang [Wan61] in 1961 to study the decidability
of the $\forall\exists\forall$ fragment of first order logic. Wang showed in
this article how to build, starting from a $\forall\exists\forall$ formula
$\phi$, a set of tiles $\tau$ and a subset $\tau^{\prime}\subseteq\tau$ so
that there exists a tiling by $\tau$ of the upper quadrant with tiles in the
first row in $\tau^{\prime}$ iff $\phi$ is satisfiable. If this particular
tiling problem was decidable, this would imply that the satisfiability of
$\forall\exists\forall$ formulas was decidable.

Wang asked more generally in this article whether the more general tiling
problem (with no particular tiles in the first row) is decidable and gave the
_fundamental conjecture_ : Every tileset either admits a periodic tiling or
does not tile.

Regardless of the status of this particular conjecture, Kahr, Moore and Wang
[KMW62] proved the next year that the $\forall\exists\forall$ problem is
indeed undecidable by reducing to another tiling problem: now we fix a subset
$\tau^{\prime}$ of tiles so that every tile on the diagonal of the first
quadrant is in $\tau^{\prime}$. This proof was later simplified by Hermes
[Her71, Her70]. From the point of view of first order logic, the problem is
thus solved. Formally speaking, the tiling problem with a constraint diagonal
is reduced to a formula of the form $\forall x\exists y\forall z\phi(x,y,z)$
where $\phi$ contains a binary predicate $P$ and some occurences of the
subformula $P(x,x)$ (to code the diagonal constraint). If we look at
$\forall\exists\forall$ formulas that do not contain the subformula $P(x,x)$
and $P(z,z)$, the decidability of this particular fragment remained open.

A few years later, Berger proved however [Ber64] that the domino problem is
undecidable, and that an aperiodic tileset existed. This implies in particular
that the particular fragment of $\forall x\exists y\forall z$ where the only
occurences of the binary predicates $P$ are of the form
$P(x,z),P(y,z),P(z,y),P(z,x)$ was undecidable.

A few other subcases of $\forall\exists\forall$ were done over the years. In
1975, Aanderaa and Lewis [AL74] proved the undecidability of the fragment of
$\forall\exists\forall$ where the binary predicates $P$ can only appear in the
form $P(x,z)$ and $P(z,y)$. It has in particular the following consequence:
The domino problem for _deterministic_ tilesets is undecidable

###  1.2 Aperiodic tilesets

The first example of a set of Wang tiles was provided by Berger in 1964. The
set contained in the 1966 AMS publication [Ber66] contains 20426 tiles, but
Berger’s original PhD Thesis [Ber64] also contains a simplified version with
104 tiles. This tileset is of a substitutive nature. Knuth [Knu68] gave
another simplified version of Berger’s original proof with 92 tiles.

Lauchli obtained in 1966 an aperiodic set of 40 Wang tiles, published in 1975
in a paper of Wang [Wan75].

Robinson found in 1967 an aperiodic set of 52 tiles. It was mentioned in a
Notices of the AMS summary, but the only place this set can be found is in an
article of Poizat [Poi80]. His most well known tileset is however a 1969
tileset (published in 1971) [Rob71] of 56 tiles. The paper hints at a set of
35 Wang tiles.

Robinson managed to lower the number of tiles again to 32 using a idea due to
Roger Penrose. The same idea is used by Grunbaum and Shephard to obtain an
aperiodic set of 24 tiles [GS87]. Robinson obtained in 1977 a set of 24 tiles
from a tiling method by Ammann. The record for a long time was held by Ammann,
who obtained in 1978 a set of 16 Wang tiles. Details on these tilesets are
provided when available in [GS87]

In 1975, Aanderaa and Lewis [AL74] build the first aperiodic _deterministic_
tileset. No details about the tileset are provided but it is possible to
extract one from the exposition by Lewis [Lew79]. This construction was
somehow forgotten in the literature and the first aperiodic deterministic
tileset is usually attributed to Kari in 1992 [Kar92].

In 1989, Mozes showed a general method that can be used to translate any
substitution tiling into a set of Wang tiles [Moz89], which will be of course
aperiodic. There are multiple generalizations of this result (depending of the
exact definition of “substitution tiling”), of which we cite only a few [GS98,
FO10, lGO12]. For a specific example, Socolar build such a representation
[Sen95] of the chair tiling, which in our vocabulary can be done using 64
tiles.

The story stopped until 1996 when Kari invented a new method to build
aperiodic tileset and obtained an aperiodic set of 14 tiles [Kar96]. This was
reduced to 13 tiles by Culik [Cul96] using the same method. There was
suspicion one of the 13 tiles was unnecessary, and Kari and Culik hinted to a
method to show it in a unpublished manuscript. However this is not true: the
method developed in this article will show this is not the case.

In 1999, Kari and Papasoglu [KP99] presented the first 4-way deterministic
aperiodic set. The construction was later adapted by Lukkarilla to provided a
proof of undecidability of the 4-way domino problem [Luk09].

The construction of Robinson was later analyzed [Sal89, AD01, JM97, FGS12] and
simplified. Durand, Levin and Shen presented in 2004 [DLS04] a way to simplify
exposition of proofs of aperiodicity of such tilesets. Ollinger used this
method in 2008 to obtain an aperiodic tileset with 104 tiles [Oll08], with
striking resemblance to the original set of 104 tiles by Berger. Other
simplifications of Robinson constructions where given by Levin in 2005 [Lev05]
and Poupet in 2010 [Pou10] using ideas similar to Robinson.

In 2008, Durand, Romashchenko and Shen provided a new construction based on
the classical fixed point construction from computability theory [DSR08,
DRS12].

##  2 Preliminaries

###  2.1 Wang tiles

A _Wang tile_ is a unit square with colored edges. Formally, let $H,V$ be two
finite sets (the horizontal and vertical colors, respectively). A wang tile
$t$ is an element of $H^{2}\times V^{2}$. We write
$t=(t_{w},t_{e},t_{s},t_{n})$ for a Wang tile, and use interchangeably the
notations $t_{w}$ (resp. $t_{e},t_{s},t_{n}$) or $w(t)$ (resp.
$e(t),s(t),n(t))$ to indicate the color on one of the edges.

A _Wang set_ is a set of Wang tiles, formally viewed as a tuple $(H,V,T)$,
where $T\subseteq H^{2}\times V^{2}$ is the set of _tiles_. Fig. 1 presents a
well known example of a Wang set. A Wang set is said to be _empty_ if
$T=\emptyset$.

Let $\mathcal{T}=(H,V,T)$ be a Wang set. Let $X\subseteq\mathbb{Z}^{2}$. A
_tiling of $X$ by $\mathcal{T}$_ is an assignation of tiles from $\mathcal{T}$
to $X$ so that contiguous edges have the same color, that is it is a function
$f:X\to T$ such that $e(f(x,y))=w(f(x+1,y))$ and $n(f(x,y))=s(f(x,y+1))$ for
every $(x,y)\in\mathbb{Z}^{2}$ when the function is defined. We are especially
interested in the tilings of $\mathbb{Z}^{2}$ by a Wang set $\mathcal{T}$.
When we say a _tiling of the plane by $\mathcal{T}$_, or simply a _tiling by
$\mathcal{T}$_, we mean a tiling of $\mathbb{Z}^{2}$ by $\mathcal{T}$.

A tiling $f$ is _periodic_ if there is a
$(u,v)\in\mathbb{Z}^{2}\setminus(0,0)$ such that $f(x,y)=f(x+u,y+v)$ for every
$(x,y)\in\mathbb{Z}^{2}$. A tiling is _aperiodic_ if it is not periodic.

A Wang set _tiles $X$_ (resp. _tiles the plane_) if there exists a tiling of
$X$ (resp. the plane) by $\mathcal{T}$. A Wang set is _finite_ if there is no
tiling of the plane by $\mathcal{T}$. A Wang set is _periodic_ if there is a
tiling $t$ by $\mathcal{T}$ which is periodic. A Wang set is _aperiodic_ if it
tiles the plane, and every tiling by $\mathcal{T}$ is not periodic.

We quote here a few well known folklore results:

######  Lemma 1.

If $\mathcal{T}$ is periodic, then there is a tiling $t$ by $\mathcal{T}$ with
two linearly independent translation vectors (in particular a tiling $t$ with
vertical and horizontal translation vectors).

######  Lemma 2.

If for every $k\in\mathbb{N}$, there exists a tiling of
$[0,\ldots,k]\times[0,\ldots,k]$ by $\mathcal{T}$, then $\mathcal{T}$ tiles
the plane.

###  2.2 Transducers

One of the most trivial but crucial observation we will use in this article is
that Wang sets $(H,V,T)$ may be viewed as finite state transducers, where each
transition reads and writes one letter, and without initial nor final states:
$H$ is the set of states, $V$ is the input and output alphabet, and $T$ is the
set of transitions. Fig. 1 presents in particular the popular set of Wang
tiles introduced by Culik from both point of views.

$1$$0$$2$$0^{\prime}$$\frac{1}{2}$$1|2$$1|1$$1|2$$0|1$$0|2$$0|1$$0^{\prime}|0$$2|1$$1|0$$1|0^{\prime}$$0^{\prime}|0$$2|1$$1|1$

$0$$1$$2$$1$$0$$2$$1$$1$$1$$2$$2$$1$$1$$0$$1$$0$$2$$0$$2$$0$$2$$1$$1$$0$$0^{\prime}$$0^{\prime}$$0$$0^{\prime}$$0^{\prime}$$0^{\prime}$$1$$2$$0^{\prime}$$\frac{1}{2}$$0$$1$$0^{\prime}$$\frac{1}{2}$$0^{\prime}$$1$$\frac{1}{2}$$\frac{1}{2}$$0$$0^{\prime}$$\frac{1}{2}$$\frac{1}{2}$$1$$2$$\frac{1}{2}$$0^{\prime}$$1$$1$

Figure 1: The aperiodic set of 13 tiles obtained by Culik from an idea of
Kari: the transducer view and the tiles view.

In this formalism, tilings correspond exactly to (biinfinite) runs of the
transducer. If $w$ and $w^{\prime}$ are biinfinite words over the alphabet
$V$, we will write $w\mathcal{T}w^{\prime}$ if $w^{\prime}$ is the image of
$w$ by the transducer. The transducer is usually nondeterministic so that this
is indeed a (partial) relation and not a function.

The composition of Wang sets, seen as transducers, is straightforward: Let
$\mathcal{T}=(H,V,T)$ and $\mathcal{T}^{\prime}=(H,V^{\prime},T^{\prime})$ be
two Wang sets. Then $\mathcal{T}\circ\mathcal{T}^{\prime}$ is the Wang set
$(H\times H^{\prime},V,T^{\prime\prime})$, where

$T^{\prime\prime}=\\{((w,w^{\prime}),(e,e^{\prime}),s,n^{\prime}):(w,e,s,n)\in
T,(w^{\prime},e^{\prime},s^{\prime},n^{\prime})\in T^{\prime}\text{ and
}n=s^{\prime}\\}.$

Let $\mathcal{T}^{k}$, $k\in\mathbb{N}^{*}$ be $\mathcal{T}$ if $k=1$,
$\mathcal{T}^{k-1}\circ\mathcal{T}$ otherwise.

A reformulation of the original question is as follows:

######  Lemma 3.

A Wang set $\mathcal{T}$ is finite if there is no infinite run of the
transducer $\mathcal{T}$: There is no biinfinite sequence
$(w_{k})_{k\in\mathbb{N}}$ so that $w_{k}\mathcal{T}w_{k+1}$ for all $k$.

A Wang set $\mathcal{T}$ is periodic iff there exists a word $w$ and a
positive integer $k$ so that $w\mathcal{T}^{k}w$.

We will also use the following operations on tile sets (or transducers):

rotation

Let ${\mathcal{T}}^{\operatorname{tr}}$ be $(V,H,T^{\prime})$ where
$T^{\prime}=\\{(s,n,e,w):(w,e,s,n)\in T\\}$. This operation corresponds to a
rotation of the tileset by $90$ degrees.

simplification

Let $s({\mathcal{T}})$ be the operation that deletes from $\mathcal{T}$ any
tile that cannot be used in a tiling of a (biinfinite) line row by
$\mathcal{T}$. This corresponds from the point of view of transducers to
eliminating sources and sinks from $\mathcal{T}$. In particular
$s({\mathcal{T}})$ is empty iff there is no words $w,w^{\prime}$ s.t.
$w\mathcal{T}w^{\prime}$.

union

$\mathcal{T}\cup\mathcal{T}^{\prime}$ is the disjoint union of transducers
$\mathcal{T}$ and $\mathcal{T}^{\prime}$: We first rename the states of both
transducers so that they are all different, and then we take the union of the
transitions of both transducers. Thus
$w(\mathcal{T}\cup\mathcal{T}^{\prime})w^{\prime}$ iff
$w\mathcal{T}w^{\prime}$ or $w\mathcal{T}^{\prime}w^{\prime}$.

##### Equivalence of Wang sets.

Once Wang sets are seen as transducers, it is easy to see that the problems
under consideration do not depend actually on $\mathcal{T}$, but only on the
relation induced by $\mathcal{T}$: We say that two Wang sets
$\mathcal{T}=(H,V,T)$ and $\mathcal{T}^{\prime}=(H^{\prime},V,T^{\prime})$ are
_equivalent_ if they are equivalent as relations, that is, for every pair of
bi-infinite words $(w,w^{\prime})$ over $V$,
$w\mathcal{T}w^{\prime}\Leftrightarrow w\mathcal{T}^{\prime}w^{\prime}$.

In the course of the proofs and the algorithms, it will be interesting to
switch between equivalent Wang sets (transducers), in particular by trying to
simplify as much as possible the sets: we can for example apply the operator
$s({\mathcal{T}})$ to trim the colors/states (and thus the tiles/transitions)
that cannot appear in a infinite row (e.g. sources/terminals of the transducer
seen as a graph), or reduce the size of the transducer by coalescing
“equivalent” states.

There are a few algorithms to simplify Wang sets. First, as our transducers
are nothing but (nondeterministic) finite automata over the alphabet $V\times
V$, it is tempting to try to _minimise_ them. However state (or transition)
minimisation of nondeterministic automata is PSPACE-complete ; The other
strategy of building the minimal determinic automaton is also not efficient in
practice. The algorithm we used is based on the notion of _strong bisimulation
equivalence_ of labeled transitions sytems [KS90, PT87, Val10, bie03]. It
allows us to find efficiently states that are equivalent (in some sense) and
thus can be collapsed together. It can be thought of as the non-deterministic
equivalent of the classical minimization algorithm for deterministic automata
from Hopcroft [Hop71].

##  3 There is no aperiodic Wang sets with 10 tiles or less

In this section, we give a brief overview of the techniques involved in the
computer assisted proof that there are not aperiodic Wang set with 10 tiles or
less.

The general method of the algorithm is obvious: generate all Wang sets with 10
tiles or less, and test whether there are aperiodic. There are two
difficulties here: first, there are a large number of Wang sets with 10 tiles:
For maximum efficiency, we have to generate as few of them as possible, that
is discard as soon as possible Wang sets that are provably not aperiodic. Then
we have to test the remaining sets for aperiodicity. Aperiodicity is of course
an undecidable problem: our algorithm will not succeed on all Wang sets, and
the remaining ones will have to be examined by hand.

###  3.1 Generating all Wang sets with 10 tiles or less

According to the general principle above, we actually do not have to generate
all Wang sets: we can refrain from generating sets that we know are not
aperiodic.

Let $\mathcal{T}$ be a Wang set. We say that $\mathcal{T}$ is minimally
aperiodic if $\mathcal{T}$ is aperiodic and no proper subset of $\mathcal{T}$
is aperiodic (that is no proper subset of $\mathcal{T}$ tiles the plane). We
will introduce criteria proving that some Wang sets are not minimally
aperiodic, and thus that we do not need to test them.

The key idea is to look at the graph $G$ underlying the transducer. Note that
this is actually a _multigraph_ : there might be multiple edges(transitions)
joining two given vertices (states), and there might also be self-loops.

This approach was also introduced in [JR12], and the following lemma is more
or less implicit in this article:

######  Lemma 4.

Let $\mathcal{T}$ be a Wang set, and $G$ the corresponding graph.

  * •

Suppose there exist two vertices/states/colors $u,v\in G$ so that there is an
edge (hence a tile/transition) from $u$ to $v$ and no path from $v$ to $u$.
Then $\mathcal{T}$ is not minimal aperiodic.

  * •

Suppose $G$ contains a strongly connected component which is reduced to a
cycle. Then $\mathcal{T}$ is not minimal aperiodic.

  * •

If the difference between the number of edges and the number of vertices in
$G$ is less than 2, then $\mathcal{T}$ is not minimal aperiodic.

###### Proof.

In terms of tiles, the first case corresponds to a tile $t$ that can appear at
most one in each row. If $\mathcal{T}$ tiles the plane, $\mathcal{T}$ tiles
arbitrarily large regions without using the tile $t$. By compactness,
$\mathcal{T}\setminus\\{t\\}$ tiles the plane.

For the second case, suppose such a component exists. This means there exist
some tiles $S\subseteq\mathcal{T}$ so that every time one of the tiles in $S$
appear, then the whole row is periodic (of period the size of the cycle). If
$\mathcal{T}$ is aperiodic, we cannot have a tiling where tiles of $S$ appear
in two different rows, as we could deduce from it a periodic tiling. As a
consequence, tiles from $S$ appear in at most one row, and using the same
compactness argument as before we deduce that $\mathcal{T}\setminus S$ tiles
the plane.

The proof of the third case can be found in [JR12]. ∎

This lemma gives a bird’s eye-view of the program: For a given $n\leq 10$,
generate all (multi)graphs $G$ with $n$ edges and at most $n-2$ vertices
satisfying the hypotheses of the lemma, then test all Wang sets for which the
underlying graph in $G$. In terms of Wang tiles, a graph correspond to a
specific assignation of colors to the east/west side: for this particular
assignation, we test all possible assignations of colors to the north/south
side.

The exact approach used in the software follows this principle, trying as much
as possible not to generate isomorphic tilesets.

###  3.2 Testing Wang sets for aperiodicity

We explained in the previous section how we generated Wang sets to test. We
now explain how we tested them for aperiodicity.

####  3.2.1 Easy cases

Recall that a Wang set is _not_ aperiodic if

  * •

Either there exists $k$ so that $s({\mathcal{T}^{k}})$ is empty: there is no
word $w,w^{\prime}$ so that $w\mathcal{T}^{k}w^{\prime}$

  * •

or there exists $k$ so that $\mathcal{T}^{k}$ is periodic: there exists a word
$w$ so that $w\mathcal{T}^{k}w$

The general algorithm to test for aperiodicity is therefore clear: for each
$k$, generate $\mathcal{T}^{k}$, and test if one of the two situations happen.
If it does, the set is not aperiodic. Otherwise, we go to the next $k$. The
algorithm stops when the computer program runs out of memory. In that case,
the algorithm was not able to decide if the Wang set was aperiodic (it is
after all an undecidable problem), and we have to examine carefully this Wang
set.

This approach works quite well in practice: when launched on a computer with a
reasonable amount of memory, it eliminates a very large number of tilesets. Of
course, the key idea is to simplify as much as possible $\mathcal{T}^{k}$
before computing $\mathcal{T}^{k+1}$. Note that this should be done as fast as
possible, as this will be done for _all_ Wang sets. It turns out that the easy
simplification that consists in deleting at each step tiles that cannot appear
in a tiling of a row (i.e. vertices that are sources/terminals) is already
sufficient.

It is important to note that this approach relying on transducers (test
whether the Wang set tiles $k$ consecutive rows, and if it does so
periodically) turned out in practice to be much more efficient than the naive
approach using tilings of squares (test whether the Wang set tiles a square of
size $k$, and if it does so periodically).

####  3.2.2 Harder cases

Once this has been done, a small number of Wang sets remain (at most 200), for
which the program was not able to prove that they tile the plane periodically
or that they do not tile the plane.

The first step for these sets was to use the same idea as before, but with a
larger memory, and additional optimizations, which involved simplifying
$\mathcal{T}^{k}$ as much as possible before examining it. Two additional
simplifications were used: First, we may delete from $\mathcal{T}^{k}$
tiles(transitions) that connect different strongly connected components: using
the same argument as in Lemma 4, it is easy to see that deleting these tiles
do not change the aperiodic status of $\mathcal{T}^{k}$. Second, we have
applied bisimulation techniques to reduce as much as possible the size of the
transducer $\mathcal{T}^{k}$. We want to stress that this technique proved to
be crucial: the gain obtained by bisimulation is tremendous.

####  3.2.3 The hardest case

Using these ameliorations on the $\sim 200$ remaining Wang sets was
successful: all of them were quickly proven to be not aperiodic. Well not
entirely! One small set of indomitable tiles still held out against the
program.

This particular set of tiles is presented in Fig. 2. It turned out that this
particular Wang set is a special case of a general construction introduced by
Kari [Kar96] of aperiodic Wang sets, except a few tiles are missing. At this
point, the situation could have become desperate: It is not known if tilings
obtained by the method of Kari but missing a few tiles may tile the plane. In
fact, it was open whether it was possible to delete a tile from the 13 tileset
from Culik [Cul96] to obtain a set that still tiles the plane111You will find
many experts on tilings that recollect this story wrongly and think that the
(13) Wang set by Culik is the (14) Wang set from Kari with one tile removed.
It is not the case. What happened is that there is one tile from the (13) Wang
set by Culik that seemed likely to be unnecessary. (and it was conjectured by
both Kari and Culik that it was indeed possible).

$1$$0$$1|2$$1|2$$1|3,0|1$$2|3,1|1$

$2/3$$0^{\prime}$$3|1$$3|1$$1|1$$2|0$

Figure 2: A set of 10 tiles that tries very hard, but fails to tile the plane.
It tiles however a square of size $212\times 212$

However we were able to prove that this tileset does not in fact tile the
plane. Wang sets belonging to the family identified by Kari all work in the
same way: The infinite words that appear on each row can be thought of as
reals, by taking the average of all numbers (between $0$ and $3$ in our
example) that appear on the row. Then what the tileset is doing is applying a
given piecewise affine map to the real number. In the case of our set of 10
tiles, the map $f$ is as follows:

  * •

If $1/2\leq x\leq 3/2$, then $f(x)=2x$

  * •

If $3/2\leq x\leq 3$, then $f(x)=x/3$

As can be seen from the first transducer, there cannot be two consecutive 0 in
$x$, this guarantees that $x\geq 1/2$ hence $x\not=0$, and in particular that
this tileset has no periodic tiling.

If we used the general method by Kari to code this particular tileset, the
transducer that divides by $3$ would have $8$ tiles. However, our particular
set of 10 tiles does so with only $4$ tiles. There is a way to explain how the
division by $3$ works. First, let’s see it like a multiplication by $3$ by
reversing the process. Recall that the Beatty expansion of a real $x$ is given
by $\beta_{n}(x)=\left\lceil(n+1)x\right\rceil-\left\lceil nx\right\rceil$.
Then it can be proven:

######  Fact 1.

Let $0<x\leq 1$ and define $b_{n}(x)=2\beta_{n}(2x)-\beta_{n}(x)$. Then the
second transducer transforms $(\beta_{n})_{n\in\mathbb{N}}$ into
$(b_{n})_{n\in\mathbb{N}}$.

Hence, the second transducer multiplies by $3$ by doing $2\times 2\times x-x$
somehow. It can be seen as a composition of a transducer that transforms
$(\beta_{n})_{n\in\mathbb{N}}$ into $(\beta_{n},b_{n})_{n\in\mathbb{N}}$ (this
can be done with only two states, using the method by Kari) and a transducer
mapping each symbol $(x,y)$ into $2y-x$, which can be done using only one
state (this is just a relabelling).

There is indeed no reason that doing the transformation this way would work
(in particular the equations given by Kari cannot be applied to this
particular transducer and prove that there is indeed a tiling), and indeed it
doesn’t: we were able to prove that this particular Wang set does not, in
fact, tile the plane.

Once this tileset was identified as belonging to the family of Kari tilesets,
it is indeed easy to see that, should it tile the plane, it tiles a half plane
starting from a word consisting only of $3$.

We then started from a transducer $\mathcal{T}^{\prime}$ that outputs a
configuration with only the symbol $3$, and build recursively
$t_{k}=\mathcal{T}^{\prime}\mathcal{T}^{k}$. It turns out that $t_{31}$ (once
reduced) is empty, which means that we cannot tile $31$ consecutive rows
starting from a word consisting only of $3$.

######  Theorem 1.

There is no aperiodic Wang set with 10 tiles or less.

Before removing unused transitions, $t_{31}$ contains a path of $212$ symbols
$3$. This means in particular that there exists a tiling of a rectangle of
size $212\times 31$ where the top and the bottom side are equal, thus a tiling
of a infinite vertical strip of width 212 by this tiling, and thus a tiling of
a square of size $212\times 212$.

We want again to stress how much the simplification of the transducers by
bisimulation was crucial. Our first proof that this tileset does not tile the
plane did not use this and 3 months were needed to prove the result,
generating sets of the order of $2^{32}$ (4 billion) tiles. Using bisimulation
for the simplification of transducers, the result can be proven in 2 minutes,
with the largest Wang set having $2^{26}$ (50 million) tiles.

The fact everything fall apart for $k=31$ can be explained. If we identify
$([0.5,3]_{0.5\sim 3},\times)$ with the unit circle $([0,1]_{0\sim 1},+)$,
what $f$ is doing is now just an addition (modulo $1$) of $\frac{\log 2}{\log
2+\log 3}$. Now $31\frac{\log 2}{\log 2+\log 3}=11.992$ is near an integer,
which means that $\mathcal{T}^{31}$ is “almost” the identity map. During the
30 first steps, our map $\mathcal{T}$ is able to deceive us and pretend it
would tile the plane by using the degrees of freedom we have in the coding of
the reals. For $k=31$, this is not possible anymore.

It turns out that the exact same method can be used for the set of 12 tiles
obtained starting from the set by Culik, and removing one tile. It corresponds
to the same rotation, and we observe indeed the same behaviour: starting from
a configuration of all $2$, it is not possible to tile $31$ consecutive rows:

######  Theorem 2.

The set of 13 tiles by Culik is minimal aperiodic: if any tile is removed from
this set, it does not tile the plane anymore.

Note that the situation is still not well understood and we can consider
ourselves lucky to obtain the result: First, we have to execute the
transducers in the good direction: $\mathcal{T}^{\prime}\mathcal{T}^{-31}$ is
nonempty. Furthermore, the next step when $\mathcal{T}^{k}$ returns near an
integer is for $k=106$, and no computer, using our technique, has enough
memory to hope computing $\mathcal{T}^{106}$.

######  Conjecture 1.

Every aperiodic tileset obtained by the method of Kari is minimal aperiodic.

##  4 An aperiodic Wang set of 11 tiles - Proof Sketch

Using the same method presented in the last section, we were able to enumerate
and test sets of 11 tiles, and found a few potential candidates. Of these few
candidates, two of them were extremely promising and we will indeed prove that
they are aperiodic sets.

0123$1|0$$2|1$$2|2$$4|2$$2|3$$1|1$$1|1$$2|2$$3|1$$1|4$$0|2$

$0$$0$$0$$1$$0$$3$$1$$2$$1$$0$$2$$2$$1$$1$$2$$4$$1$$3$$3$$2$$3$$0$$1$$1$$3$$1$$1$$1$$3$$1$$2$$2$$3$$3$$1$$3$$2$$2$$4$$1$$2$$2$$2$$0$

Figure 3: Wang set $\mathcal{T}$.

0123$1|0$$2|1$$2|2$$0|2$$2|3$$1|1$$1|1$$2|2$$3|1$$1|0$$0|2$

$0$$0$$0$$1$$0$$3$$1$$2$$1$$0$$2$$2$$1$$1$$2$$0$$1$$3$$3$$2$$3$$0$$1$$1$$3$$1$$1$$1$$3$$1$$2$$2$$3$$3$$1$$3$$2$$2$$0$$1$$2$$2$$2$$0$

Figure 4: Wang set $\mathcal{T}^{\prime}$.

These sets of tiles are presented in Figure 3 and 4. Both sets are very
similar: the second one is obtained from the first one by collapsing the
colors 4 and 0.

We focus now on the first set.

$\mathcal{T}$ is the union of two Wang sets, $\mathcal{T}_{0}$ and
$\mathcal{T}_{1}$, of respectively 9 and 2 tiles. For
$w\in\\{0,1\\}^{*}\setminus\\{\epsilon\\}$, let
$\mathcal{T}_{w}={\mathcal{T}_{w[1]}\circ\mathcal{T}_{w[2]}\circ\ldots\mathcal{T}_{w[|w|]}}$.

It can be seen by a easy computer check that every tiling by $\mathcal{T}$ can
be decomposed into a tiling by transducers
$\mathcal{T}_{1}\mathcal{T}_{0}\mathcal{T}_{0}\mathcal{T}_{0}\mathcal{T}_{0}$
and $\mathcal{T}_{1}\mathcal{T}_{0}\mathcal{T}_{0}\mathcal{T}_{0}$.

Simplifications of these two transducers, called $\mathcal{T}_{a}$ and
$\mathcal{T}_{b}$ will be obtained in section 5.1 and are depicted in Fig. 5.

We then study the transducer $\mathcal{T}_{D}$ formed by the two transducers
$\mathcal{T}_{a}$ and $\mathcal{T}_{b}$ and prove that there exists a tiling
by $\mathcal{T}_{D}$, and that any tiling by $\mathcal{T}_{D}$ is aperiodic.

abcdefghij$1|0$$1|1$$1|1$$1|1$$1|0$$1|0$$1|1$$1|1$$0|0$$0|0$$0|0$$0|0$$0|0$$0|1$

KLMM’NOO’PQR$1|1$$1|1$$1|1$$0|0$$0|1$$0|1$$0|1$$0|0$$0|1$$0|0$$0|1$$0|1$$0|0$$1|1$

Figure 5: $\mathcal{T}_{D}$, the union of $\mathcal{T}_{a}$ (top) and
$\mathcal{T}_{b}$ (bottom).

We will prove that the tileset is aperiodic by proving that any tiling is
_substitutive_.

Let $u_{-2}=\epsilon$,$u_{-1}=a$, $u_{0}=b,u_{n+2}=u_{n}u_{n-1}u_{n}$.

Let $g(n)$, $n\in\mathbb{N}$ be $(n+1)$-th Fibonacci number, that is $g(0)=1$,
$g(1)=2$ and $g(n+2)=g(n)+g(n+1)$ for every $n\in\mathbb{N}$. Remark that
$u_{n}$ is of size $g(n)$.

$T_{n}$ for $n$ odd:

$1^{g(n+2)-3}|0^{g(n+2)-3}$$\begin{array}[]{l@{|}l}1^{g(n+1)+3}&(110)0^{g(n+1)}\\\
1^{g(n+3)+3}&0^{g(n+2)}(111)0^{g(n+1)}\\\
1^{g(n+1)}(000)1^{g(n+2)}&0^{g(n+3)+3}\\\ 1^{g(n+1)}(100)&0^{g(n+1)+3}\\\
1^{g(n+3)}(100)1^{g(n+1)}&0^{g(n+1)}(110)0^{g(n+3)}\end{array}$

$T_{n}$ for $n$ even:

$0^{g(n+2)-3}|1^{g(n+2)-3}$$\begin{array}[]{l@{|}l}0^{g(n+1)+3}&(100)1^{g(n+1)}\\\
0^{g(n+3)+3}&1^{g(n+2)}(000)1^{g(n+1)}\\\
0^{g(n+1)}(111)0^{g(n+2)}&1^{g(n+3)+3}\\\ 0^{g(n+1)}(110)&1^{g(n+1)+3}\\\
0^{g(n+3)}(110)0^{g(n+1)}&1^{g(n+1)}(100)1^{g(n+3)}\\\ \end{array}$

Figure 6: The family of transducers $T_{n}$

Then we will prove that, for all $n$, any tiling by $\mathcal{T}_{D}$ is a
tiling by $\mathcal{T}_{u_{n}},\mathcal{T}_{u_{n+1}},\mathcal{T}_{u_{n+2}}$.
(This is obvious by definition for $n=-2,-1$). For this, we now introduce a
family of transducers, presented in Fig 6, and we will prove

  * •

We prove (section 5.2) that every tiling by
$\mathcal{T}_{D}=\mathcal{T}_{a}\cup\mathcal{T}_{b}$ can be seen as a tiling
by
$\mathcal{T}_{u_{0}}\cup\mathcal{T}_{u_{1}}\cup\mathcal{T}_{u_{2}}=\mathcal{T}_{b}\cup\mathcal{T}_{aa}\cup\mathcal{T}_{bab}$.

  * •

We prove (section 5.2) that $\mathcal{T}_{u_{0}}$, $\mathcal{T}_{u_{1}}$ and
$\mathcal{T}_{u_{2}}$, when occuring in a tiling of the entire plane, can be
simplified to obtain the three transducers $T_{0},T_{1},T_{2}$.

  * •

We prove (section 6) that $T_{n+3}=T_{n+1}\circ T_{n}\circ T_{n+1}$ for all
$n$, which proves that $\mathcal{T}_{u_{n}}$ can be simplified to obtain
$T_{n}$

  * •

We then prove (section 7) that any tiling by
$\mathcal{T}_{u_{n}},\mathcal{T}_{u_{n+1}}$ and $\mathcal{T}_{u_{n+2}}$ can be
rewritten as a tiling by
$\mathcal{T}_{u_{n+1}},\mathcal{T}_{u_{n+2}},\mathcal{T}_{u_{n+3}}$, by
replacing any block
$\mathcal{T}_{u_{n+1}}\mathcal{T}_{u_{n}}\mathcal{T}_{u_{n+1}}$ by
$\mathcal{T}_{u_{n+3}}$ (the difficulty is to prove that by doing this, there
is no remaining occurence of $\mathcal{T}_{u_{n}}$).

  * •

This proves in particular that every tiling is aperiodic.

  * •

From the description of $T_{n}$, it is clear that the transducer $T_{n}$
(hence $\mathcal{T}_{u_{n}}$) is nonempty. This implies that there exists a
tiling of one row by $\mathcal{T}_{u_{n}}$, hence a tiling of $g(n)$
consecutive rows by $\mathcal{T}_{a}$ and $\mathcal{T}_{b}$, hence there
exists a tiling of a plane.

Finally, we explain in section 7 how the same proof gives us also the
aperiodicity of the set $\mathcal{T}^{\prime}$.

##  5 From $\mathcal{T}$ to $\mathcal{T}_{D}$ then to $T_{0},T_{1},T_{2}$

###  5.1 From $\mathcal{T}$ to $\mathcal{T}_{D}$

Recall that our Wang set $\mathcal{T}$ can be seen as the union of two Wang
sets, $\mathcal{T}_{0}$ and $\mathcal{T}_{1}$, of respectively 9 and 2 tiles.

For $w\in\\{0,1\\}^{*}\setminus\\{\epsilon\\}$, let
$\mathcal{T}_{w}={\mathcal{T}_{w[1]}\circ\mathcal{T}_{w[2]}\circ\ldots\mathcal{T}_{w[|w|]}}$.
The following facts can be easily checked by computer or by hand:

######  Fact 2.

The transducers $s({\mathcal{T}_{11}})$, $s({\mathcal{T}_{101}})$,
$s({\mathcal{T}_{1001}})$ and $s({\mathcal{T}_{00000}})$ are empty.

Thus, if $t$ is a tiling by $\mathcal{T}$, then there exists a bi-infinite
binary word $w\in\\{1000,10000\\}^{\mathbb{Z}}$ such that $t(x,y)\in
T(\mathcal{T}_{w[y]})$ for every $x,y\in\mathbb{Z}$. Let
$\mathcal{T}_{A}=s({\mathcal{T}_{1000}\cup\mathcal{T}_{10000}})$ (see Figure
7(a)). There is a bijection between the tilings by $\mathcal{T}$ and the
tilings by $\mathcal{T}_{A}$, and $\mathcal{T}$ is aperiodic if and only if
$\mathcal{T}_{A}$ is aperiodic.

2033021030210332110021103211132113021300213102131121330231002330023310$1|0$$1|1$$1|0$$1|1$$1|1$$1|0$$1|1$$1|1$$1|0$$1|0$$1|1$$1|2$$1|3$$1|1$$0|0$$0|0$$0|0$$0|0$$0|0$$0|0$$0|1$

203020332100210321102111211321302131213323002310231123302331$1|0$$1|1$$1|1$$1|1$$1|2$$1|3$$1|1$$1|1$$1|2$$1|3$$1|2$$0|0$$0|1$$0|0$$0|1$$0|1$$0|0$$0|1$$0|1$$0|0$$0|1$$0|1$$0|0$$0|1$$0|2$$0|3$$0|1$$0|2$$0|3$

(a) $\mathcal{T}_{A}$, the union of $s({\mathcal{T}_{10000}})$ (left) and
$s({\mathcal{T}_{1000}})$ (right).

203302103021033211032111321130213002131021330231002330023310$1|0$$1|1$$1|0$$1|1$$1|1$$1|1$$1|0$$1|0$$1|1$$1|1$$0|0$$0|0$$0|0$$0|0$$0|0$$0|0$$0|1$

203020332103211321302133230023102330$1|1$$1|1$$1|1$$0|0$$0|1$$0|0$$0|1$$0|1$$0|1$$0|0$$0|1$$0|0$$0|1$$0|1$

(b) $\mathcal{T}_{B}$ corresponds to $\mathcal{T}_{A}$ when unused transitions
are deleted.

abcdefghij$1|0$$1|1$$1|1$$1|1$$1|0$$1|0$$1|1$$1|1$$0|0$$0|0$$0|0$$0|0$$0|0$$0|1$

KLMNOPQR$1|1$$1|1$$1|1$$0|0$$0|1$$0|1$$0|1$$0|0$$0|1$$0|0$$0|1$$0|1$

(c) $\mathcal{T}_{C}$ is the simplification of $\mathcal{T}_{B}$ by
bisimulation.

abcdefghij$1|0$$1|1$$1|1$$1|1$$1|0$$1|0$$1|1$$1|1$$0|0$$0|0$$0|0$$0|0$$0|0$$0|1$

KLMM’NOO’PQR$1|1$$1|1$$1|1$$0|0$$0|1$$0|1$$0|1$$0|0$$0|1$$0|0$$0|1$$0|1$$0|0$$1|1$

(d) $\mathcal{T}_{D}$ is the simplification of $\mathcal{T}_{C}$ using the
fact that the successions of symbols $101$ and $010$ cannot appear. The
transducers to the left and to the right are called respectively
$\mathcal{T}_{a}$ and $\mathcal{T}_{b}$.

Figure 7: The different steps of simplification of $\mathcal{T}_{A}$.

We see that the transducer $\mathcal{T}_{A}$ never reads $2$, $3$ nor $4$.
Thus the transitions that write $2$, $3$ or $4$ are never used in a tiling by
$\mathcal{T}$. Let $\mathcal{T}_{B}$ (see Figure 7(b)) be the transducer
$\mathcal{T}_{A}$ after removing these unused transitions, and deleting states
that cannot appear in a tiling of a row (i.e. sources and sinks). Then $t$ is
a tiling by $\mathcal{T}_{A}$ if and only if $t$ is a tiling by
$\mathcal{T}_{B}$, and $\mathcal{T}_{B}$ is aperiodic if and only if
$\mathcal{T}_{A}$ is.

Now we simplify a bit the transducer $\mathcal{T}_{B}$ using bisimulation. The
states 23300 and 23310 have the same incoming transitions, hence can be
coalesced into one state The same goes for states 21300 and 21310, and for
states 2300 and 2310. Once we coalesce all those states, we obtain the Wang
set $\mathcal{T}_{C}$ depicted in Figure 7(c).

$\mathcal{T}_{B}$ and $\mathcal{T}_{C}$ are equivalent. Thus $\mathcal{T}_{B}$
is aperiodic if and only if $\mathcal{T}_{C}$ is aperiodic.

######  Proposition 1.

Let $(w_{i})_{i\in\mathbb{Z}}$ be a bi-infinite sequence of bi-infinite binary
words such that $w_{i}\mathcal{T}_{C}w_{i+1}$ for every $i\in\mathbb{Z}$. Then
for every $i\in\mathbb{Z}$, $w_{i}$ is $(010,101)$-free.

###### Proof.

We consider the tiling in the other direction, and look at the transducer
$({\mathcal{T}}^{\operatorname{tr}}_{C})^{3}$. This transducer has 8 states
(that corresponds respectively to $000$, $001$, …$111$) and a quick computer
check shows that in this transducer the states $010$ and $101$ are
respectively a source and a sink. As a consequence, these two states cannot
appear in a tiling of the plane by
$({\mathcal{T}}^{\operatorname{tr}}_{C})^{3}$, hence $101$ and $010$ cannot
appear in any line of a tiling by $\mathcal{T}_{C}$. ∎

In a tiling by $\mathcal{T}_{C}$, the transition from Q to O is never followed
by a transition from O to P, otherwise it writes a $101$. Similarly, a
transition from M to K is never preceded by a transition from L to M,
otherwise it reads a $010$. Thus there is a bijection between tilings by
$\mathcal{T}_{C}$ and tilings by $\mathcal{T}_{D}$ (Figure 7(d)).

###  5.2 From $\mathcal{T}_{D}$ to $T_{0},T_{1},T_{2}$

Let $\mathcal{T}_{a}$ and $\mathcal{T}_{b}$ be the two connected component of
$\mathcal{T}_{D}$. For a word $w\in\\{a,b\\}^{*}$, let
$\mathcal{T}_{w}={\mathcal{T}_{w[1]}\circ\mathcal{T}_{w[2]}\circ\ldots\mathcal{T}_{w[|w|]}}$.
The following fact can be easily checked by computer or by hand:

######  Fact 3.

The transducers $s({\mathcal{T}_{bb}})$, $s({\mathcal{T}_{aaa}})$ and
$s({\mathcal{T}_{babab}})$ are empty.

It is a classical exercise to show that this implies that if $t$ is a tiling
by $\mathcal{T}_{C}$ then there exists a bi-infinite binary word
$w\in\\{b,aa,bab\\}^{\mathbb{Z}}$ such that $t(x,y)\in T(\mathcal{T}_{w[y]})$
for every $y\in\mathbb{Z}$. That is, $t$ is image of a tiling by
$\mathcal{T}_{b}\cup\mathcal{T}_{aa}\cup\mathcal{T}_{bab}$.

We will now simplify the three transducers.

##### Case of $\mathcal{T}_{b}$.

In $\mathcal{T}_{b}$, every path eventually go to the state “N”. Thus
$\mathcal{T}_{b}$ is equivalent to the following transducer (written in a
compact form):

N$\small\begin{array}[]{l@{{}|{}}l}00000&10011\\\ 00000000&11100011\\\
00111000&11111111\\\ 00110&11111\\\ 0000011000&1110011111\\\ 0010&1011\\\
001000&111011\\\ 0000010&1110011\\\ 0011000&1011111\\\ \end{array}$

In the previous transducer, the last 4 transitions are never used in a tiling
of the plane, since they read 010 or write 101. So we can simplify the
transducer into:

N$\small\begin{array}[]{l@{{}|{}}l}00000&10011\\\ 00000000&11100011\\\
00111000&11111111\\\ 00110&11111\\\ 0000011000&1110011111\\\ \end{array}$

This transducer is equivalent to $T_{0}$, that we recall here for comparison:

$\epsilon|\epsilon$$\begin{array}[]{l@{|}l}0^{5}&(100)1^{2}\\\
0^{5+3}&1^{3}(000)1^{2}\\\ 0^{2}(111)0^{3}&1^{5+3}\\\ 0^{2}(110)&1^{2+3}\\\
0^{5}(110)0^{2}&1^{2}(100)1^{5}\\\ \end{array}$

bachcjdcebgb$111|000$$111|000$$11|11$$11|00$$1|0$$11111100|11000000$$1|0$$1111|0111$$0001|0000$$00|00$
(a) $s({\mathcal{T}_{aa}})$

LaOMbKMbRNeRNcLPbNQcORcO$1|1$$10|11$$000000011|001111111$$0000|1100$$00000|11111$$0|1$$0|0$$0|1$$000000|111111$$0|0$$0000|1111$$1100|1111$
(b) $s({\mathcal{T}_{bab}})$

Figure 8: $s({\mathcal{T}_{aa}})$ and $s({\mathcal{T}_{bab}})$.

##### Case of $\mathcal{T}_{aa}$.

The transducer $s({\mathcal{T}_{aa}})$ is depicted in Figure 8(a) in a compact
form. In this transducer, every path eventually go to the state “eb”. Then
$s({\mathcal{T}_{aa}})$ is equivalent to the following transducer (written in
a compact form):

eb$\small\begin{array}[]{l@{{}|{}}l}11111111&11000000\\\
1111111111111&0000011100000\\\ 1110001111111&0000000000000\\\
11110011&00000000\\\ 1111111110011111&0001100000000000\\\ \end{array}$

This transducer is clearly equivalent to $T_{1}$, that we recall for
convenience:

$1^{5-3}|0^{5-3}$$\begin{array}[]{l@{|}l}1^{3+3}&(110)0^{3}\\\
1^{8+3}&0^{5}(111)0^{3}\\\ 1^{3}(000)1^{5}&0^{8+3)}\\\ 1^{3}(100)&0^{3+3}\\\
1^{8}(100)1^{3}&0^{3}(110)0^{8}\end{array}$

##### Case of $\mathcal{T}_{bab}$.

The transducer $s({\mathcal{T}_{bab}})$ is depicted in Figure 8(b).

In this transducer, every path eventually go to the state “NeR”. Then
$s({\mathcal{T}_{bab}})$ is equivalent to the following transducer (wrote in a
compact form):

NeR$\small\begin{array}[]{l@{{}|{}}l}0000000000000&1111110011111\\\
000000000000000000000&111111111111100011111\\\
000000000011100000000&111111111111111111111\\\ 0000000000110&1111111111111\\\
00000000000000000011000000&11111111111001111111111111\\\ \end{array}$

This transducer is clearly equivalent to $T_{2}$, that we recall for the
reader convenience:

$0^{8-3}|1^{8-3}$$\begin{array}[]{l@{|}l}0^{5+3}&(100)1^{5}\\\
0^{13+3}&1^{8}(000)1^{5}\\\ 0^{5}(111)0^{8}&1^{13+3}\\\ 0^{5}(110)&1^{5+3}\\\
0^{13}(110)0^{5}&1^{5}(100)1^{13}\\\ \end{array}$

##  6 From $T_{n},T_{n+1},T_{n+2}$ to $T_{n+1},T_{n+2},T_{n+3}$

For the reader convenience, we recall the definition of the family of
transducers, and we introduce notations for the transitions $T_{n}$ for $n$
even:

$0$$5$$\alpha:0^{g(n+2)-3}|1^{g(n+2)-3}$$\begin{array}[]{l@{\,:\,}l@{|}l}\beta&0^{g(n+1)+3}&(100)1^{g(n+1)}\\\
\gamma&0^{g(n+3)+3}&1^{g(n+2)}(000)1^{g(n+1)}\\\
\delta&0^{g(n+1)}(111)0^{g(n+2)}&1^{g(n+3)+3}\\\
\epsilon&0^{g(n+1)}(110)&1^{g(n+1)+3}\\\
\gamma&0^{g(n+3)}(110)0^{g(n+1)}&1^{g(n+1)}(100)1^{g(n+3)}\\\ \end{array}$

$T_{n+1}$ for $n$ even:

$0$$5$$\mathbb{A}:1^{g(n+3)-3}|0^{g(n+3)-3}$$\begin{array}[]{l@{\,:\,}l@{|}l}\mathbb{B}&1^{g(n+2)+3}&(110)0^{g(n+2)}\\\
\mathbb{C}&1^{g(n+4)+3}&0^{g(n+3)}(111)0^{g(n+2)}\\\
\mathbb{D}&1^{g(n+2)}(000)1^{g(n+3)}&0^{g(n+4)+3}\\\
\mathbb{E}&1^{g(n+2)}(100)&0^{g(n+2)+3}\\\
\mathbb{O}&1^{g(n+4)}(100)1^{g(n+2)}&0^{g(n+2)}(110)0^{g(n+4)}\end{array}$

Before going into the proof, we first give some remarks.

  * •

$T_{n}$ for $n$ even and $n$ odd are essentially similar. This means it is
sufficient to prove that $T_{n+3}=T_{n+1}\circ T_{n}\circ T_{n+1}$ for $n$
even, and the result for $n$ odd follows.

  * •

Apply the following transformation to $T_{n}$: Change input and output, and
reverse the edges: reverse the direction and mirror (reverse) the words, and
exchange the symbols $0$ and $1$. Then we obtain $T_{n}$ again (for $n$ even,
with $\beta$ playing the role of $\epsilon$, $\delta$ the role of $\gamma$,
and $\alpha$ and $\omega$ their own role). This internal symmetry will be used
a lot in the proofs.

  * •

All transitions are symmetric and easy to understand, except the self-
symmetric tiles $\omega$ and $\mathbb{O}$. These transitions actually cannot
occur in the tiling of the plane, but a transition of shape $\omega$ or
$\mathbb{O}$ large enough can appear in a finite strip large enough. It means
it is not possible to do the proof without speaking about these transitions,
even if they cannot appear in a tiling of the plane.

We now proceed to prove the result. As said before, we now suppose that $n$ is
even, and we will look at the sequence of transducers $T_{n+1}\circ T_{n}\circ
T_{n+1}$.

The following table represent the possible distance between two consecutive
markers (i.e. 000 and 100) as inputs of $T_{n+1}$.

$\begin{array}[]{l|l|ll}\text{First Marker}&\text{Second
Marker}&\text{Distance}\\\ \hline\cr(000)\text{ from }D&(000)\text{ from
}D&g(n+5)&\rdelim\\}{9}{3.5cm}[$\begin{matrix}+ag(n+4) + bg(n+5)\\\ a,b
\in\mathbb{N} \end{matrix}$]\\\ (000)\text{ from }D&(100)\text{ from
}E&g(n+5)\\\ (000)\text{ from }D&(100)\text{ from }O&g(n+5)+g(n+3)\\\
(100)\text{ from }E&(000)\text{ from }D&g(n+4)\\\ (100)\text{ from
}E&(100)\text{ from }E&g(n+4)\\\ (100)\text{ from }E&(100)\text{ from
}O&g(n+5)\\\ (100)\text{ from }O&(000)\text{ from }D&g(n+4)+g(n+2)\\\
(100)\text{ from }O&(100)\text{ from }E&g(n+4)+g(n+2)\\\ (100)\text{ from
}O&(100)\text{ from }O&2g(n+4)\\\ \hline\cr\end{array}$

To prove the main result, we will prove that the transitions in the transducer
$T_{n}$ (when surrounded by transducers $T_{n+1}$) must be done in a certain
order.

In the following, we deliberately omit the transition $\alpha$: When we say
that $\gamma\beta$ cannot appear, we mean that it is impossible to see
successively the transitions $\gamma$, then $\alpha$, then $\beta$ in a run of
the transducer $T_{n}$ (when surrounded by transducers $T_{n+1}$).

######  Lemma 5.

The following words cannot appear:

  * •

$\gamma\omega$,$\gamma\gamma$,$\gamma\beta,\beta\omega,\beta\beta,\beta\epsilon\beta,\gamma\epsilon\beta$,
$\beta\delta\epsilon\beta$, $\gamma\delta\epsilon\beta$

  * •

$\omega\delta,\delta\delta,\epsilon\delta,\omega\epsilon,\epsilon\epsilon,\epsilon\beta\epsilon,\epsilon\beta\delta$,
$\epsilon\beta\gamma\epsilon$, $\epsilon\beta\gamma\delta$

###### Proof.

All the following successions of transitions are impossible due to the input
constraints on $T_{n+1}$ :

Case | Why it is impossible
---|---
$\gamma\omega$ | (000) and (100) separated by $g(n+1)+g(n+3)$
$\gamma\gamma$ | (000) and (000) separated by $g(n+4)$
$\gamma\beta$ | (000) and (100) separated by $g(n+3)$
$\beta\omega$ | (100) and (100) separated by $g(n+1)+g(n+3)$
$\beta\beta$ | (100) and (100) separated by $g(n+3)$
$\beta\epsilon\beta$ | (100) and (100) separated by $2g(n+3)$
$\gamma\epsilon\beta$ | (000) and (100) separated by $2g(n+3)$
$\beta\delta\epsilon\beta$ | (100) and (100) separated by $2g(n+4)+g(n+1)$
$\gamma\delta\epsilon\beta$ | (000) and (100) separated by $2g(n+4)+g(n+1)$

All others cases follow by symmetry. ∎

######  Lemma 6.

$\omega$ cannot appear.

###### Proof.

Case disjunction on what appears before:

Case | Why it is impossible
---|---
$\beta\omega$ | see above
$\gamma\omega$ | see above
$\beta\delta\omega$ | (100) and (100) separated by
| $g(n+4)+g(n+3)+g(n+1)$
$\gamma\delta\omega$ | (000) and (100) separated by
| $g(n+4)+g(n+3)+g(n+1)$
$\beta\epsilon\omega$ | (100) and (100) separated by
| $g(n+4)+2g(n+1)$
$\gamma\epsilon\omega$ | (000) and (100) separated by
| $g(n+4)+2g(n+1)$
$\beta\delta\epsilon\omega$ | (100), (100) separated by
| $g(n+5)+g(n+3)+g(n+1)=2g(n+4)+2g(n+1)$
$\gamma\delta\epsilon\omega$ | (000), (100) separated by
| $g(n+5)+g(n+3)+g(n+1)=2g(n+4)+2g(n+1)$

∎

######  Lemma 7.

$\mathbb{O}$ cannot appear.

###### Proof.

Suppose that $\mathbb{O}$ appear in the top transducer (i.e. the transducers
with input $T_{n}$). This means the $(100)$ marker is generated, the only
possibility being by $\beta$.

We prove there is no possibility to find transitions after this $\beta$.

Case | Why it is impossible starting from $\mathbb{O}$
---|---
$\beta\gamma$ | (100) and (000) separated by $g(n+4)$
$\beta\delta\beta$ | (100) and (100) separated by $g(n+4)+g(n+3)$
$\beta\delta\gamma$ | (100) and (000) separated by $g(n+4)+g(n+1)+g(n+3)$
$\beta\delta\epsilon\beta$ | (100) and (100) separated by $2g(n+4)+g(n+1)$
$\beta\delta\epsilon\gamma$ | (100) and (000) separated by $2g(n+4)+g(n+3)$
$\beta\epsilon\gamma$ | (100) and (000) separated by $g(n+5)$

By symmetry, $\mathbb{O}$ cannot appear in the bottom transducer. ∎

Now that $\mathbb{O}$ has disappeared, the possible distances between the
markers are greatly simplified

$\begin{array}[]{l|l|ll}\text{First Marker}&\text{Second
Marker}&\text{Distance}\\\
\hline\cr(000)&(000)&g(n+5)&\rdelim\\}{4}{4cm}[$\begin{matrix}+ag(n+4)+bg(n+5)
\\\ a,b\in\mathbb{N}\end{matrix}$]\\\ (000)&(100)&g(n+5)\\\
(100)&(000)&g(n+4)\\\ (100)&(100)&g(n+4)\\\ \hline\cr\end{array}$

######  Lemma 8.

The following words do not appear: $\beta\epsilon$, $\epsilon\beta$
$\beta\delta\beta$, $\delta\gamma\delta$, as well as $\epsilon\gamma\epsilon$
and $\gamma\delta\gamma$

###### Proof.

$\beta\epsilon$ should be followed by $\gamma$ which leads to $(100)$ and
$(000)$ separated by $g(n+5)$.

$\epsilon\beta$ should be preceded by a $\delta$, which cannot be preceded by
anything.

Case | Why it is impossible
---|---
$\beta\delta\beta$ |  $(100),(100)$ separated by $g(n+4)+g(n+3)$
$\gamma\delta\gamma$ |  $(000),(000)$ separated by $g(n+5)+g(n+2)$

The last two follow by symmetry.

∎

######  Lemma 9.

Every infinite path on the transducer $T_{n}$ can be written as paths on the
following graph:

$\gamma\delta$$\beta,\epsilon,\beta\delta\gamma\epsilon,\beta\gamma\epsilon,\beta\delta\epsilon$

###### Proof.

Clear: all other words are forbidden by the previous lemmas ∎

Recall that in this picture, words $\alpha$ have been forgotten. We now
rewrite it adding the transitions $\alpha$.

$\gamma\alpha\delta$$\alpha\beta\alpha,\alpha\epsilon\alpha,\alpha\beta\alpha\delta\alpha\gamma\alpha\epsilon\alpha,\alpha\beta\alpha\gamma\alpha\epsilon\alpha,\alpha\beta\alpha\delta\alpha\epsilon\alpha$

All transitions in the picture will be called _meta-transitions_.

We now have a more accurate description of the behaviour of the transducer
$T_{n}$ when surrounded by transducers $T_{n+1}$. This will be sufficient to
prove the results. We will see indeed that each of the six meta-transitions
depicted can be completed in only one way by transitions of $T_{n+1}$. This
will give us six tiles, which (almost) correspond to the transitions of
$T_{n+3}$.

We will use drawings to prove the result. Let first draw all tiles: The
pictures will be self-explanatory.

First, the transitions of $T_{n}$, seen as tiles:

$\alpha$$\beta$$\gamma$$\delta$$\epsilon$

Then the transitions of $T_{n+1}$:

$\mathbb{A}$$\mathbb{B}$$\mathbb{C}$$\mathbb{D}$$\mathbb{E}$

We now first look at $\gamma\delta$. By necessity, the following transitions
of $T_{n+1}$ should surround it:

$\gamma$$\alpha$$\delta$$\mathbb{A}$$\mathbb{C}$$\mathbb{D}$$\mathbb{A}$

Note that the three transducers are aligned (up to a a shift of $\pm 3$) when
$\gamma\alpha\delta$ is present. As all other meta-transitions are enclosed by
the meta-transition $\gamma\alpha\delta$, This means that in an execution of
$T_{n+1}\circ T_{n}\circ T_{n+1}$, every other meta-transition should be
surrounded above and below by transitions of $T_{n+1}$ that almost align with
it. Moreover the transitions of $T_{n+1}$ below should begin by $\mathbb{A}$
and the transitions of $T_{n+1}$ above should end with $\mathbb{A}$. It turns
out that there is only one way to do this for any of the meta-transitions.

This gives for $\epsilon$ and $\beta$:

$\alpha$$\epsilon$$\alpha$$\mathbb{A}$$\mathbb{B}$$\mathbb{B}$$\mathbb{A}$

$\alpha$$\beta$$\alpha$$\mathbb{A}$$\mathbb{E}$$\mathbb{E}$$\mathbb{A}$

This gives for $\beta\gamma\epsilon$ and $\beta\delta\epsilon$:

$\alpha$$\beta$$\alpha$$\delta$$\alpha$$\epsilon$$\alpha$$\mathbb{A}$$\mathbb{C}$$\mathbb{A}$$\mathbb{B}$$\mathbb{E}$$\mathbb{A}$$\mathbb{C}$$\mathbb{A}$

$\alpha$$\beta$$\alpha$$\gamma$$\alpha$$\epsilon$$\alpha$$\mathbb{A}$$\mathbb{D}$$\mathbb{A}$$\mathbb{B}$$\mathbb{E}$$\mathbb{A}$$\mathbb{D}$$\mathbb{A}$

And the piece de resistance $\beta\delta\gamma\epsilon$:

$\alpha$$\beta$$\alpha$$\delta$$\alpha$$\gamma$$\alpha$$\epsilon$$\alpha$$\mathbb{A}$$\mathbb{C}$$\mathbb{A}$$\mathbb{E}$$\mathbb{A}$$\mathbb{B}$$\mathbb{E}$$\mathbb{A}$$\mathbb{B}$$\mathbb{A}$$\mathbb{D}$$\mathbb{A}$

We now look at the transducer $T^{\prime}$ we obtain with the preceding six
pieces. Remark that $T^{\prime}=T_{n}\circ T_{n+1}\circ T_{n}\circ\sigma^{3}$
where $\sigma$ is the shift:

$1^{g(n+5)}|0^{g(n+5)}$$\begin{array}[]{l@{|}l}1^{g(n+4)}&(110)0^{g(n+4)-3}\\\
1^{g(n+4)-3}(100)&0^{g(n+4)}\\\ 1^{g(n+6)}&0^{g(n+5)}(111)0^{g(n+4)-3}\\\
1^{g(n+4)-3}(111)1^{g(n+5)}&0^{g(n+6)}\\\
1^{g(n+6)-3}(100)1^{g(n+4)}&0^{g(n+4)}(110)0^{g(n+6)-3}\\\ \end{array}$

It is easy to see that $T^{\prime}$ is exactly $T_{n+3}$ up to a shift of $3$.

######  Theorem 3.

$T_{n+3}=T_{n}\circ T_{n+1}\circ T_{n}$.

##  7 End of the proof

###  7.1 Aperiodicity of $\mathcal{T}$

######  Theorem 4.

Every infinite composition of the tranducers $T_{n},T_{n+1}$, $T_{n+2}$ can be
rewritten as a composition of transducers $T_{n+1},T_{n+2},T_{n+3}$ by
replacing every block $T_{n+1}\circ T_{n}\circ T_{n+1}$ by $T_{n+3}$. In
particular, every tiling by $T_{0},T_{1}$ and $T_{2}$ is aperiodic.

###### Proof.

It is easy to see, given the inputs of $T_{n},T_{n+1}$ and $T_{n+2}$, that
every $T_{n}$ should be bordered by the transducers $T_{n+1}$.

It therefore remains to show that $T_{n+1}\circ T_{n}\circ T_{n+1}\circ
T_{n}\circ T_{n+1}$ cannot appear.

By the previous section, $T_{n}$, when bordered by $T_{n+1}$ on both sides,
can be rewritten as concatenations of blocks of the following five types:
$\beta\gamma\delta$, $\epsilon\gamma\delta$,
$\beta\delta\gamma\epsilon\gamma\delta$, $\beta\gamma\epsilon\gamma\delta$ and
$\beta\delta\epsilon\gamma\delta$.

However, as $T_{n+1}\circ T_{n}\circ T_{n+1}\circ T_{n}\circ
T_{n+1}=T_{n+3}\circ T_{n}\circ T_{n+1}$, the block $\epsilon\gamma\delta$
(and any block containing it) cannot appear in the execution of the transducer
$T_{n}$is impossible, as $T_{n+3}$ does not produce any input that where $100$
and $000$ are that close. So the only block that remain possibly is
$\beta\gamma\delta$. But $T_{n+3}$ does not produce any input where $000$ and
$000$ are at distance $g(n+6)$. ∎

######  Corollary 1.

The Wang set corresponding to the transducer $T_{0}\cup T_{1}\cup T_{2}$ is
aperiodic

######  Corollary 2.

The Wang set $\mathcal{T}_{D}=\mathcal{T}_{a}\cup\mathcal{T}_{b}$ is
aperiodic. Furthermore, the set of words $u\in\\{a,b\\}^{\star}$ s.t. the
sequence of transducers $\mathcal{T}_{u}$ appear in a tiling of the plane is
exactly the set of factors of the Fibonacci word (_i.e._ the fixed point of
the morphism $a\to ab,b\to a$), i.e. the set of factors of sturmian words of
slope $1/\phi$, for $\phi$ the golden mean.

The set of biinfinite words $u\in\\{a,b\\}^{\mathbb{Z}}$ s.t $\mathcal{T}_{u}$
represents a valid tiling of the plane are exactly the sturmian words of slope
$1/\phi$.

See [BS02] for some references on sturmian words.

###### Proof.

The sequence of words $u_{n}$ we defined is the sequence of singular factors
of the Fibonacci word (see for example [WW94]). Thus, on tilings by
$\mathcal{T}_{a}\cup\mathcal{T}_{b}$, the vertical sequence on $\\{a,b\\}$
have the same set of factors that the Fibonacci word. ∎

######  Corollary 3.

The Wang set $\mathcal{T}$ is aperiodic. Furthermore, the set of words
$u\in\\{0,1\\}^{\star}$ s.t. the sequence of transducers $\mathcal{T}_{u}$
appear in a tiling of the plane is exactly the set of factors of sturmian
words of slope $\phi/(5\phi-1)$, for $\phi$ the golden mean.

The set of biinfinite words $u\in\\{0,1\\}^{\mathbb{Z}}$ s.t $\mathcal{T}_{u}$
represents a valid tiling of the plane are exactly the sturmian words of slope
$\phi/(5\phi-1)$.

###### Proof.

Let $\psi$ be the morphism $a\mapsto 10000,b\mapsto 1000$. The set of all
words $u\in\\{0,1\\}^{\mathbb{Z}}$ that can appear in a tiling of the whole
plane are exactly the image by $\psi$ of the sturmian words over the alphabet
$\\{a,b\\}$ of slope $1/\phi$.

It is well known that the image of a sturmian word by $\psi$ is again a
sturmian word, see [BS02, Corollary 2.2.19], where $\psi=\tilde{G}^{3}D$ (with
$\\{a,b\\}$ instead of $\\{0,1\\}$ as input alphabet). The derivation of the
slope is routine. ∎

###  7.2 Aperiodicity of $\mathcal{T}^{\prime}$

Recall that $\mathcal{T}^{\prime}$ is the Wang set from Figure 4. This Wang
set is obtained from $\mathcal{T}$, by merging two vertical colors: 0 and 4 in
$\mathcal{T}$ become 0 in $\mathcal{T}^{\prime}$. Thus every tiling of
$\mathcal{T}$ can be turned into a tiling of $\mathcal{T}^{\prime}$, and
$\mathcal{T}^{\prime}$ tiles the plane. We will show in the sequel that every
tiling of $\mathcal{T}^{\prime}$ can be turned into a tiling of $\mathcal{T}$,
and thus every tiling of $\mathcal{T}^{\prime}$ is aperiodic.

$\mathcal{T}^{\prime}$ is the union of two Wang sets
$\mathcal{T}^{\prime}_{0}$ and $\mathcal{T}^{\prime}_{1}$ of respectively 9
and 2 tiles. The following facts can be easily checked by computer. For
$w\in\\{0,1\\}^{*}\setminus\\{\epsilon\\}$, let
$\mathcal{T}^{\prime}_{w}={\mathcal{T}^{\prime}_{w[1]}\circ\mathcal{T}^{\prime}_{w[2]}\circ\ldots\mathcal{T}^{\prime}_{w[|w|]}}$.

######  Fact 4.

The transducers $s({\mathcal{T}^{\prime}_{111}})$,
$s({\mathcal{T}^{\prime}_{101}})$, $s({\mathcal{T}^{\prime}_{1001}})$,
$s({\mathcal{T}^{\prime}_{1000001}})$, $s({\mathcal{T}^{\prime}_{10000001}})$,
$s({\mathcal{T}^{\prime}_{100000001}})$,
$s({\mathcal{T}^{\prime}_{000000000}})$, $s({\mathcal{T}^{\prime}_{000011}})$,
$s({\mathcal{T}^{\prime}_{110000}})$ and $s({\mathcal{T}^{\prime}_{1100011}})$
are empty.

Thus, if $t$ is a tiling by $\mathcal{T}^{\prime}$ then there exists a bi-
infinite binary word $w\in\\{1000,10000,100011000,100000000\\}^{\mathbb{Z}}$
such that $t(x,y)\in T(\mathcal{T}^{\prime}_{w[y]})$ for every
$x,y\in\mathbb{Z}$.

Let
$\mathcal{T}^{\prime}_{A}=s({\mathcal{T}^{\prime}_{1000}\cup\mathcal{T}^{\prime}_{10000}\cup{\mathcal{T}^{\prime}_{100000000}\cup{\mathcal{T}^{\prime}_{100011000}}}})$.
As before, $\mathcal{T}^{\prime}_{A}$ has unused transitions (those which
writes $2$ or $3$). Once deleted, with states that cannot appear in a tiling
of a row, we obtain $\mathcal{T}^{\prime}_{B}$. $\mathcal{T}^{\prime}_{B}$ has
4 connected components: two were already present in $\mathcal{T}$:
$\mathcal{T}_{a}$ and $\mathcal{T}_{b}$, the third one $\mathcal{T}_{c}$ is a
subset of $\mathcal{T}^{\prime}_{100000000}$, and the last one
$\mathcal{T}_{d}$ is a subset of $\mathcal{T}^{\prime}_{100011000}$.

######  Proposition 2.

$\mathcal{T}^{\prime}_{11}$ is isomorphic to a subset of
$\mathcal{T}^{\prime}_{01}$, and $\mathcal{T}^{\prime}_{100000}$ is isomorphic
to a subset of $\mathcal{T}^{\prime}_{100001}$.

###### Proof.

$\mathcal{T}^{\prime}_{11}$ is the transducer with one state, which reads $1$
and writes $2$. $\mathcal{T}^{\prime}_{01}$ has also a loop that reads $1$ and
writes $2$: the transition $(02,02,1,2)$. $\mathcal{T}^{\prime}_{100000}$ and
$\mathcal{T}^{\prime}_{100001}$ are depicted in Figure 9 (in a compact form).
$\mathcal{T}^{\prime}_{100000}$ is isomorphic to the subset of
$\mathcal{T}^{\prime}_{100001}$ drawn in bold. ∎

210302210332211032211302213002213102213302$1|2$$1|0$$1|2$$1|0$$1|0$$1|2$$1|2$$1|0$$11|00$$000|222$$00|22$$00|20$
211301$100|222$$00011|22222$

Figure 9: $\mathcal{T}^{\prime}_{100001}$ (left) and
$\mathcal{T}^{\prime}_{100000}$ (right).

######  Corollary 4.

$\mathcal{T}_{c}$ and $\mathcal{T}_{d}$ are both isomorphic to a subset of
$\mathcal{T}_{a}\circ\mathcal{T}_{b}$.

A tiling of $\mathcal{T}^{\prime}_{B}$ can thus be turned into a tiling of
$\mathcal{T}_{B}$, by substituting every tile from $\mathcal{T}_{c}$ (resp.
$\mathcal{T}_{d}$) by two tiles, one from $\mathcal{T}_{a}$ and one from
$\mathcal{T}_{b}$.

######  Theorem 5.

The Wang set $\mathcal{T}^{\prime}$ is aperiodic.

###### Proof.

The Wang set $\mathcal{T}^{\prime}$ is aperiodic if and only if
$\mathcal{T}^{\prime}_{B}$ is aperiodic. Suppose that
$\mathcal{T}^{\prime}_{B}$ is not aperiodic. We know that
$\mathcal{T}^{\prime}$, and thus $\mathcal{T}^{\prime}_{B}$ tile the plane.
Take a periodic tiling by $\mathcal{T}^{\prime}_{B}$. This tiling can be
turned into a tiling of $\mathcal{T}_{B}$ by the Corollary 4. Thus
$\mathcal{T}_{B}$ has a periodic tiling, contradiction. ∎

###  7.3 Concluding remarks

  * •

The reader may regret that our substitutive system starts from
$\mathcal{T}_{b}\cup\mathcal{T}_{aa}\cup\mathcal{T}_{bab}$ and not from
$\mathcal{T}_{a}\cup\mathcal{T}_{b}\cup\mathcal{T}_{aa}$, or even from
$\mathcal{T}_{a}\cup\mathcal{T}_{b}$. We do not know if this is possible. Our
definition of $T_{n}$ certainly does not work for $n=-1$, and the natural
generalization of it is not equivalent to $\mathcal{T}_{a}$. This is somewhat
obvious, as $T_{n}$ (for $n\geq 0$) cannot be composed with itself, whereas
$\mathcal{T}_{a}$ should be composed with itself to obtain $\mathcal{T}_{aa}$.

  * •

$\mathcal{T}_{a}$ and $\mathcal{T}_{b}$ both have the properties that they are
time symmetric: If we reverse the directions of all edges, exchange inputs and
outputs, and exchange 0 and 1, we obtain an equivalent transducer (it is
obvious for $\mathcal{T}_{b}$ and become obvious for $\mathcal{T}_{a}$ if we
write it in a compact form without the states $h$ and $g$). This property was
used to simplify the proof that the sequence $(T_{n})$ is a recursive
sequence, but we do not know whether it can be used to simplify the whole
proof.

  * •

While we gave a sequence of transducers $T_{n}$, it is of course possible to
give another sequence of transducers, say $U_{n}$, which are equivalent to
$T_{n}$, and thus with the same properties. Our sequence $T_{n}$ has nice
properties, in particular the symmetry explained above and its short number of
transitions, but has the drawback that the substitution once seen
geometrically has small bumps due to the fact that the tiles are aligned only
up to $\pm 3$. It is possible to find a sequence $U_{n}$ for which this does
not appear, by splitting some transitions of $T_{n}$ into transitions of size
$g(k)$ and transitions of size exactly $3$. However this makes the proof that
the sequence is recursive harder. We think our sequence $T_{n}$ reaches a nice
compromise.

  * •

We do now know if it is possible to obtain the result directly on the original
tileset $\mathcal{T}$ rather than $\mathcal{T}_{D}$. A difficulty is that
$\mathcal{T}$ is not purely substitutive (due for example to the fact that no
sturmian word of slope $\phi/(5\phi-1)$ is purely morphic): What we could
obtain at best is that tilings by $\mathcal{T}$ are images by some map $\phi$
of some substitutive tilings (which is more or less what we obtain in our
proof).

  * •

We have now obtained a large number of Wang sets with 11 tiles which are
candidates for aperiodicity. The reader might ask why we choose to investigate
this particular one. The reason is that, for this particular tileset
$\mathcal{T}$, it is very easy for a computer to produce the transducer for
$\mathcal{T}^{k}$ even for large values of $k$ ($k=1000$). For comparison, for
almost all other tilesets, we were not able to reach even $k=30$. This
suggested this tileset had some particular structure. We will not give here a
full bestiary of all our candidates, but we will say that a large number of
them are tileset corresponding to the method of Kari, with one tile or more
omitted. With the method we described previously we were able to prove that
some of them do not tile the plane, but the method did not work on all of
them. We have found for now only three tilesets which were likely to be
substitutive or nearly substitutive, of which two are presented in this
article.

  * •

Experimental results tend to support the following conjecture

######  Conjecture 2.

Let $f(n)$ be the smallest $k$ s.t. every Wang set of size $n$ that does not
tile the plane does not tile a square of size $k$. Let $g(n)$ be the smallest
$k$ s.t. every Wang set of size $n$ that tiles the plane periodically does so
with a period $p\leq k$.

Then $g(n)\leq f(n)$ for all $n$.

0

0

0

000000000000000

000000000000000

0000000000000000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Figure 10: Representation of the meta-tile $\gamma$ (resp. $C$ if $n$ is odd)
of $T_{n}$ as tiles of $T_{0}\uplus T_{1}\uplus T_{2}$ for
$n=0,1,2,3,4,5,6,7$.

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Figure 11: A fragment of a tiling by the transducers $T_{0},T_{1},T_{2}$.

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Figure 12: A fragment of a tiling by $\mathcal{T}^{\prime}$, with
(0,1,2,3)=(white,red,blue,green).

## References

  * [AD01] Cyril Allauzen and Bruno Durand.  Tiling Problems.  In The Classical Decision Problem, Perspectives in Mathematical Logic, chapter A, pages 407–420. Springer, 2001.
  * [AL74] Stål Olav Aanderaa and Harry R. Lewis.  Linear Sampling and the $\forall\exists\forall$ Case of the Decision Problem.  Journal of Symbolic Logic, 39(3):519–548, September 1974.  See also [Lew79].
  * [Ber64] Robert Berger.  The Undecidability of the Domino Problem.  PhD thesis, Harvard University, 1964.
  * [Ber66] Robert Berger.  The Undecidability of the Domino Problem.  Number 66 in Memoirs of the American Mathematical Society. The American Mathematical Society, 1966.
  * [bie03] Reducing NFAs by invariant equivalences.  Lucian Ilie and Sheng Yu.  Theoretical Computer Science, 306:373–390, 2003.
  * [BS02] Jean Berstel and Patrice Séébold.  Sturmian Words.  In Algebraic Combinatorics on Words, chapter 2, pages 40–97. Cambridge University Press, 2002.
  * [CHLL14] Hung-Hsun Chen, Wen-Guei Hu, De-Jan Lai, and Song-Sun Lin.  Nonemptiness problems of Wang tiles with three colors.  Theoretical Computer Science, 547:34–45, August 2014.
  * [Cul96] Karel Culik II.  An aperiodic set of 13 Wang tiles.  Discrete Mathematics, 160:245–251, 1996.
  * [DLS04] Bruno Durand, Leonid A. Levin, and Alexander Shen.  Local rules and global order, or aperiodic tilings.  Mathematical Intelligencer, 27(1):64–68, 2004.
  * [DRS12] Bruno Durand, Andrei Romashchenko, and Alexander Shen.  Fixed-point tile sets and their applications.  Journal of Computer and System Sciences, 78(3):731–764, May 2012\.
  * [DSR08] Bruno Durand, Alexander Shen, and Andrei Romashchenko.  Fixed Point and Aperiodic Tilings.  Technical Report TR08-030, ECCC, 2008.
  * [FGS12] Antoine Julien Franz Gähler and Jean Savinien.  Combinatorics and Topology of the Robinson tiling.  Comptes Rendus de l’Académie des Sciences de Paris, Série I - Mathématiques, pages 627–631, 2012.
  * [FO10] Thomas Fernique and Nicolas Ollinger.  Combinatorial Substitutions and Sofic Tilings .  In Journées Automates Cellulaires (JAC), TUCS, pages 100–110, 2010\.
  * [GS87] Branko Grunbaum and G.C. Shephard.  Tilings and Patterns.  W.H. Freeman, 1987.
  * [GS98] Chaim Goodman-Strauss.  Matching Rules and Substitution Tilings.  Annals of Mathematics, 147(1):181–223, 1998.
  * [Her70] Hans Hermes.  Entscheidungsproblem und Dominospiele.  In Selecta Mathematica II. Springer, 1970.
  * [Her71] Hans Hermes.  A simplified proof for the unsolvability of the decision problem in the case $\wedge\vee\wedge$.  In Logic Colloquium 1969, volume 61 of Studies in Logic and the Foundations of Mathematics, pages 307–310, 1971.
  * [Hop71] John E. Hopcroft.  An $n\log n$ algorithm for minimizing states in a finite automaton.  Technical Report STAN-CS-71-190, Stanford university, computer science department, January 1971.
  * [JM97] Aimee Johnson and Kathleen Madden.  Putting the Pieces Together: Understanding Robinson’s Nonperiodic Tilings.  The College Mathematics Journal, 28(3):172–181, May 1997.
  * [JR12] Emmanuel Jeandel and Nicolas Rolin.  Fixed parameter undecidability for wang tilesets.  In Symposium on Cellular Automata (JAC), pages 69–85, 2012.
  * [Kar92] Jarkko Kari.  The Nilpotency Problem of One-Dimensional Cellular Automata.  SIAM Journal on Computing, 21(3):571–586, 1992.
  * [Kar96] Jarkko Kari.  A small aperiodic set of Wang tiles.  Discrete Mathematics, 160:259–264, 1996.
  * [KMW62] A.S. Kahr, Edward F. Moore, and Hao Wang.  Entscheidungsproblem reduced to the $\forall\exists\forall$ case.  Proceedings of the National Academy of Sciences of the United States of America, 48(3):365–377, March 1962.
  * [Knu68] Donald E. Knuth.  Fundamental Algorithms, volume 1 of The Art of Computer Programming, section 2.3.4.3 The infinity lemma, pages 382–385.  Addison-Wesley, first edition, 1968.
  * [KP99] Jarkko Kari and P. Papasoglu.  Deterministic Aperiodic Tile Sets.  Geometric And Functional Analysis, 9:353–369, 1999.
  * [KS90] Paris C. Kanellakis and Scott A. Smolka.  CCS Expressions, Finite State Processes and Three Problems of Equivalence.  Information and Computation, 86:43–68, 1990.
  * [Lev05] Leonid A. Levin.  Aperiodic Tilings: Breaking Translational Symmetry.  The Computer Journal, 48(6):642–645, 2005.
  * [Lew79] Harry R. Lewis.  Unsolvable Classes of Quantificational Formulas.  Addison-Wesley, 1979.
  * [lGO12] Bastien le Gloannec and Nicolas Ollinger.  Substitutions and Strongly Deterministic Tilesets.  In Computability in Europe (CiE), number 7318 in Lecture Notes in Computer Science, pages 462–471. Springer, 2012.
  * [Luk09] Ville Lukkarila.  The 4-way deterministic tiling problem is undecidable.  Theoretical Computer Science, 410:1516–1533, 2009.
  * [Moz89] Shahar Mozes.  Tilings, substitutions systems and dynamical systems generated by them.  J. d’Analyse Math., 53:139–186, 1989.
  * [Oll08] Nicolas Ollinger.  Two-by-Two Substitution Systems and the Undecidability of the Domino Problem.  In CiE 2008, number 5028 in Lecture Notes in Computer Science, pages 476–485, 2008.
  * [Poi80] Bruno Poizat.  Une théorie finiement axiomatisable et superstable.  Groupe d’études de théories stables, 3:1–9, 1980.
  * [Pou10] Victor Poupet.  Yet Another Aperiodic Tile Set .  In Journées Automates Cellulaires (JAC), TUCS, pages 191–202, 2010\.
  * [PT87] Robert Paige and Robert E. Tarjan.  Three Partition Refinement Algorithms.  SIAM Journal on Computing, 16(6):973–989, December 1987.
  * [Rob71] Raphael M. Robinson.  Undecidability and Nonperiodicity for Tilings of the Plane.  Inventiones Mathematicae, 12(3):177–209, 1971.
  * [Sal89] Olivier Salon.  Quelles tuiles! (Pavages apériodiques du plan et automates bidimensionnels).  Journal de Théorie des Nombres de Bordeaux, 1(1):1–26, 1989\.
  * [Sen95] Marjorie Senechal.  Quasicrystals and geometry.  Cambridge University Press, 1995.
  * [Val10] Antti Valmari.  Simple Bisimilarity Minimization in O($m\log n)$ Time.  Fundamenta Informaticae, 105:319–339, 2010.
  * [Wan61] Hao Wang.  Proving theorems by Pattern Recognition II.  Bell Systems technical journal, 40:1–41, 1961.
  * [Wan75] Hao Wang.  Notes on a class of tiling problems.  Fundamenta Mathematicae, 82:295–305, 1975.
  * [WW94] Zhi-Xiong Wen and Zhi-Ying Wen.  Some Properties of the Singular Words of the Fibonacci Word.  European Journal of Combinatorics, 15(6):587–598, November 1994\.