
In
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, Keller's conjecture is the conjecture that in any
tiling
Tiling may refer to:
*The physical act of laying tiles
*Tessellations
Computing
*The compiler optimization of loop tiling
* Tiled rendering, the process of subdividing an image by regular grid
*Tiling window manager
People
* Heinrich Sylvester ...
of -dimensional
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean sp ...
by identical
hypercube
In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions ...
s, there are two hypercubes that share an entire -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 , after whom it is named. A breakthrough by showed that it is false in ten or more dimensions, and after subsequent refinements, it is now known to be true in spaces of dimension at most seven and false in all higher dimensions. The proofs of these results use a reformulation of the problem in terms of the
clique number of certain graphs now known as Keller graphs.
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
György Hajós (February 21, 1912, Budapest – March 17, 1972, Budapest) was a Hungarian mathematician who worked in group theory, graph theory, and geometry..
Biography
Hajós was born February 21, 1912, in Budapest; his great-grandfathe ...
in 1942.
, , and give surveys of work on Keller's conjecture and related problems.
Statement
A
tessellation
A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of ge ...
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 set
In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric spac ...
s, 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
hypercube
In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions ...
s of the same dimension as the space. As formulates the problem, a ''cube tiling'' is a tiling by congruent hypercubes in which the tiles are additionally required to all be
translations
Translation is the communication of the Meaning (linguistic), meaning of a #Source and target languages, source-language text by means of an Dynamic and formal equivalence, equivalent #Source and target languages, target-language text. The ...
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, 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 -dimensional hypercube has faces of dimension 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 ()-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: 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.
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 geometry, the Weaire–Phelan structure is a three-dimensional structure representing an idealised foam of equal-sized bubbles, with two different shapes. In 1993, Denis Weaire and Robert Phelan found that this structure was a better solution ...
, 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.
Group-theoretic reformulation
Keller's conjecture was shown to be true in dimensions at most six by . 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
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
and, from there, into a problem in
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
.
[
first reformulated Keller's conjecture in terms of factorizations of ]abelian group
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is com ...
s. 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 of an abelian group to be a ''factorization'' if each element of the group has a unique expression as a sum , where each belongs to . With this definition, Hajós' reformulated conjecture is that whenever an Abelian group has a factorization in which the first set may be arbitrary but each subsequent set takes the special form for some element of , then at least one element must belong to (the difference set
In combinatorics, a (v,k,\lambda) difference set is a subset D of size k of a group G of order v such that every nonidentity element of G can be expressed as a product d_1d_2^ of elements of D in exactly \lambda ways. A difference set D is said to ...
of with itself).[
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 group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bi ...
s of order four, with each .
Keller graphs
reformulated Szabó's result as a condition about the existence of a large clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popula ...
in a certain family of graphs, which subsequently became known as the Keller graphs. More precisely, the vertices of the Keller graph of dimension are the elements where each 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 and 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 vertices differ in two coordinates implies that these cubes cannot meet face-to-face. The condition that the clique has size 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 do not overlap, this implies that the cubes placed in this way tile space without meeting face-to-face.
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, 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, 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
A computer-assisted proof is a mathematical proof that has been at least partially generated by computer.
Most computer-aided proofs to date have been implementations of large proofs-by-exhaustion of a mathematical theorem. The idea is to use a ...
in 2019 used Keller graphs to establish that the conjecture holds true in seven dimensions. 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.
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.[; , "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."]
Related problems
As describes, Hermann Minkowski
Hermann Minkowski (; ; 22 June 1864 – 12 January 1909) was a German mathematician and professor at Königsberg, Zürich and Göttingen. He created and developed the geometry of numbers and used geometrical methods to solve problems in numb ...
was led to a special case of the cube-tiling conjecture from a problem in diophantine approximation
In number theory, the study of Diophantine approximation deals with the approximation of real numbers by rational numbers. It is named after Diophantus of Alexandria.
The first problem was to know how well a real number can be approximated by ...
. One consequence of Minkowski's theorem is that any lattice (normalized to have determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if ...
one) must contain a nonzero point whose Chebyshev distance
In mathematics, Chebyshev distance (or Tchebychev distance), maximum metric, or L∞ metric is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension. It is ...
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
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal ar ...
, with ones on its main diagonal and numbers less than one away from the diagonal. György Hajós
György Hajós (February 21, 1912, Budapest – March 17, 1972, Budapest) was a Hungarian mathematician who worked in group theory, graph theory, and geometry..
Biography
Hajós was born February 21, 1912, in Budapest; his great-grandfathe ...
proved Minkowski's conjecture in 1942 using Hajós's theorem In group theory, Hajós's theorem states that if a finite abelian group is expressed as the Cartesian product of simplexes, that is, sets of the form \ where e is the identity element, then at least one of the factors is a subgroup. The theorem wa ...
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 -fold covering of space (that is, all but a measure-zero subset of the points in the space must be interior to exactly 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. characterized the combinations of and the dimension that permit a counterexample. Additionally, combining both Furtwängler's and Keller's conjectures, Robinson showed that -fold square coverings of the Euclidean plane must include two squares that meet edge-to-edge. However, for every and every , there is a -fold tiling of -dimensional space by cubes with no shared faces.
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 is at most seven, this maximum dimension is just , by the proofs of Keller's conjecture for those small dimensions, and when is at least eight, then this maximum dimension is at most . showed that it is at most , stronger for ten or more dimensions.
and found close connections between cube tilings and the spectral theory In mathematics, spectral theory is an inclusive term for theories extending the eigenvector and eigenvalue theory of a single square matrix to a much broader theory of the structure of operators in a variety of mathematical spaces. It is a result ...
of square-integrable function
In mathematics, a square-integrable function, also called a quadratically integrable function or L^2 function or square-summable function, is a real- or complex-valued measurable function for which the integral of the square of the absolute val ...
s on the cube.
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
Branko Grünbaum ( he, ברנקו גרונבאום; 2 October 1929 – 14 September 2018) was a Croatian-born mathematician of Jewish descent[G. C. Shephard
Geoffrey Colin Shephard is a mathematician who works on convex geometry and reflection groups. He asked Shephard's problem on the volumes of projected convex bodies, posed another problem on polyhedral nets, proved the Shephard–Todd theorem in ...](_blank)
found a tiling of three-dimensional space by parallelepiped
In geometry, a parallelepiped is a three-dimensional figure formed by six parallelograms (the term '' rhomboid'' is also sometimes used with this meaning). By analogy, it relates to a parallelogram just as a cube relates to a square. In Euclid ...
s with 60° and 120° face angles in which no two parallelepipeds share a face.
Notes
References
*
*
*.
*.
*.
*.
*.
*.
*.
*. See in particular pages 43, 114, 147, 156, and 161–163, describing different computational results on the Keller graphs included in this challenge set.
*.
*.
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*.
*.
*.
{{Good article
Cubes
Tessellation
Parametric families of graphs
Disproved conjectures
Computer-assisted proofs