‘Nasty’ Geometry Breaks Decades-Old Tiling Conjecture

Penrose’s two tiles raised the question: Might there be a single, cleverly shaped tile that fits the bill?

Surprisingly, the answer turns out to be yes — if you’re allowed to shift, rotate and reflect the tile, and if the tile is disconnected, meaning that it has gaps. Those gaps get filled by other suitably rotated, suitably reflected copies of the tile, ultimately covering the entire two-dimensional plane. But if you’re not allowed to rotate this shape, it’s impossible to tile the plane without leaving gaps.

Indeed, several years ago, the mathematician Siddhartha Bhattacharya proved that — no matter how complicated or subtle a tile design you come up with — if you’re only able to use shifts, or translations, of a single tile, then it’s impossible to devise a tile that can cover the whole plane aperiodically but not periodically.

Mathematicians conjectured that Bhattacharya’s two-dimensional result would also hold in higher-dimensional spaces. Just as no aperiodic two-dimensional tile exists, they supposed that no suitable three-dimensional block (or more complicated tile) exists, and so on in an arbitrarily large number of dimensions.

This hypothesis was dubbed the periodic tiling conjecture.

In a preprint posted last month, Greenfeld, along with Terence Tao of the University of California, Los Angeles, finally settled the conjecture — but not in the way mathematicians had anticipated. They constructed a tile that can aperiodically fill a high-dimensional space but cannot do so periodically, thus disproving the conjecture.

“That was a surprise. I expected the conjecture to be true in all dimensions,” said Mihalis Kolountzakis, a mathematician at the University of Crete. “But I guess in high enough dimensions, intuition does not go very far.”

The strange tile isn’t just noteworthy for pushing the boundaries of what’s geometrically possible and what’s not. It’s also intimately connected to questions beyond geometry — including ones about the limits of logic itself.

The Pivot

In 2019, Greenfeld arrived at UCLA as a postdoctoral researcher, and she and Tao — having both worked independently on another problem related to translational tilings — set their sights on proving the periodic tiling conjecture.

Since the conjecture was already known to be true in one and two dimensions, they sought to prove it in three: to show that if you can shift copies of one shape to tile all of three-dimensional space, then there must be a way to tile the space periodically.

They made some progress, re-proving the conjecture in two dimensions using different techniques — ones they hoped would be applicable to the three-dimensional case. But then they hit a wall. “At some point, we got frustrated and said, ‘OK, maybe there’s a reason why we can’t prove this conjecture in higher dimensions. We should start looking for counterexamples,’” Tao said.

They combed the literature for other aperiodic constructions, starting with the first one: the set of more than 20,000 tiles, published in 1964, that could cover the plane through translations, but only aperiodically. They then got to work developing new techniques for constructing a single aperiodic tile.

They started with a change of setting. Say you want to tile two-dimensional space. Instead of trying to tile a continuous plane, consider a two-dimensional lattice, an infinite array of points arranged in a grid. You can now define a tile as a finite set of points on that grid; if you have a proper tiling, then you can cover every point in the lattice exactly once by making copies of that finite set of points and sliding them around.

Proving the “discrete” periodic tiling conjecture for high-dimensional lattices is a slightly different problem than proving the continuous version of the conjecture, as there are tilings that are possible in lattices but not in continuous space. But they’re related. Greenfeld and Tao planned to come up with a discrete counterexample to the conjecture that they could then modify to work in the continuous case as well.

In the summer of 2021, they came close, finding two tiles in a very high-dimensional space. The tiles can fill the space they inhabit, but only aperiodically. “This is not enough,” Greenfeld said. “Two is very close, but tiling by two tiles is much less rigid than tiling by a single tile.” It would take another year and a half for them to assemble a true counterexample to the periodic tiling conjecture.

Tile Sandwich

They started by creating a new language, rewriting their problem as a special kind of equation. The unknown “variable” in this equation — what they needed to solve for — represented all possible ways to tile a high-dimensional space. “But it’s hard to describe things with just one equation,” Tao said. “Sometimes you need multiple equations to describe a really complicated set in space.”

So Greenfeld and Tao reframed the question they were trying to solve. They realized that they could instead devise a system of equations, where each equation would encode a different constraint on their solution. This let them break up their problem into a question about many different tiles — in this case, tiles that all cover a given space using the same set of translations.

For instance, in two dimensions, you can tile the plane with a square by sliding it up, down, left or right, one unit at a time. But other shapes can also tile the plane using the exact same set of shifts: for example, a square with a bump added to the right edge and removed from the left edge, like a jigsaw puzzle piece.

If you take a square, a puzzle piece, and other tiles that use the same set of shifts, and then stack them together like cold cuts in a sandwich, you can construct one tile that uses a single set of translations to cover three-dimensional space. Greenfeld and Tao would need to do this in many more dimensions.

“Since we were working in high dimensions anyway, adding one more dimension didn’t really hurt us,” Tao said. Rather, it gave them the additional flexibility they’d need to get their hands on a good solution.

The mathematicians sought to reverse this sandwich-building procedure, rewriting their single-equation, high-dimensional tiling problem as a series of tiling equations in lower dimensions. Those equations would later dictate what the higher-dimensional tile construction would look like.

Greenfeld and Tao thought of their system of tiling equations as a computer program: Every line of code, or equation, is a command, and in combination the commands can generate a program that achieves a specific goal. “Logic circuits are built up of very basic objects, these AND gates and OR gates and so forth, each of which is not very interesting,” Tao said. “But you can stack them together, and you can make a circuit that will draw a sine wave or communicate on the internet.”

“So we started viewing our problem as kind of a programming problem,” he continued. Each of their commands would be a different property that their final tiling needed to satisfy, so that the program as a whole would guarantee that any tilings fitting all the criteria must be aperiodic.

The question, then, became what kinds of properties they needed to encode in all those tiling equations to make that happen. A tile in one layer of the sandwich, for instance, might be shaped in a way that would only permit certain kinds of movements. The mathematicians would have to build up their list of constraints carefully — so that it wouldn’t be so restrictive as to preclude any solutions whatsoever, but would be restrictive enough to exclude all periodic solutions.

“The game here is to construct the correct level of constraint,” Greenfeld said, “to encode the correct puzzle.”

Infinite Sudoku

The puzzle that Greenfeld and Tao hoped to program with their tiling equations was a grid with an infinite number of rows and a large but finite number of columns. The mathematicians sought to fill every row and diagonal with particular sequences of digits that corresponded to the kinds of constraints they could describe with tiling equations: something they likened to a giant sudoku puzzle. The pair then found sequences that were aperiodic — meaning that the solution to the associated system of tiling equations was also aperiodic. “There’s basically only one solution to this puzzle, and it’s this funny thing that’s almost but not quite periodic,” Tao said. “That took a lot of time to find.”

“This sort of thing, where you study functions that are almost periodic but not quite, is something that has been around in mathematics,” said Izabella Łaba, a mathematician at the University of British Columbia. “But this is a very different way to use that type of structure.”

As Iosevich put it, Greenfeld and Tao “created a completely elementary object and lifted it up to a situation where things look more complicated.”

In doing so, they constructed a high-dimensional aperiodic tile — first in the discrete setting, then in the continuous one. Their tile is so complicated, so full of twists and holes, that it barely tiles space. “It’s a nasty tile,” Tao said. “We did not make any attempt to make this tile pretty.” He and Greenfeld didn’t compute the dimension of the space it lives in; they just know it’s massive, possibly as large as $latex 2^{{100}^{100}}$. (If you tried to write this number out in the pages of all the books in the world, you’d run out of paper.) “Our proof is constructive, so everything is explicit and computable,” Greenfeld said. “But because it’s very, very far from being optimal, we just didn’t check it.”

Indeed, the mathematicians think they can find aperiodic tiles in much lower dimensions. That’s because some of the more technical parts of their construction involved working in special spaces that are conceptually “very close to being two-dimensional,” Greenfeld said. She doesn’t think they’ll find a three-dimensional tile, but she says it’s feasible that a 4D one could exist.

And so, Iosevich said, they didn’t just disprove the periodic tiling conjecture: “They did this in the most humiliating fashion possible.”

Foray Into Incompleteness

The work marks a new way to construct aperiodic tiles — one that Greenfeld and Tao now think could be applied to disproving other tiling-related conjectures. That, in turn, will likely allow mathematicians to push even further at the boundaries of where complexity can arise. “There does seem to be this emerging sort of principle that higher-dimensional geometry is just nasty,” Tao said. “That pathologies can show up, and that the intuition that we get from two and three dimensions can be misleading.”

The work also taps into questions not just about the boundaries of human intuition but about the boundaries of mathematical reasoning. In the 1930s, the mathematician Kurt Gödel showed that any logical system that’s sufficient for developing basic arithmetic is incomplete: There are statements that can be neither proved nor disproved within that system. Mathematics, it turns out, is full of “undecidable” statements.

In a similar vein, it’s also full of computationally undecidable problems — problems that cannot be solved by any algorithm in a finite amount of time. Mathematicians discovered in the 1960s that problems about tilings can also be undecidable. That is, for some sets of shapes, you can prove that it’s impossible to figure out, in finite time, if they tile a given space or not. (The only way to do so, in principle, would be to consider all possible ways to lay tiles next to one another, until the end of time.)

“It’s a very simple-to-state problem, but nonetheless beyond the scope of mathematics,” said Richard Kenyon, a mathematician at Yale University. “It’s not the first example of this situation where a certain mathematical theory is undecidable or incomplete, but it’s really the most down-to-earth one.”

Last year, Greenfeld and Tao found that a general statement about pairs of high-dimensional tiles is undecidable: They proved that nobody will ever be able to figure out if certain pairs of tiles can be made to entirely cover the space they inhabit (whether periodically or aperiodically).

Could a statement about a single tile also be undecidable? It’s been known since the 1960s that if the periodic tiling conjecture were true, then it would always be possible to determine whether any given tile could cover the plane.

But the opposite is not necessarily true. Just because an aperiodic tile exists, that doesn’t imply that an undecidable one does.

That’s what Greenfeld and Tao want to figure out next, using some of the techniques they developed for their recent result. “It’s quite plausible, we think, that the language we created should be able to create an undecidable puzzle,” Tao said. “So there may be some tile for which we will never be able to prove it tiles space or doesn’t tile space.”

To prove that a statement is undecidable, mathematicians typically show that it’s equivalent to another question that’s already known to be undecidable. As a result, if this tiling problem turns out to be undecidable as well, it can serve as one more tool for demonstrating undecidability in other contexts — contexts well beyond questions about how to tile spaces.

In the meantime, though, Greenfeld and Tao’s result serves as a warning of sorts. “Mathematicians like beautiful, clean statements,” Iosevich said. “But don’t believe everything you hear. … Unfortunately, it’s not a fact that all interesting statements in mathematics need to be pretty, and that they need to work out the way we want them to.”

Correction: December 16, 2022
Due to an editing error, an earlier version of this article said that $latex 2^{{100}^{100}}$  is about 3 followed by 199 zeros, or $latex 3 \times {10}^{199}$ . In fact, that is roughly the number of digits that this number contains . The number itself is about $latex 10^{3 \times {10}^{199}}$, a much larger value.