Recently, a team of computer scientists and mathematicians has completely solved a mathematical puzzle known as the Keller conjecture. The Keller conjecture is a 90-year-old puzzle related to the problem of dense paving in different spatial dimensions.
We can start with the simplest two-dimensional case. In two-dimensional space, when paving with square tiles of the same size, is it always the case that two tiles have a whole shared edge? It is not difficult to see from the graphics that this is indeed the case.
In two-dimensional space, when paved with square tiles of the same size, the yellow edges indicate two fully linked tiles.
Is the same with elevating this problem from two-dimensional to three-dimensional space?
It is not difficult to see that when a space is completely filled with a cube of the same size, there must be a situation where two cubes completely share a face.
Compacting cubes of the same size in 3D space causes two cubes to share a face. | Image reference: cs.cmu.edu
Two-dimensional and three-dimensional situations are spaces that we can imagine, but what about in higher dimensions? In 1930, the German mathematician Ott-Heinrich Keller hypothesized that this pattern applied to any dimension. This is the Keller conjecture.
In the decades since, the Keller conjecture has made many advances. In 1940, mathematician Oskar Perron successfully proved that the Keller conjecture was correct in six dimensions and smaller dimensions. In 1992, however, the work of Jeffrey Lagarias and Peter Shor showed that when the dimension was raised to ten or more, the conjecture no longer held. By 2002, John Mackey had further narrowed this "exclusion" to an eight-dimensional space, indicating that it no longer applied in eight or more dimensions. In this way, what is still in the unknown state is the situation in the seven-dimensional space.
From Perron to Lagarias and Shor, the approach to research has changed significantly as mathematicians challenge this conjecture. In Perron's day, he relied on pen and paper to calculate the applicability of this pattern in the first six dimensions; in the 1990s, in order to get powerful computers to join the challenge, mathematicians Keresztély Corrádi and Sándor Szabó re-articulated the conjecture, transforming it into a completely different form.
Keller's conjecture originally involved a smooth, continuous space in which there were infinite ways to pave an infinite number of tiles, and this infinity was a problem that computers were not good at dealing with. Corrádi and Szabó therefore deal with conjectures into some kind of problem involving discrete, finite objects. Such an equivalence method effectively reduces a problem about infinity to an arithmetic problem about a few numbers, and one of the fundamental cores involved is a graph called a Keller diagram.
Simply put, the Keller diagram is made up of dice with a specific number of points, and the connections between those dice. Points correspond to dimensional numbers, and to determine whether the Keller hypothesis is correct in n-dimensional space, it is possible to look for the existence of a small set of 2ⁿ dice connected to each other on the Keller diagram, and if so, the Keller conjecture is incorrect in the n-dimensional.
Take the Keller conjecture in two-dimensional space as an example, first imagine that there are some dice on the table, and for each dice, the number of points on the upward side is 2 points - these two points correspond to the two-dimensional, and their positions represent the x and y axes in the coordinate system. Next, each dot is arbitrarily colored with four colors: red, green, black, and white, and red and green, black and white are set as two sets of "paired colors".
Now, when the points in the same position of two dice have different colors, and the colors of the points in the other position are not only different, but the colors are paired (red and green, or black and white), the two dice dice are connected in a straight line, and the condition of connecting with a line is satisfied in the fourth case in the figure below.
There are two dots on the dice in a two-dimensional Keller diagram, which means that the two tiles coincide perfectly in space if the colors of the dots on the two dice are identical; if the two dice have neither a common color nor a matching color, it means that the tiles overlap partially (a situation where the two dice are not allowed in a paving problem); if the two dice have a color pairing in one position and the color on the other position, it means that the two tiles have a shared surface; when there is a connection between the two dice, it means that the two tiles are in contact with each other. But slightly misaligned from each other. This last scenario is the example to look for in proving Keller's conjecture, which represents tiles that touch each other but don't share a surface. | Image reference: Samuel Velasco/Quanta Magazine
In the Keller diagram, each dice can be seen as a tile in Keller's conjecture; the color on the dice can be seen as coordinates that define the position of the tile in space; and whether there is a connection between the dice can be seen as a description of the relative position of the two tiles.
Keller diagram of two-dimensional space. | Image reference: cs.cmu.edu
The image above shows the Keller diagram of the two-dimensional case, which consists of 16 dice with 2 points. As already mentioned, this graph turns the proof of the Keller conjecture into a judgment on whether 4 (i.e. 2²) of such dice can be found to form a small set that is completely interconnected with each other, and if so, proves that the Keller conjecture is wrong in two-dimensional space.
A small set of 4 dice that are perfectly connected to each other. | Image reference: Quanta Magazine
But as can be seen from the two-dimensional Keller diagram, such a small set does not exist, so Keller's conjecture is correct in two-dimensional space.
Using this approach, Corrádi and Szabó proved that the Keller conjecture applies to three-dimensional space with 216 dice with 3 points, in which case the counterexample they were looking for was 8 (i.e. 2³) interconnected dice. Mackey proved that the Keller conjecture does not apply to eight dimensions and beyond by finding a small set of 256 (i.e. 2⁸) dice with 8 points.
To determine whether seven-dimensional space is suitable for the Keller conjecture, one needs to determine whether a small set of 128 (i.e. 2⁷) dice with 7 points can be found. Seven-dimensional space has always been a difficult point, which is not unrelated to the prime nature of it, which means that it cannot be decomposed into lower dimensions.
Finally, in the new study, mathematicians Joshua Brakensiek, Marijn Heule, Mackey, and David Narváez solved the problem with the help of 40 computers. The final answer given by the computer is: Yes. This means that we finally know how the Keller conjecture applies in the last dimension, proving that the Keller conjecture is still correct in seven-dimensional space. And the answer provided by the computer is much more than a simple conclusion, it also includes a 200Gb size of evidence to prove that the answer is correct.
At this point, the Keller conjecture can be considered to have been completely resolved.
References:
https://www.cs.cmu.edu/~mheule/Keller/
https://www.quantamagazine.org/computer-search-settles-90-year-old-math-problem-20200819/
https://mathworld.wolfram.com/KellersConjecture.html