Keller's conjecture
In geometry, Keller's conjecture is the conjecture that in any tiling of n-dimensional Euclidean space by identical hypercubes, there are two hypercubes that share an entire (n − 1)-dimensional face with each other. For instance, in any tiling of the plane by identical squares, some two squares must share an entire edge, as they do in the illustration.
This conjecture was introduced by
The related Minkowski lattice cube-tiling conjecture states that whenever a tiling of space by identical cubes has the additional property that the cubes' 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.
Statement
A tessellation or tiling of a Euclidean space is, intuitively, a family of subsets that cover the whole space without overlapping. More formally, a family of closed sets, called tiles, forms a tiling 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 have the same shape (they 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. In formulating the same problem, Shor (2004) instead considers all tilings 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.[1]
The original version of the conjecture stated by Keller was for a stronger statement: every cube tiling has a column of cubes all meeting face-to-face. This version of the problem is true or false for the same dimensions as its more commonly studied formulation.[2] It is a necessary part of the conjecture that the cubes in the tiling all be congruent to each other, for if cubes of unequal sizes are allowed, then the Pythagorean tiling would form a counterexample in two dimensions.
The conjecture as stated does not require all of the cubes in a tiling to meet face-to-face with other cubes. Although tilings by congruent squares in the plane have the stronger property that every square meets edge-to-edge with another square, some of the tiles in higher-dimensional hypercube tilings may not meet face-to-face with any other tile. For instance, in three dimensions, the tetrastix structure formed by three perpendicular sets of square prisms can be used to construct a cube tiling, combinatorially equivalent to the Weaire–Phelan structure, in which one fourth of the cubes (the ones not part of any prism) are surrounded by twelve other cubes without meeting any of them face-to-face.[3]
Group-theoretic reformulation
Keller's conjecture was shown to be true in dimensions at most six by Perron (1940a, 1940b). 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.[1]
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, with each qi = 2.
Keller graphs
Lagarias and Shor (1992) disproved Keller's conjecture by finding a clique of size 210 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) found a clique of size 28 in the Keller graph of dimension eight, leading in the same way to a non-face-to-face tiling in dimension 8 and (by stacking) in dimension 9.
Subsequently, Debroni et al. (2011) showed that the Keller graph of dimension seven has a maximum clique of size 124. Because this is less than 27 = 128, 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 does not settle the geometric version of the conjecture in seven dimensions. Finally, a 200-gigabyte computer-assisted proof in 2019 used Keller graphs to establish that the conjecture holds true in seven dimensions.[5] Therefore, the question Keller posed can be considered solved: the conjecture is true in seven dimensions or fewer but is false when there are more than seven dimensions.[6]
The sizes of the maximum cliques in the 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.[7]
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.[8]
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.[9]
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 seven, this maximum dimension is just n − 1, by the proofs of Keller's conjecture for those small dimensions, and when n is at least eight, then this maximum dimension is at most n − 2. Lagarias & Shor (1994) showed that it is at most n − √n/3, stronger for ten or more dimensions.
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.
In 1975, Ludwig Danzer and independently
Notes
- ^ a b c Szabó (1993); Shor (2004); Zong (2005)
- ^ Łysakowska and Przesławski (2011, 2012).
- ^ Conway, Burgiel & Goodman-Strauss (2008).
- ^ Corrádi & Szabó (1990).
- ^ Brakensiek et al. (2020).
- ^ Hartnett (2020).
- ^ Johnson & Trick (1996); Debroni et al. (2011), "Keller graphs are in the benchmark set of clique problems from the DIMACS clique challenge, and they appear to be especially difficult for clique algorithms."
- ^ Szabó (1993).
- ^ Szabó (1982).
- ^ Grünbaum & Shephard (1980).
References
- Brakensiek, Joshua; S2CID 203951899
- MR 2410150
- 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, S2CID 121453908.
- Debroni, Jennifer; Eblen, John D.; S2CID 15797721.
- Dutour Sikirić, Mathieu; Itoh, Yoshiaki; Poyarkov, Alexei (2007), "Cube packings, second moment and holes", S2CID 15876010.
- MR 0585178.
- MR 0045727.
- Hartnett, Kevin (August 19, 2020), "Computer Search Settles 90-Year-Old Math Problem", Quanta Magazine.
- Iosevich, Alex; Pedersen, Steen (1998), "Spectral and tiling properties of the unit cube", International Mathematics Research Notices, 1998 (16): 819–828, S2CID 14232561.
- ISBN 0-8218-6609-5. See in particular pages 43, 114, 147, 156, and 161–163, describing different computational results on the Keller graphs included in this challenge set.
- S2CID 199547028.
- Lagarias, Jeffrey C.; Reeds, James A.; Wang, Yang (2000), "Orthonormal bases of exponentials for the -cube",MR 1758237.
- S2CID 6390600.
- Lagarias, J. C.; Shor, P. W.(1994), "Cube-tilings of and nonlinear codes",MR 1273224.
- Łysakowska, Magdalena; Przesławski, Krzysztof (2011), "On the structure of cube tilings and unextendible systems of cubes in low dimensions", .
- Łysakowska, Magdalena; Przesławski, Krzysztof (2012), "Keller's conjecture on the existence of columns in cube tilings of ", S2CID 14016886
- Mackey, John (2002), "A cube tiling of dimension eight with no facesharing", MR 1920144.
- Perron, Oskar (1940a), "Über lückenlose Ausfüllung des -dimensionalen Raumes durch kongruente Würfel", S2CID 186236462.
- Perron, Oskar (1940b), "Über lückenlose Ausfüllung des -dimensionalen Raumes durch kongruente Würfel. II", S2CID 123877436.
- Robinson, Raphael M. (1979), "Multiple tilings of -dimensional space by unit cubes", S2CID 123242152.
- 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" (PDF), S2CID 122364522.
- 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, S2CID 120163301.
- 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", MR 2133310.