Given a set of tiles, can you use them to cover the entire plane without any overlaps? The attempt to answer this question led to the discovery of various tilings exhibiting intricate structures, such as the Wang tilings, the Penrose tilings, and the Socolar–Taylor tiling. In this talk, I will try to eliminate these beautiful tilings and make everything periodic and orderly.
This is a talk given on October 2nd, 2018, for the Harvard Math Table. I’ve been meaning to write a post on this subject, since I have been working on this problem for quite a long time now, but I never had a chance.
1. Aperiodic tilings#
What are tilings? Imagine you’re an architect, and suppose you want to build your own bathroom. I’m not an architect, so I googled "how to build a bathroom", and there was this webpage with a \( 12 \)-step instruction. And three of the steps were "tile the floor", "tile the shower", "tile the backsplash". Apparently, if you tile the floor and walls with ceramic tiles, they becomes more water-resistant, durable, and also attract less dust. So even if you don’t want to follow the instructions, it’s probably a good idea to tile.
There are some obvious restrictions to your plan. You don’t want there to be any part of the floor that is not covered by the tiles, and of course two tiles cannot have an overlap. Maybe you also want that there are only finitely many shapes a tile can take, to make the manufacturing process easier. We can try and formulate this as a mathematical problem.
Definition 1. A tiling of \( \mathbb{R}^2 \) is a way of covering the entire plane without overlaps by
- a finite set \( S = \{ V _ 1, \ldots, V _ n \} \) of shapes,
- and allowing translations and rotations and reflections.
More generally, we can speak of tilings of \( \mathbb{R}^d \) for any dimension \( d \).
Example 1. Here is a rather uninteresting example. Take \( S = \{ \square \} \) to be just one square shape. There is the tiling that looks like an infinite grid. This is what Harvard does to our bathrooms, and I think everyone will agree that it looks pretty bad.
This inspired mathematicians to look for tilings with more interesting configurations, probably because they wanted their bathrooms to look nice. Here is one possible mathematical definition of "interesting" and "nice".
Definition 2. A tiling is called periodic if there is a finite region of the tiling that keeps repeating in a periodic manner over the entire space \( \mathbb{R}^d \). (More precisely, a tiling is periodic if there is a full rank lattice in \( \mathbb{R}^d \) consisting of translational symmetries of the tiling.) If a tiling is not periodic, it is called aperiodic.
Here is one way to obtain interesting tilings from simple shapes. You start with the standard square tile \( \square \), but on some of the sides, you make some dent, like a jigsaw puzzle. You can think of this as a rule for how some sides should match, and they are called matching rules.
Example 2. Here is one example of a tile with matching rules:
If we don’t allow reflections (we can impose this condition by taking slightly more complicated matching rules), then you will see that there is essentially one way of tiling the plane by this tile. But this tiling is still periodic, with period \( 2 \) in both the \( x \) and the \( y \) direction.
Logician Hao Wang was the first to study the tilings of squares with matching rules.
Definition 3. A Wang tiling is a tiling of \( \mathbb{R}^2 \) by
- a finite set \( S = \{V _ 1, \ldots, V _ n\} \), each of which is a square with matching rules,
- allowing translations and rotations and reflections.
Wang conjectured that aperiodic Wang tilings do not exist, that all Wang tilings are going to be periodic. But this was disproved by one of his students, Robert Berger!
Theorem 4 (Berger, 1966). The problem of "determining whether a finite set of Wang tiles do tile the plane" is undecidable. (There is no Turing machine that can solve this problem.) As a consequence, there exists a set of Wang tiles that only tile the plane aperiodically.
This is really interesting, because it is saying that a finite set of simple rules can generate an aperiodic structure. But there are a bit too many tiles involved. Bergner’s original set had over \( 20,000 \) tiles. People worked on reducing this number, and in 2015 Jeandel and Rao found a set, which has \( 11 \) tiles shown in Figure 1.
Figure 1. Jeandel and Rao's aperiodic Wang tiles: colors depict the matching rules, where edges are matched if and only if they have the same color and the opposite orientation
But can we reduce the number of tiles, if we allow tiles that are not "squares with matching rules", and also allow rotations? The answer is yes! There is a very famous example due to Roger Penrose, called the Penrose tilings.
Theorem 5 (Penrose tiling 3). There exists
- a set \( S = \{ V _ 1, V _ 2 \} \), where \( V _ 1 \) is a rhombus with angles \( 36^\circ, 144^\circ \) and \( V _ 2 \) is a rhombus with angles \( 72^\circ, 108^\circ \), both with matching rules,
that tile \( \mathbb{R}^2 \) only aperiodically, when
- allowing translations and rotations and reflections.
The tiles and a finite portion of a tiling can be found in Figure 1.
Figure 2. Penrose tiling by rhombuses with matching rules
So if there are two tiles, it is possible that they tile the plane only aperiodically. Can we be more extreme, and ask the same question for a single tile? This is called the einstein problem, not because Einstein worked on this problem but because "ein stein" is German for "one tile". This question was resolved by Socolar and Taylor in the affirmative, quite recently.
Theorem 6 (Socolar–Taylor, 2010). There exists
- a single tile \( S = \{ V _ 1 \} \), which is a hexagon with extended matching rules,
that tiles \( \mathbb{R}^2 \) only aperiodically, when
- allowing translations and rotations and reflections.
The tile and a finite portion of a tiling can be found in Figure 1.
Figure 3. The Socolar–Taylor tile and its tiling
Unfortunately, the Socolar–Taylor tile is not connected, which is a bit annoying for architects. In three or more dimensions, the tile can be made connected, but in two dimensions, we don’t know the answer to the einstein problem for connected tiles.
Is there a connected tile in \( \mathbb{R}^2 \) that tiles the plane only aperiodically, where translations and rotations and reflections are allowed?
2. Translational tilings#
So we have seen all these beautiful examples of aperiodic tilings. The way this subject progressed was, somebody comes up with an aperiodic set of tiles, and then somebody asks if there can be an aperiodic set of tiles with further restrictions. We can to describe this as "searching for simpler patterns that generate aperiodicity", and we can also call it "trying to eliminate aperiodicity". So far, leading to the einstein problem, our attention was only on reducing the number of tiles. But what will happen if we restricted our attention to tilings made out of only translations?
Definition 7. A translational tiling of \( \mathbb{R}^2 \) is a way of covering the entire plane without overlaps by
- a finite set \( S = \{ V _ 1, \ldots, V _ n \} \) of shapes,
- and allowing only translations.
More generally, we can speak of translational tilings of \( \mathbb{R}^d \) for any dimension \( d \).
Actually, all the tilings we saw above can be thought of as translational tilings, because we can simply set \( S \) to be the set of tiles with all possible rotations and reflections. But if we are interested in the number of tiles in this setting, there is a big difference between tilings and translational tilings.
So what question can we ask in the context of translational tilings? Here is the direct analogue of the einstein problem.
There does not exist a single tile \( S = \{V\} \) that translationally tiles \( \mathbb{R}^n \) only aperiodically.
Unlike the einstein problem, the answer to this question is wildly unknown. Here are some partial results:
- (Venkov, 1954) The conjecture is true if \( V \) is a convex polyhedron.
- (Girault-Beauquier–Nivat, 1989) The conjecture is true if \( n = 2 \) and \( V \) is a topological disk with nice boundaries.
Because this problem seems to be too hard, let me restrict to the case when \( V \) looks like a disjoint union of translations of a single unit cube \( [0, 1]^n \). Then using some tricks for dealing with irrational coordinates, the conjecture is equivalent to the following one.
The periodic tiling conjecture is true if we demand that the tile \( V \) and the tilings come from the standard tiling of \( \mathbb{R}^n \) by \( [0, 1]^n \). (Discrete reformulation: there does not exist a single subset \( V \subseteq \mathbb{Z}^n \) that translationally tiles \( \mathbb{Z}^n \) only aperiodically.)
This now looks like a fairly standard algebra problem, because we’re partitioning \( \mathbb{Z}^n \) into translations of a finite subset \( S \). But this problem is open as well. The following surprising result was proved by Mario Szegedy.
Theorem 8 (Szegedy, 1998). The discrete periodic tiling conjecture is true if \( \lvert V \rvert \) is a prime number. In fact, if \( \lvert V \rvert \) is prime, then every tiling has period \( \lvert V \rvert \) if every direction.
The proof is really nice, so let me give a sketch.
Figure 4. Translational tiling of a Y-pentomino
Proof. Let’s say that our tile is \( V = \{ (0,0), (0,1), (-1, 0), (1, 0), (2, 0) \} \). Consider the (Laurent) polynomial with two variables \[ \displaystyle Q _ V(x,y) = \sum _ {(a,b) \in V}^{} x^a y^b = 1 + y + x^{-1} + x + x^2. \] Now take the squares corresponding to the \( (0,0) \in V \) in \( \mathbb{Z}^2 \), and then add their monomials up like we did for \( Q _ V \). Then we get an infinite series \[ \displaystyle P(x,y) = \sum _ {(a,b) \text{ colored}}^{} x^a y^b. \] Because this is a tiling, we get \[ \displaystyle P(x,y) \cdot Q _ V(x,y) = \sum _ {a=-\infty}^{\infty} \sum _ {b=\infty}^{\infty} x^a y^b. \] If we multiply \( Q _ V^4 \) on both sides, we get \[ \displaystyle P(x,y) \cdot Q _ V^5(x, y) = 5^4 \sum _ {a=-\infty}^{\infty} \sum _ {b=-\infty}^{\infty} x^a y^b. \] If we look at everything modulo \( 5 \), we can apply Freshman’s dream and get \[ \displaystyle P(x, y) Q _ V(x^5, y^5) \equiv 0 \pmod{5}. \] The left hand side is just \[ \displaystyle \sum _ {(a,b) \text{ colored}}^{} (x^a y^b + x^a y^{b+5} + x^{a-5} y^b + x^{a+5} y^b + x^{a+10} y^b). \] Because all coefficients are multiple of \( 5 \) but has to be between \( 0 \) and \( 5 \), they are either \( 0 \) or \( 5 \). If \( (a,b) \) is colored, the coefficient of \( x^a y^b \) is nonzero, so it is \( 5 \). This shows that \( (a,b-5) \), \( (a+5, b) \), \( (a-5, b) \), \( (a-10,b) \) are colored as well. That is, the tiling is periodic. ▨
Recently, Siddhartha Bhattacharya posted a preprint on ArXiv claiming a proof of the discrete periodic tiling conjecture for \( n = 2 \). I tried to read this, but it uses the language of ergodic theory, of which I know nothing. If you know ergodic theory, I will appreciate it if you can explain to me how the proof goes.