Keller's conjecture

In geometry, Keller's conjecture is the conjecture that in any tiling of Euclidean space by identical hypercubes there are two cubes that meet face to face. For instance, as shown in the illustration, in any tiling of the plane by identical squares, some two squares must meet edge to edge.

For Keller's conjecture about polynomial maps, see Jacobian conjecture.

In this tiling of the plane by congruent squares, the green and violet squares meet edge-to-edge as do the blue and orange squares.

This conjecture was introduced by Ott-Heinrich Keller (1930), after whom it is named. It was shown to be true in dimensions at most 6 by Perron (1940a, 1940b). However, for higher dimensions it is false, as was shown in dimensions at least 10 by Lagarias and Shor (1992) and in dimensions at least 8 by Mackey (2002). These disproofs used a reformulation of the problem in terms of the clique number of certain graphs now known as Keller graphs. Although this graph-theoretic version of the conjecture was resolved for all dimensions by 2002, Keller's original cube-tiling conjecture remained open in dimension 7 until 2019. The conjecture was shown to be true in dimension 7 in Brakensiek, Heule & Mackey (2019).

The related Minkowski lattice cube-tiling conjecture states that, whenever a tiling of space by identical cubes has the additional property that the cube centers form a lattice, some cubes must meet face to face. It was proved by György Hajós in 1942.

Szabó (1993), Shor (2004), and Zong (2005) give surveys of work on Keller's conjecture and related problems.

Definitions

A family of closed sets called tiles forms a tessellation or tiling of a Euclidean space if their union is the whole space and every two distinct sets in the family have disjoint interiors. A tiling is said to be monohedral if all of the tiles are congruent to each other. Keller's conjecture concerns monohedral tilings in which all of the tiles are hypercubes of the same dimension as the space. As Szabó (1986) formulates the problem, a cube tiling is a tiling by congruent hypercubes in which the tiles are additionally required to all be translations of each other, without any rotation, or equivalently to have all of their sides parallel to the coordinate axes of the space. Not every tiling by congruent cubes has this property: for instance, three-dimensional space may be tiled by two-dimensional sheets of cubes that are twisted at arbitrary angles with respect to each other. Shor (2004) instead defines a cube tiling to be any tiling of space by congruent hypercubes, and states without proof that the assumption that cubes are axis-parallel can be added without loss of generality.

An n-dimensional hypercube has 2n faces of dimension n − 1, that are themselves hypercubes; for instance, a square has four edges, and a three-dimensional cube has six square faces. Two tiles in a cube tiling (defined in either of the above ways) meet face-to-face if there is an (n − 1)-dimensional hypercube that is a face of both of them. Keller's conjecture is the statement that every cube tiling has at least one pair of tiles that meet face-to-face in this way.

The original version of the conjecture stated by Keller was for a stronger statement, that every cube tiling has a column of cubes all meeting face to face. As with the weaker statement more commonly studied in subsequent research, this is true for dimensions up to six, false for dimensions eight or greater, and remains open for seven dimensions (Łysakowska & Przesławski 2008, 2011)

The Pythagorean tiling shows that unequal squares can tile the plane without meeting edge-to-edge.

It is a necessary part of the conjecture that the cubes in the tiling all be congruent to each other, for if similar but not congruent cubes are allowed then the Pythagorean tiling would form a trivial counterexample in two dimensions.

Group-theoretic reformulation

The disproof of Keller's conjecture, for sufficiently high dimensions, has progressed through a sequence of reductions that transform it from a problem in the geometry of tilings into a problem in group theory, and from there into a problem in graph theory.

Hajós (1949) first reformulated Keller's conjecture in terms of factorizations of abelian groups. He shows that, if there is a counterexample to the conjecture, then it can be assumed to be a periodic tiling of cubes with an integer side length and integer vertex positions; thus, in studying the conjecture, it is sufficient to consider tilings of this special form. In this case, the group of integer translations, modulo the translations that preserve the tiling, forms an abelian group, and certain elements of this group correspond to the positions of the tiles. Hajós defines a family of subsets A_i of an abelian group to be a factorization if each element of the group has a unique expression as a sum a₀ + a₁ + ..., where each a_i belongs to A_i. With this definition, Hajós' reformulated conjecture is that, whenever an Abelian group has a factorization in which the first set A₀ may be arbitrary but each subsequent set A_i takes the special form {0, g_i, 2g_i, 3g_i, ..., (q_i − 1)g_i}, then at least one of the elements q_ig_i must belong to A₀ −A₀ (the difference set of A₀ with itself).

Szabó (1986) showed that any tiling that forms a counterexample to the conjecture can be assumed to have an even more special form: the cubes have side length a power of two and integer vertex coordinates, and the tiling is periodic with period twice the side length of the cubes in each coordinate direction. Based on this geometric simplification, he also simplified Hajós' group-theoretic formulation, showing that it is sufficient to consider abelian groups that are the direct sums of cyclic groups of order four, and with each q_i = 2.

Keller graphs

The Keller graph of dimension two, isomorphic to the Clebsch graph.

Corrádi & Szabó (1990) reformulated Szabó's result as a condition about the existence of a large clique in a certain family of graphs, which subsequently became known as the Keller graphs. More precisely, the vertices of the Keller graph of dimension n are the 4ⁿ elements (m₁,...,m_n) where each m is 0, 1, 2, or 3. Two vertices are joined by an edge if they differ in at least two coordinates and differ by exactly two in at least one coordinate. Corrádi and Szabó showed that the maximum clique in this graph has size at most 2ⁿ, and that if there is a clique of this size then Keller's conjecture is false. Given such a clique, one can form a covering of space by cubes of side two whose centers have coordinates that, when taken modulo four, are vertices of the clique. The condition that any two vertices of the clique have a coordinate that differs by two implies that cubes corresponding to these vertices do not overlap. The condition that the clique has size 2ⁿ implies that the cubes within any period of the tiling have the same total volume as the period itself. Together with the fact that they don't overlap, this implies that the cubes placed in this way tile space. However, the condition that any two clique vertices differ in at least two coordinates implies that no two cubes have a face in common.

Lagarias and Shor (1992) disproved Keller's conjecture by finding a clique of size 2¹⁰ in the Keller graph of dimension 10. This clique leads to a non-face-to-face tiling in dimension 10, and copies of it can be stacked (offset by half a unit in each coordinate direction) to produce non-face-to-face tilings in any higher dimension. Similarly, Mackey (2002) reduced the dimension in which a counterexample to the conjecture is known by finding a clique of size 2⁸ in the Keller graph of dimension eight.

Finally, Debroni et al. (2011) showed that the Keller graph of dimension seven has a maximum clique of size 124 <  2⁷. Because this is less than 2⁷, the graph-theoretic version of Keller's conjecture is true in seven dimensions. However, the translation from cube tilings to graph theory can change the dimension of the problem, so this result doesn't settle the geometric version of the conjecture in seven dimensions.

The sizes of the maximum cliques in the smaller Keller graphs of dimensions 2, 3, 4, 5, and 6 are, respectively, 2, 5, 12, 28, and 60. The Keller graphs of dimensions 4, 5, and 6 have been included in the set of "DIMACS challenge graphs" frequently used as a benchmark for clique-finding algorithms (Johnson & Trick 1996).

Related problems

As Szabó (1993) describes, Hermann Minkowski was led to a special case of the cube-tiling conjecture from a problem in diophantine approximation. One consequence of Minkowski's theorem is that any lattice (normalized to have determinant one) must contain a nonzero point whose Chebyshev distance to the origin is at most one. The lattices that do not contain a nonzero point with Chebyshev distance strictly less than one are called critical, and the points of a critical lattice form the centers of the cubes in a cube tiling. Minkowski conjectured in 1900 that, whenever a cube tiling has its cubes centered at lattice points in this way, it must contain two cubes that meet face to face. If this is true, then (because of the symmetries of the lattice) each cube in the tiling must be part of a column of cubes, and the cross-sections of these columns form a cube tiling of one smaller dimension. Reasoning in this way, Minkowski showed that (assuming the truth of his conjecture) every critical lattice has a basis that can be expressed as a triangular matrix, with ones on its main diagonal and numbers less than one away from the diagonal. György Hajós proved Minkowski's conjecture in 1942 using Hajós's theorem on factorizations of abelian groups, a similar group-theoretic method to the one that he would later apply to Keller's more general conjecture.

Keller's conjecture is a variant of Minkowski's conjecture in which the condition that the cube centers form a lattice is relaxed. A second related conjecture, made by Furtwängler in 1936, instead relaxes the condition that the cubes form a tiling. Furtwängler asked whether a system of cubes centered on lattice points, forming a k-fold covering of space (that is, all but a measure-zero subset of the points in the space must be interior to exactly k cubes) must necessarily have two cubes meeting face to face. Furtwängler's conjecture is true for two- and three-dimensional space, but Hajós found a four-dimensional counterexample in 1938. Robinson (1979) characterized the combinations of k and the dimension n that permit a counterexample. Additionally, combining both Furtwängler's and Keller's conjectures, Robinson showed that k-fold square coverings of the Euclidean plane must include two squares that meet edge to edge. However, for every k > 1 and every n > 2 there is a k-fold tiling of n-dimensional space by cubes with no shared faces (Szabó 1982).

Once counterexamples to Keller's conjecture became known, it became of interest to ask for the maximum dimension of a shared face that can be guaranteed to exist in a cube tiling. When the dimension n is at most six, this maximum dimension is just n − 1, by Perron's proof of Keller's conjecture for small dimensions, and when n is at least eight, then this maximum dimension is at most n − 2. Lagarias & Shor (1994) showed more strongly that it is at most n − √n/3.

Iosevich & Pedersen (1998) and Lagarias, Reeds & Wang (2000) found close connections between cube tilings and the spectral theory of square-integrable functions on the cube.

Dutour Sikirić, Itoh & Poyarkov (2007) use cliques in the Keller graphs that are maximal but not maximum to study packings of cubes into space that cannot be extended by adding any additional cubes.

In 1975, Ludwig Danzer and independently Branko Grünbaum and G. C. Shephard found a tiling of three-dimensional space by parallelepipeds with 60° and 120° face angles in which no two parallelepipeds share a face; see Grünbaum & Shephard (1980).

References

• Brakensiek, Joshua; Heule, Marijn; Mackey, John (2019), The resolution of Keller's conjecture, arXiv:1910.03740
• Corrádi, K.; Szabó, S. (1990), "A combinatorial approach for Keller's conjecture", Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society, 21 (2): 95–100, doi:10.1007/BF01946848, MR 1070948.
• Debroni, Jennifer; Eblen, John D.; Langston, Michael A.; Shor, Peter; Myrvold, Wendy; Weerapurage, Dinesh (2011), "A complete resolution of the Keller maximum clique problem", Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (PDF), pp. 129–135.
• Dutour Sikirić, Mathieu; Itoh, Yoshiaki; Poyarkov, Alexei (2007), "Cube packings, second moment and holes", European Journal of Combinatorics, 28 (3): 715–725, arXiv:math/0509100, doi:10.1016/j.ejc.2006.01.008, MR 2300752.
• Grünbaum, Branko; Shephard, G. C. (1980), "Tilings with congruent tiles", Bulletin of the American Mathematical Society, 3 (3): 951–973, doi:10.1090/S0273-0979-1980-14827-2, MR 0585178.
• Hajós, G. (1949), "Sur la factorisation des groupes abéliens", Československá Akademie Věd. Časopis Pro Pěstování Matematiky, 74: 157–162, MR 0045727.
• Iosevich, Alex; Pedersen, Steen (1998), "Spectral and tiling properties of the unit cube", International Mathematics Research Notices (16): 819–828, arXiv:math/0104093, doi:10.1155/S1073792898000506, MR 1643694.
• Johnson, David S.; Trick, Michael A. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11–13, 1993, Boston, MA, USA: American Mathematical Society, ISBN 0-8218-6609-5.
• Keller, O. -H. (1930), "Über die lückenlose Erfüllung des Raumes mit Würfeln", Journal für die reine und angewandte Mathematik (in German), 163: 231–248, doi:10.1515/crll.1930.163.231, JFM 56.1120.01.
• Lagarias, Jeffrey C.; Reeds, James A.; Wang, Yang (2000), "Orthonormal bases of exponentials for the n-cube", Duke Mathematical Journal, 103 (1): 25–37, doi:10.1215/S0012-7094-00-10312-2, MR 1758237.
• Lagarias, Jeffrey C.; Shor, Peter W. (1992), "Keller's cube-tiling conjecture is false in high dimensions", Bulletin of the American Mathematical Society, New Series, 27 (2): 279–283, arXiv:math/9210222, doi:10.1090/S0273-0979-1992-00318-X, MR 1155280.
• Lagarias, J. C.; Shor, P. W. (1994), "Cube-tilings of Rⁿ and nonlinear codes", Discrete and Computational Geometry, 11 (4): 359–391, doi:10.1007/BF02574014, MR 1273224.
• Łysakowska, Magdalena; Przesławski, Krzysztof (2008), Keller's conjecture on the existence of columns in cube tilings of Rⁿ, arXiv:0809.1960, Bibcode:2008arXiv0809.1960L.
• Łysakowska, Magdalena; Przesławski, Krzysztof (2011), "On the structure of cube tilings and unextendible systems of cubes in low dimensions", European Journal of Combinatorics, 32 (8): 1417–1427, doi:10.1016/j.ejc.2011.07.003.
• Mackey, John (2002), "A cube tiling of dimension eight with no facesharing", Discrete and Computational Geometry, 28 (2): 275–279, doi:10.1007/s00454-002-2801-9, MR 1920144.
• Perron, Oskar (1940a), "Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel", Mathematische Zeitschrift, 46: 1–26, doi:10.1007/BF01181421, MR 0003041.
• Perron, Oskar (1940b), "Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel. II", Mathematische Zeitschrift, 46: 161–180, doi:10.1007/BF01181436, MR 0006068.
• Robinson, Raphael M. (1979), "Multiple tilings of n-dimensional space by unit cubes", Mathematische Zeitschrift, 166 (3): 225–264, doi:10.1007/BF01214145, MR 0526466.
• Shor, Peter (2004), Minkowski's and Keller's cube-tiling conjectures, Lecture notes for IAP Mathematics Lecture Series.
• Szabó, Sándor (1982), "Multiple tilings by cubes with no shared faces", Aequationes Mathematicae, 25 (1): 83–89, doi:10.1007/BF02189600, MR 0716380.
• Szabó, Sándor (1986), "A reduction of Keller's conjecture", Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society, 17 (4): 265–277, doi:10.1007/BF01848388, MR 0866636.
• Szabó, Sándor (1993), "Cube tilings as contributions of algebra to geometry", Beiträge zur Algebra und Geometrie, 34 (1): 63–75, MR 1239279.
• Zong, Chuanming (2005), "What is known about unit cubes", Bulletin of the American Mathematical Society, New Series, 42 (2): 181–211, doi:10.1090/S0273-0979-05-01050-5, MR 2133310.