Keller's conjecture

Remarks

Ott-Heinrich Keller conjectured in 1930 that clause 1 holds in every dimension. Oskar Perron proved it for $n \le 6$ in 1940. Jeffrey Lagarias and Peter Shor showed in 1992 that it fails for $n \ge 10$, and John Mackey showed in 2002 that it fails for $n = 8$, hence also for $n = 9$. The case $n = 7$ was settled positively in 2020 by Joshua Brakensiek, Marijn Heule, John Mackey and David Narváez with a large computer search based on a SAT solver. The counterexamples come from cliques in the Keller graphs, finite graphs whose large cliques correspond to cube tilings without face-to-face pairs. For $n = 2$ the statement is easy to see. A tiling of the plane by unit squares splits into rows or into columns, and two neighbouring squares in a row or column share an edge.

Going deeper

For a student

In the plane the conjecture is easy, and in three dimensions it can still be checked by hand. Hajós turned the problem into a question about factorizations of finite abelian groups, and later the problem was reduced to finite graphs. These reductions allowed computer searches, and the final case, dimension $7$, needed a computer-assisted proof. The lattice version, where the translation vectors form a lattice, is Minkowski's conjecture, proved by Hajós in 1941 in all dimensions.