Humans Couldn't Solve This Math Problem for 90 Years. Computers Did It in 30 Minutes.
The last dimension of Keller's conjecture has been proven using a computer algorithm.
The conjecture involves the way hypercubes in different dimensions share sides when tiled.
The proof is computerized and verified by another computer, indecipherable by humans.
Scientists have trained a computer algorithm to complete a nearly century-old math problem in a mere half hour. Keller’s conjecture, a tessellation problem about the way certain shapes tile in certain spaces, has been solved for all but seven-dimensional space. Now, the brute force of computational power has let scientists hand over the most tedious part of the job—with conclusive results that can’t be confirmed by humans. Let’s dig in.
➗ You love numbers. We love numbers. Let's nerd out over them together.
Keller’s conjecture sounds simple: “tiling an n-dimensional space with n-dimensional hypercubes of equal size yields an arrangement in which at least two hypercubes have an entire (n-1)-dimensional ‘side’ in common.” So when your Boggle cubes settle into the little cube nests on the Boggle board, they’re flush alongside one another. The bricks in a wall end up fully touching along at least one side.
But for more dimensions, it gets complicated. The term hypercube includes the same kinds of shapes—perpendicular sided “cubes,” but raised to different spatial dimensionalities, meaning there are complexities we can’t analogize with a brick wall or Boggle anymore. This becomes messy and harder to reason through.
“In 1986 [mathematician] Szab́o reduced Keller’s conjecture to the study of periodic tilings. Using this reduction [mathematicians] Corradi and Szabo introduced the Keller graphs: the graph has vertices such that a pair are adjacent if and only if they differ by exactly [one amount] in at least one coordinate and they differ in at least two coordinates,” the scientists write in their introduction.
This means the remaining problem, in seven dimensions, could be solved through what computer scientists call “brute force,” which just means a computer is able to systematically process all examples to test them for validity. In a given dimensionality, are there vertices that differ by exact one amount, with at least two other, different coordinates? Do the tiled seven-dimensional hypercubes conform to this condition?
The math sounds simple, but it’s computationally expensive—a term reflecting the way computer math can exponentially increase, very quickly, to the point that it’s impossible even for a powerful computer to do. Think of the old adage about folding paper, which becomes impossible quickly for a normal sheet of printer paper. After 10 folds, the hypothetical paper is over a thousand layers thick. Now imagine that each fold included axis values between, say, -10 and 10 only. For those 21 number line values, over seven dimensions of coordinates have almost 2 billion possible combinations.
Proving the conjecture by dimensions has revealed surprises, Quanta reports. For dimensions 1 through 6, mathematician Oskar Perron proved the conjecture in 1940. But in the 1990s, mathematicians Jeffrey Lagarias and Peter Shor proved it was not true in 10 dimensions. The nature of higher dimensions means brilliant mathematicians can find ways to shortcut having to manually solve an entire set, for example, because they can prove a smaller relationship that scales up to the entire problem.
If you have 10 chances to solve a problem, but you solve it in your first chance, why would you need to work on the other nine chances?
Only seven was left because of a funny overlap in work. “[A]fter Lagarias and Shor, the only unsettled dimensions were seven, eight and nine. In 2002, Mackey proved Keller’s conjecture false in dimension eight (and therefore also in dimension nine),” Quanta explains. “That left just dimension seven open—it was either the highest dimension where the conjecture holds or the lowest dimension where it fails.”
You Might Also Like
