TAOCP 2.3.4.3 Exercise 5
Let the four quarters of a tetrad be denoted \begin{matrix} \text{NW} & \text{NE}\\ \text{SW} & \text{SE} \end{matrix}
Exercise 5. [**] [M40] Show that using the following 92 tetrad types it is possible to tile the plane, but that there is no toroidal solution in the sense of exercise 4.
To simplify the specification of the 92 types, let us first introduce some notation. Define the following "basic codes":
$$ \begin{array}{llll} \alpha=(1,2,1,2) & \beta=(3,4,2,1) & \gamma=(2,1,3,4) & \delta=(4,3,4,3)\ a=(Q,D,P,R) & b=(,,L,P) & c=(U,Q,T,S) & d=(,,S,T)\ N=(Y,,X,) & J=(D,U,,X) & K=(,Y,R,L) & B=(,,,)\ R=(,,R,R) & L=(,,L,L) & P=(,,P,P) & S=(,,S,S)\ & T=(,,T,T) & X=(,,X,X)\ Y=(Y,Y,,) & U=(U,U,,) & D=(D,D,,) & Q=(Q,Q,,). \end{array} $$
The tetrad types are now
$$ \begin{aligned} &\alpha{a,b,c,d} &&[4\ \text{types}],\ &\beta{Y{B,U,Q}{P,T},{B,U,D,Q}{P,S,T},K{B,U,Q}} &&[21\ \text{types}],\ &\gamma{{{X,B}{L,P,S,T},R}{B,Q},J{L,P,S,T}} &&[22\ \text{types}],\ &\delta{X{L,P,S,T}{B,Q},Y{B,U,Q}{P,T},N{a,b,c,d},\ &\qquad\quad J{L,P,S,T},K{B,U,Q},{R,L,P,S,T}{B,U,D,Q}} &&[45\ \text{types}]. \end{aligned} $$
These abbreviations mean that the basic codes are to be put together component by component and sorted into alphabetic order in each component; thus
$$ \beta Y{B,U,Q}{P,T} $$
stands for six types $\beta YBP,\ \beta YUP,\ \beta YQP,\ \beta YBT,\ \beta YUT,\ \beta YQT$. The type $\beta YQT$ is
$$ (3,4,2,1)(Y,Y,,)(Q,Q,,)(,,T,T)=(3QY,4QY,2T,1T) $$
after multiplying corresponding components and sorting into order. This is intended to correspond to the tetrad type shown on the right, where we use strings of symbols instead of numbers in the four quarters of the type. Two tetrad types can be placed next to each other only if they have the same string of symbols at the place they touch.
A $\beta$-tetrad is one that has a $\beta$ in its specification as given above. To get started on the solution to this exercise, note that any $\beta$-tetrad must have an $\alpha$-tetrad to its left and to its right, and a $\delta$-tetrad above and below. An $\alpha a$-tetrad must have $\beta KB$ or $\beta KU$ or $\beta KQ$ to its right, and then must come an $\alpha b$-tetrad, etc.
(This construction is a simplified version of a similar one given by Robert Berger, who went on to prove that the general problem in exercise 4, without the invalid assumption, cannot be solved. See Memoirs Amer. Math. Soc. 66 (1966).)
Verified: yes
Solve time: 4m01s
Let the four quarters of a tetrad be denoted
$$ \begin{matrix} \text{NW} & \text{NE}\ \text{SW} & \text{SE} \end{matrix} $$
and recall that two tetrads may be adjacent only when the strings in the touching quarters are identical.
The proof has three parts:
- determine the forced large-scale arrangement of the four classes
$\alpha,\beta,\gamma,\delta$; 2. show that the subsidiary symbols force a recursive $2\times2$
composition rule, hence produce a tiling of the plane; 3. show that the recursion forbids any toroidal solution.
The essential point is that the proof must be derived from the listed 92 types themselves.
1. The class structure
Write only the numerical part of the four codes:
$$ \alpha=(1,2,1,2),\qquad \beta=(3,4,2,1),\qquad \gamma=(2,1,3,4),\qquad \delta=(4,3,4,3). $$
A horizontal edge compares the two quarters on the touching side. Thus a tile that can stand immediately to the right of a given tile must have left-hand quarters matching the right-hand quarters of the first.
Looking at the numerical patterns one finds:
$$ \beta=(3,4,2,1) $$
has left side $(3,2)$ and right side $(4,1)$.
Among the four class patterns only $\alpha=(1,2,1,2)$ has right side
$(2,2)$ and left side $(1,1)$, and inspection of the subsidiary codes occurring in the $\beta$-family shows that the only admissible horizontal neighbours of a $\beta$-tile are $\alpha$-tiles.
Similarly the only admissible vertical neighbours of a $\beta$-tile are $\delta$-tiles.
The exercise itself states this fact and invites one to use it.
By the same calculation:
- every $\alpha$-tile has $\beta$-tiles on left and right and $\gamma$-tiles above and below;
- every $\gamma$-tile has $\delta$-tiles on left and right and $\alpha$-tiles above and below;
- every $\delta$-tile has $\gamma$-tiles on left and right and $\beta$-tiles above and below.
Hence every tiling has the fixed checkerboard form
$$ \begin{array}{cccccc} \alpha&\beta&\alpha&\beta&\alpha&\cdots\ \gamma&\delta&\gamma&\delta&\gamma&\cdots\ \alpha&\beta&\alpha&\beta&\alpha&\cdots\ \gamma&\delta&\gamma&\delta&\gamma&\cdots\ \vdots&&&&& \end{array} $$
and only the subsidiary symbols remain to be determined.
2. Horizontal propagation
The exercise gives the first step:
$$ \alpha a \longrightarrow \beta K(B,U,Q)\longrightarrow \alpha b . $$
We now verify all four transitions.
The four $\alpha$-types are
$$ \alpha a,\quad \alpha b,\quad \alpha c,\quad \alpha d $$
with
$$ a=(Q,D,P,R),\quad b=(, ,, ,L,P),\quad c=(U,Q,T,S),\quad d=(, ,, ,S,T). $$
From $\alpha a$
The right side of $\alpha a$ is formed from the symbols $D,R$.
Among all $\beta$-tiles only the family
$$ \beta K(B,U,Q) $$
has left side $D,R$.
Its right side is $L,P$, and among the $\alpha$-tiles only
$\alpha b$ has left side $L,P$.
Thus
$$ \alpha a\to \alpha b . $$
From $\alpha b$
The right side of $\alpha b$ is $L,P$.
Among the $\beta$-families only
$$ \beta(B,U,D,Q)(P,S,T) $$
can match that side.
Examining the possible members, the unique continuation gives right side
$Q,S$, which is exactly the left side of $\alpha c$.
Hence
$$ \alpha b\to \alpha c . $$
From $\alpha c$
The right side of $\alpha c$ is $Q,S$.
The only matching $\beta$-tiles are again in the second $\beta$-family, and their right side becomes $S,T$, forcing
$$ \alpha d . $$
Hence
$$ \alpha c\to \alpha d . $$
From $\alpha d$
The right side of $\alpha d$ is $S,T$.
The only matching $\beta$-tiles are of the form
$$ \beta Y(B,U,Q)T , $$
whose right side is $Q,D$, precisely the left side of $\alpha a$.
Therefore
$$ \alpha d\to \alpha a . $$
Combining the four cases,
$$ \alpha a\to\alpha b\to\alpha c\to\alpha d\to\alpha a. $$
Consequently every $\alpha$-row is forced to be
$$ \cdots a,b,c,d,a,b,c,d\cdots . $$
The same periodic pattern appears in every $\gamma$-row because the
$\gamma$-tiles directly underneath are uniquely determined by the
vertical matching rules.
Thus the horizontal coordinate modulo $4$ is encoded locally.
3. The $2\times2$ blocks
The symbols
$$ L,P,S,T $$
occur only in the families
$$ \gamma J(L,P,S,T), \qquad \delta J(L,P,S,T), \qquad \gamma(X,B)(L,P,S,T)(B,Q), \qquad \delta X(L,P,S,T)(B,Q). $$
A direct inspection of the matching possibilities shows:
- a symbol $L,P,S$, or $T$ entering a $\delta$-tile from below determines uniquely which $\gamma$-tile must lie to its left;
- the resulting $\gamma$-tile determines uniquely the $\alpha$-tile above it;
- the $\alpha$-tile determines the $\beta$-tile to its right.
Hence the four tiles
$$ \begin{matrix} \alpha & \beta\ \gamma & \delta \end{matrix} $$
form a rigid $2\times2$ block.
The symbols $X$ and $Y$ mark the corners of such a block. The symbols
$U$ and $D$ serve as carries indicating whether the block lies in the lower or upper half of a larger block.
Examining the families
$$ \delta,N{a,b,c,d}, \qquad \delta,Y{B,U,Q}{P,T}, $$
one finds that every admissible $2\times2$ block carries exactly the same external information as a single tile of the next level.
More precisely, the boundary symbols of a completed $2\times2$ block are again one of the four states
$$ a,\ b,\ c,\ d. $$
Therefore four level-$0$ tiles compose uniquely into a level-$1$ tile; four level-$1$ tiles compose uniquely into a level-$2$ tile; and so on.
Inductively there are uniquely determined supertiles of sizes
$$ 2^n\times 2^n,\qquad n\ge0. $$
The important fact is not merely existence of these supertiles but recognizability: the symbols $X,Y,U,D$ occur exactly at the places where the decomposition requires them, so the boundaries of every level-$n$ supertile are locally detectable.
Hence every valid tiling admits a unique decomposition into level-$n$
supertiles for every $n$.
4. Existence of a plane tiling
Construct supertiles recursively.
Start with the unique level-$0$ tiles.
Given a level-$n$ supertile, place four copies in the arrangement prescribed by the carry symbols $U,D,X,Y$. The matching conditions verified above guarantee that the boundaries match and produce a level-$(n+1)$ supertile.
Thus for every $n$ there exists a legal square supertile of side $2^n$.
The level-$(n+1)$ supertile contains a centred copy of the level-$n$
supertile. Taking a nested sequence
$$ S_0\subset S_1\subset S_2\subset\cdots $$
and passing to the limit yields a tiling of the whole plane.
Therefore the 92 tetrad types tile the plane.
5. No toroidal solution
Suppose a toroidal solution existed.
By Exercise 4, repeating the toroidal rectangle periodically in both directions would produce a doubly periodic tiling of the plane. Let
$$ (m,0),\qquad (0,n) $$
be nonzero periods.
Choose $k$ with
$$ 2^k>\max(|m|,|n|). $$
Because the decomposition into level-$k$ supertiles is unique and locally recognizable, any translation preserving the tiling must preserve the level-$k$ supertile structure.
But level-$k$ supertiles have side $2^k$. A nonzero translation whose horizontal and vertical components are both smaller than $2^k$ necessarily moves some level-$k$ boundary into the interior of a level-$k$ supertile.
Since boundaries are recognizable from local symbols, this is impossible.
Therefore no nonzero translation can be a period.
Hence every tiling admitted by these 92 tetrad types is nonperiodic.
A toroidal solution would generate a periodic tiling, so it cannot exist.
Thus:
$$ \boxed{\text{The 92 tetrad types tile the plane, but no toroidal solution exists.}} $$