High-Dimensional Sudoku Puzzle Proves Mathematicians Wrong on Long-standing Geometry Problem

High-Dimensional Sudoku Puzzle Proves Mathematicians Wrong about Long-Standing Geometry Problem

By Max Springer

Tiling a two-dimensional bathroom floor is a straightforward home renovation, but researchers have found that in higher dimensions it could blossom into a baffling mess of nonrepeating chaos. New results overturn a long-standing tiling conjecture, showing another way disorder must emerge from the structured realm of mathematics.

Generally speaking, a tiling is a way to cover some space with lots of little pieces (tiles) that fit together without gaps or overlaps. A never-ending bathroom floor or infinitely large car trunk being loaded for a road trip are natural examples in two or three dimensions. A tiling is “periodic” if copies of a single shape fit together in a pattern that repeats itself in every direction to fill the space—akin to the herculean task of loading an endless car trunk with identically sized luggage arranged in a pattern. The periodic tiling conjecture this study took on says every shape that can tile a space without rotating or flipping must be able to do so in a repeating, regular way.

The study authors, publishing in the Annals of Mathematics, disproved this conjecture by constructing a strictly aperiodic tile—one that fully covers a space without any regular pattern. To do so, they translated the geometric tiling problem into an algebraic one defined by a system of equations. Each equation captures constraints to which a tiling must adhere—such as no rotations and no gaps between the tiles—forming a kind of “tiling language,” says study co-author Rachel Greenfeld, a mathematician at Northwestern University.

On supporting science journalism

If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

With the addition of more constraints in this language, the potential number of solutions shrinks in the same way that there are fewer possible numbers you can put into a Sudoku square as more of the puzzle is filled in. The ultimate solution, a nonrepeating sequence of numbers, can then be translated back into a strictly aperiodic tile, disproving the conjecture. “Tiling is just not simple enough to be well behaved forever, but it’s [also] not complex enough to be crazy forever,” Greenfeld says.

In disproving the result, the researchers “almost find a way to turn the shape of a tile into a programming language,” says University of Waterloo computer scientist Craig Kaplan. Because the result came from adding more and more constraints, which translate to extra dimensions, the counterexample turned out to operate in an extremely high-dimensional space—something like 10^100,000 dimensions (that’s a number with 100,000 digits).

“High-dimensional tilings are enormously complex,” says study co-author Terence Tao, a Fields Medal–winning mathematician at the University of California, Los Angeles. “The situation seems much better behaved in low-dimensional [space], with three dimensions being the current frontier of research.” Comparing this intuitive space with the high-dimensional result, he says, we are “at the boundary between order and complete chaos.”