Keller's conjecture
Encyclopedia
In geometry, Keller's conjecture is the conjecture introduced by that in any tiling
of Euclidean space
by identical hypercube
s 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. This was shown to be true in dimensions at most 6 by . However, for higher dimensions it is false, as was shown in dimensions at least 10 by and in dimensions at least 8 by , using 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 is now resolved for all dimensions, Keller's original cube-tiling conjecture remains open in dimension 7.
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.
, , and give surveys of work on Keller's conjecture and related problems.
s 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 hypercube
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
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. 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
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.
, and from there into a problem in graph theory
.
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, form an abelian group, and certain elements of this group correspond to the positions of the tiles. Hajós defines a family of subsets Ai of an abelian group to be a factorization if each element of the group has a unique expression as a sum a0 + a1 + ..., where each ai belongs to Ai. With this definition, Hajós' reformulated conjecture is that, whenever an Abelian group has a factorization in which the first set A0 may be arbitrary but each subsequent set Ai takes the special form {0, gi, 2gi, 3gi, ..., (qi − 1)gi}, then at least one of the elements qigi must belong to A0 −A0 (the difference set
of A0 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
s of order four, and with each qi = 2.
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 4n elements (m1,...,mn) 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 two in at least one coordinate. Corrádi and Szabó showed that the maximum clique in this graph has size at most 2n, 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, and the condition that the clique has size 2n implies that the cubes within any period of the tiling have the same total volume as the period itself, which together with the fact that they don't overlap 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.
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, reduced the dimension in which a counterexample to the conjecture is known by finding a clique of size 28 in the Keller graph of dimension eight.
Finally, showed that the Keller graph of dimension seven has a maximum clique of size 124 < 27. Thus, the same approach does not lead to a counterexample to the cube-tiling conjecture in this dimension However, reducing the problem from cube tilings to cliques may entail an increase in dimension, so it may be possible for the cube-tiling conjecture to be false in dimension seven even though the graph-clique formulation of the conjecture turns out to be true in that dimension.
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
.
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 a four-dimensional counterexample was found Hajós in 1938. 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 .
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. showed more strongly that it is at most n − √n/3.
and found close connections between cube tilings and the spectral theory
of square-integrable function
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.
Tessellation
A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
of Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
by identical hypercube
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, perpendicular to each other and of the same length.An...
s 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. This was shown to be true in dimensions at most 6 by . However, for higher dimensions it is false, as was shown in dimensions at least 10 by and in dimensions at least 8 by , using 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 is now resolved for all dimensions, Keller's original cube-tiling conjecture remains open in dimension 7.
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
Lattice (group)
In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
, some cubes must meet face to face. It was proved by György Hajós
György Hajós
György Hajós was a Hungarian mathematician who worked in group theory, graph theory, and geometry.-Biography:...
in 1942.
, , and give surveys of work on Keller's conjecture and related problems.
Definitions
A family of closed setClosed 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...
s called tiles forms a tessellation
Tessellation
A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
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 hypercube
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, perpendicular to each other and of the same length.An...
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 (geometry)
In Euclidean geometry, a translation moves every point a constant distance in a specified direction. A translation can be described as a rigid motion, other rigid motions include rotations and reflections. A translation can also be interpreted as the addition of a constant vector to every point, or...
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. 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
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
Pythagorean tiling
In geometry, the Pythagorean tiling or two squares tessellation is a tessellation of the plane by squares of two different sizes, in which each square touches four squares of the other size on its four sides. A tiling of this type may be formed by squares of any two different sizes...
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 theoryGroup theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
, and from there into a problem in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
.
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, form an abelian group, and certain elements of this group correspond to the positions of the tiles. Hajós defines a family of subsets Ai of an abelian group to be a factorization if each element of the group has a unique expression as a sum a0 + a1 + ..., where each ai belongs to Ai. With this definition, Hajós' reformulated conjecture is that, whenever an Abelian group has a factorization in which the first set A0 may be arbitrary but each subsequent set Ai takes the special form {0, gi, 2gi, 3gi, ..., (qi − 1)gi}, then at least one of the elements qigi must belong to A0 −A0 (the difference set
Sumset
In additive combinatorics, the sumset of two subsets A and B of an abelian group G is defined to be the set of all sums of an element from A with an element from B...
of A0 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
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
s of order four, and with each qi = 2.
Keller graphs
reformulated Szabó's result as a condition about the existence of a large cliqueClique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
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 4n elements (m1,...,mn) 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 two in at least one coordinate. Corrádi and Szabó showed that the maximum clique in this graph has size at most 2n, 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, and the condition that the clique has size 2n implies that the cubes within any period of the tiling have the same total volume as the period itself, which together with the fact that they don't overlap 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.
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, reduced the dimension in which a counterexample to the conjecture is known by finding a clique of size 28 in the Keller graph of dimension eight.
Finally, showed that the Keller graph of dimension seven has a maximum clique of size 124 < 27. Thus, the same approach does not lead to a counterexample to the cube-tiling conjecture in this dimension However, reducing the problem from cube tilings to cliques may entail an increase in dimension, so it may be possible for the cube-tiling conjecture to be false in dimension seven even though the graph-clique formulation of the conjecture turns out to be true in that dimension.
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
Benchmark (computing)
In computing, a benchmark is the act of running a computer program, a set of programs, or other operations, in order to assess the relative performance of an object, normally by running a number of standard tests and trials against it...
for clique-finding algorithms
Clique problem
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
.
Related problems
As describes, Hermann MinkowskiHermann Minkowski
Hermann Minkowski was a German mathematician of Ashkenazi Jewish descent, who created and developed the geometry of numbers and who used geometrical methods to solve difficult problems in number theory, mathematical physics, and the theory of relativity.- Life and work :Hermann Minkowski was born...
was led to a special case of the cube-tiling conjecture from a problem in diophantine approximation
Diophantine approximation
In number theory, the field of Diophantine approximation, named after Diophantus of Alexandria, deals with the approximation of real numbers by rational numbers....
. One consequence of Minkowski's theorem
Minkowski's theorem
In mathematics, Minkowski's theorem is the statement that any convex set in Rn which is symmetric with respect to the origin and with volume greater than 2n d contains a non-zero lattice point...
is that any lattice
Lattice (group)
In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
(normalized to have determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
one) must contain a nonzero point whose Chebyshev distance
Chebyshev distance
In mathematics, Chebyshev 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...
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
Triangular matrix
In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where either all the entries below or all the entries above the main diagonal are zero...
, with ones on its main diagonal and numbers less than one away from the diagonal. György Hajós
György Hajós
György Hajós was a Hungarian mathematician who worked in group theory, graph theory, and geometry.-Biography:...
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 a four-dimensional counterexample was found Hajós in 1938. 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 .
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. showed more strongly that it is at most n − √n/3.
and found close connections between cube tilings and the spectral theory
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 studies of linear algebra and the solutions of...
of square-integrable function
Square-integrable function
In mathematics, a quadratically integrable function, also called a square-integrable function, is a real- or complex-valued measurable function for which the integral of the square of the absolute value is finite...
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.