More on high-dimensional cubes

In a previous post we discussed how the unit cube, simple as it is to define, exhibits some surprising phenomena. In this post I would like to highlight some fascinating questions, some of which are surprisingly open.

Cross-sections

A first natural question one might ask: how large or small can the cross-sections of the unit cube be?

Let $\overline{B^j}$ denote the $j$-dimensional ball of unit $j$-dimensional volume and centred at the origin of the space and let $\chi(V, x)$ denote the characteristic function of a set $V$. 

Theorem 1 (Vaaler): Suppose that $n_1, n_2, \cdots, n_j$ are positive integers satisfying $n = n_1 + n_2 + \cdots + n_j$, $D = \overline{B^{n_1}} \oplus \overline{B^{n_2}} \oplus \cdots \oplus \overline{B^{n_j}} \subset E^n$, and $A$ is an $i \times n$ real matrix of rank $i$. Then we have
\[
\int_{E^i} \chi(D, xA)  dx \geq |AA'|^{-\frac{1}{2}},
\]
where $A'$ is the transpose of $A$.

The proof requires some involved analysis. Taking $n_1 = n_2 = \cdots = n_n = 1$ and choosing $A$ such that its rows form an orthonormal basis for $H^i$ in $E^n$, then we have $D = I^n$, $|AA'| = 1$ and
\[
\int_{E^i} \chi(D, xA)  dx = v_i (I^n \cap H^i).
\]

Thus, we have the following as a corollary (it was previously known as Good's conjecture).

Corollary 2: If $1 \leq i \leq n - 1$, then
\[
v_i (I^n \cap H^i) \geq 1.
\]

Projections

What is the maximum (minimum) area of an $i$-dimensional projection of $I^n$?

It is known that the maximum area of a two-dimensional cross section of $I^3$ is $\sqrt{2}$. However, by routine computation one can deduce that the maximum area of a two-dimensional projection of $I^3$ is $\sqrt{3}$. This example does show the essential difference between cross sections and projections of $I^n$. In addition, as one will see, while the key method to deal with the cross sections is analytic the basic technique for projections is algebraic.

Let $H^i$ denote an $i$-dimensional hyperplane containing $o$ and let $P_i$ denote the orthogonal projection from $I^n$ to $H^i$. It is easy to see that $P_i$ is a polytope and
\[
I^n \cap H^i \subseteq P_i
\]
holds for every $H^i$. Therefore, by Vaaler's Theorem 1 we have the following lower bound for $v_i(P_i)$.

Theorem 3:(Chakerian and Filliman) If $1 \leq i \leq n-1$, for any $i$-dimensional orthogonal projection $P_i$ of $I^n$ we have
\[
v_i(P_i) \geq 1,
\]
where the equality holds if and only if $H^i$ is spanned by $i$ axes of $E^n$.

The upper bounds are still open.

Hadamard matrices

We start with the natural question of: what is the largest volume of a $k$-dimensional simplex in the $n$-cube?

Let \(S^{*}\) denote a \(k\)-dimensional simplex with vertices \(\mathbf{v}_{0}=(0,0,\ldots,0)\), \(\mathbf{v}_{1}=(1,0,\ldots,0)\), \ldots, \(\mathbf{v}_{k}=(0,0,\ldots,1)\) in the \(k\)-dimensional Euclidean space \(E^{k}\). Then it is well known that

\[v_{k}(S^{*})=\int_{S^{*}}d\mathbf{x}=\int\cdots\int_{\sum x_{i}\leq 1,\ x_{i} \geq 0}dx_{1}\cdots dx_{k}=\tfrac{1}{k!}.\]

Let \(S\) be a \(k\)-dimensional simplex with vertices \(\mathbf{a}_{0}=(0,0,\ldots,0)\), \(\mathbf{a}_{1}=(a_{11}, a_{12},\ldots,a_{1n})\), \ldots, \(\mathbf{a}_{k}=(a_{k1},a_{k2},\ldots,a_{kn})\) in the \(n\)-dimensional Euclidean space \(E^{n}\). For convenience, we assume that \(\mathbf{a}_{1}\), \(\mathbf{a}_{2}\), \ldots, \(\mathbf{a}_{k}\) are linearly independent; that is

\[v_{k}(S)>0.\]


Theorem 4: \[v_{k}(S)=\tfrac{1}{k!}\sqrt{\det(A_{k}A_{k}^{\prime})}.\]

Proof: Let \(H\) denote the \(k\)-dimensional subspace spanned by \(\mathbf{a}_{1}\), \(\mathbf{a}_{2}\), \ldots, \(\mathbf{a}_{k-1}\), and \(\mathbf{a}_{k}\), and let \(H^{\prime}\) denote the \((n-k)\)-dimensional subspace which is perpendicular with \(H\). In other words

\[H=\left\{\sum_{i=1}^{k}\lambda_{i}\mathbf{a}_{i}:\ \lambda_{i}\in R\right\}\]

and

\[H^{\prime}=\Bigl\{\mathbf{x}\in E^{n}:\ \langle\mathbf{x},\mathbf{y}\rangle=0 \textrm{ for all }\mathbf{y}\in H\Bigr\}.\]

Let \(\{a_{k+1}, a_{k+2}, \ldots, a_{n}\}\) be a basis of \(H^{\prime}\) such that

\[\langle a_{i}, a_{j}\rangle=\begin{cases}1&\text{if }i=j,\\ 0&\text{otherwise}\end{cases}\]

holds for \(k+1\leq i\leq j\leq n\). Then we define

\[S^{*}=\left\{S+\sum_{i=k+1}^{n}\lambda_{i}a_{i}:\;0\leq\lambda_{i}\leq 1\right\}.\]

It is easy to see that

\[v_{n}(S^{*})=v_{k}(S).\]

Let \(A\) denote the \(n\times n\) matrix with entries \(a_{ij}\), let \(A_{k}\) denote its \(k\times n\) sub-matrix consisting of the first \(k\) rows, and let \(T\) denote the linear transformation determined by

\[T(a_{i})={\bf e}_{i},\quad i=1, 2, \ldots, n,\]

where \(\{{\bf e}_{1}, {\bf e}_{2}, \ldots, {\bf e}_{n}\}\) is an orthonormal basis of \(E^{n}\). Thus we have

\[T(S^{*})=\left\{S^{*}+\sum_{i=k+1}^{n}\lambda_{i}{\bf e}_{i}:\;0\leq\lambda_{i} \leq 1\right\}\]

and therefore

\begin{align*} v_{k}(S)&=v_{n}(S^{*})=\int_{S^{*}}d{\bf x}=|\det(A)|\int_{T(S^{*})}d{\bf x}\\
&=\tfrac{1}{k!}\cdot|\det(A)|. \tag{1}
\end{align*}

It follows from the definition of $H'$ and orthogonality of the basis that

\[AA^{\prime}=\begin{pmatrix}A_{k}A_{k}^{\prime}&0\\ 0&I_{n-k}\end{pmatrix}\]

and therefore

\[\det(AA^{\prime})=\det(A_{k}A_{k}^{\prime}).\]
    This and  (1) prove the result. $\blacksquare$

Let \({\bf a}_{0}=(0, 0, \ldots, 0)\), \({\bf a}_{1}=(a_{11}, a_{12}, \ldots, a_{1n})\), \ldots, \({\bf a}_{k}=(a_{ki}, a_{k2}, \ldots, a_{kn})\) be \(k+1\) vertices of \(\overline{I^{n}}\), let \(S\) denote the simplex determined by them, and let \(A\) denote the \(k\times n\) matrix with entries \(a_{ij}\), where \(i=1, 2, \ldots, k\) and \(j=1, 2, \ldots, n\). Clearly, for any fixed \(i\) and \(j\), \(a_{ij}\) is either zero or one, and therefore \(A\) is a binary matrix. By theorem 4, we can restate the problem on volumes of simplices as: 

Determine the values of\[\theta(n,k)=\max\Bigl\{\det(AA^{\prime})\Bigr\},\]where the maximum is over all \(k\times n\) binary matrices.

Let \(S\) denote a simplex with \(n+1\) vertices \(\mathbf{a}_{0}=(a_{01},a_{02},\ldots,a_{0n})\), \(\mathbf{a}_{1}=(a_{11},a_{12},\ldots,a_{1n}),\ldots,\mathbf{a}_{n}=(a_{n1},a_{ n2},\ldots,a_{nn})\) in \(E^{n}\). We define \(a_{00}=a_{10}=\ldots=a_{n0}=1\) and let \(A\) denote the \((n+1)\times(n+1)\) matrix with entries \(a_{ij}\), where \(i,j=0,1,\ldots,n\). It is easy to see that

\[|\det(A)|=\begin{vmatrix}1&a_{01}&\cdots&a_{0n}\\ 0&a_{11}-a_{01}&\cdots&a_{1n}-a_{0n}\\ \vdots&\vdots&\ddots&\vdots\\ 0&a_{n1}-a_{01}&\cdots&a_{nn}-a_{0n}\end{vmatrix}=n!\cdot v_{n}(S).\]

On the other hand, when \(S\) is a vertex simplex of \(I^{n}\), multiplying \(a_{ij}\) \((i=0,1,\ldots,n; j=1,2,\ldots,n)\) by \(2\) we get an \((n+1)\times(n+1)\) matrix with \(\pm 1\) entries. Thus, by Theorem 3.1, the special case \(k=n\) of the question that spawned this section is equivalent to the following matrix problem.

What is the maximum determinant of an $(n + 1) \times (n + 1)$ matrix with $\pm1$ entries?

Remark: (Williamson, 1946) Let \(\theta_{n}\) denote the maximum determinant of an \(n\times n\) binary matrix and let \(\theta_{n}^{*}\) denote the maximum determinant of an \(n\times n\) matrix of \(\pm 1\) entries. Then

\[\theta_{n+1}^{*}=2^{n}\theta_{n}.\]

Therefore, to determine the \(n\)-dimensional maximal vertex simplex of \(I^{n}\), we can deal with either \(n\times n\) binary matrices or \((n+1)\times(n+1)\) matrices of \(\pm 1\) entries.

Theorem 5: For any $n \times n$ matrix $A$ with $\pm 1$ entries we have
\[
\det(AA') \leq 
\begin{cases} 
n^n & \text{if } n \equiv 0 \pmod{4}, \\
(2n-1)(n-1)^{n-1} & \text{if } n \equiv 1 \pmod{4}, \\
{4(n-1)^2(n-2)^{n-2}} & \text{if } n \equiv 2 \pmod{4}, \\
\frac{4\cdot 11^6}{7^n}n^7(n-3)^{n-7} & \text{if } n \equiv 3 \pmod{4}, \\
\end{cases}
\]

The proof of this theorem is very complicated, especially the fourth case. It is based on detailed analysis of the structure of $AA'$ and induction. For example, one can observe that, in the fourth case, every element of $AA'$ is $3 \mod 4$. Then we can try to get an upper bound for $\det(C)$ instead, where $C$ is a symmetric metric with elements congruent to $3 \mod 4$.  It is very surprising indeed that all of the first three upper bounds can be attained at infinitely many $n$, though they are very different.

The first case is the well-known Hadamard inequality. An $n \times n$ matrix with $\pm 1$ entries is called a Hadamard matrix if $AA' = nI_n$. By Williamson's remark one can deduce that Hadamard matrices only exist if $n \equiv 0 \pmod{4}$. Paley conjectured that the condition is also sufficient, but this remains open. On the other hand, we have the following surprising connection:


Grigoriev's theorem:  There is an $n$-dimensional regular vertex simplex in $I^n$ if and only if there exists an $(n+1) \times (n+1)$ Hadamard matrix.

Proof:Let \(A\) be an \((n+1)\times(n+1)\) Hadamard matrix with entries \(a_{ij}\), where both \(i\) and \(j\) run from \(0\) to \(n\). If \(a_{i0}=1\) and  \[a_i=(a_{i1},a_{i2},\ldots,a_{in})\]  
for \(i=0,1,\ldots,n\), then by definition it follows that  
\[\langle a_i,a_j\rangle=
\begin{cases} 
n&\text{if }i=j,\\
-1&\text{otherwise},
\end{cases}\]  
and thus  
\[\|a_i-a_j\|=\sqrt{\langle a_i-a_j,a_i-a_j\rangle}=\sqrt{2n+2}\]  
holds for every pair of distinct indices \(i\) and \(j\). Therefore, the simplex with vertices \(a_0,a_1,\ldots,a_{n-1}\), and \(a_n\) is regular. On the other hand, if \(I^n\) contains an \(n\)-dimensional regular vertex simplex, then we can construct an \((n+1)\times(n+1)\) Hadamard matrix. $\blacksquare$

Constructions

Here are two constructions that give Hadamard matrices that I learned from a course of Tim Gowers. The first is a very simple inductive one. Let \( W_0 \) be the \( 1 \times 1 \) matrix (1) and in general define
\[W_m = \begin{pmatrix} W_m & W_m \\ W_m & -W_m \end{pmatrix}.\]
It is straightforward to check the following facts.

•  \( W_m \) is a \( 2^m \times 2^m \) matrix with \(\pm 1\) entries.
• The first row of \( W_m \) consists entirely of 1s.
• The rows of \( W_m \) are orthogonal to each other.

The matrices \( W_m \) are called Walsh matrices. If \( n = 2^m \), we have an \( n \times n \) \(\pm 1\) matrix \( W \) with first row consisting of 1s. If we now take \( A_i \) to be \( \{j : W_{ij} = 1\} \) and \( B_i = \{j : W_{ij} = -1\} \) for \( i = 2, 3, \ldots , n \), we obtain \( 2(n - 1) \) sets \( A_2, \ldots , A_n, B_2, \ldots , B_n \) of size \( n/2 \) such that \( A_i \cap B_i = \emptyset \) for each \( i \) and otherwise any two distinct sets from the collection have intersection of size \( n/4 \). (The fact that the sets have size \( n/2 \) follows is equivalent to the fact that the later rows of \( H_n \) are orthogonal to the first row.)


The second construction is algebraic. Recall that if \( 0 \leq x < p \), then the Legendre symbol \( \left( \frac{x}{p} \right) \) stands for 1 if \( x \) is a quadratic residue, \(-1 \) if \( x \) is a non-residue, and 0 if \( x = 0 \). Let \( p \) be a prime of the form \( 4m + 3 \), let \( n = p + 1 \) and define the Paley matrix \( P = P_n \) by setting \( P_{xy} = \left( \frac{x - y}{p} \right) \) if \( 0 \leq x, y \leq p - 1 \) and \( x \neq y \), \(-1 \) if \( x = y \), and 1 if either of \( x, y \) is equal to \( p \). In other words, we first create a \( p \times p \) matrix by setting \( P_{xy} \) to be 1 or -1 according to whether \( x - y \) is or is not a quadratic residue, considering 0 to be a non-residue for this purpose, and then we attach to it an extra row and column that consist of 1s.

Lemma 6: For every prime \(p\) and every \(d\neq 0 \bmod p\) we have that \(\sum_{x}\left(\frac{x}{p}\right)\left(\frac{x+d}{p}\right)=-1\), where the summation is over all \(x \bmod p\).

Proof: We shall make use of the fact that the function \(x\mapsto\left(\frac{x}{p}\right)\) is multiplicative.

\begin{align*}
\sum_{x}\left(\frac{x}{p}\right)\left(\frac{x+d}{p}\right) &= \sum_{x\neq 0,-d}\left(\frac{x^{2}}{p}\right)\left(\frac{1+dx^{-1}}{p}\right) \\
&= \sum_{x\neq 0,-d}\left(\frac{1+dx^{-1}}{p}\right).
\end{align*}

Now as \(x\) ranges over all values other than \(0\) or \(d\), \(1+dx^{-1}\) ranges over all values other than \(1\) or \(0\). But half the non-zero elements mod \(p\) are quadratic residues and \(1\) is a quadratic residue, so this last sum is equal to -1. $\blacksquare$

Corollary 7: The Paley matrix has orthogonal rows.

Proof: The inner product of two distinct rows of the Paley matrix is closely related to the sum calculated in Lemma 6. If neither row is the last, then it is of the form

\[\sum_{x\neq 0,-d}\left(\frac{x}{p}\right)\left(\frac{x+d}{p}\right)-\left(\frac{d}{p}\right)-\left(\frac{-d}{p}\right)+1,\]

since when \(x=0\) we replace \(\left(\frac{\cdot}{p}\right)\) by -1, and the product of the last entries in the two rows is 1. But \(p\equiv 3\bmod{4}\), so -1 is not a quadratic residue mod \(p\), from which it follows that \(\left(\frac{d}{p}\right)=-\left(\frac{-d}{p}\right)\). Therefore, by Lemma 6 (and the fact that \(\left(\frac{0}{p}\right)=0\)), the inner product is \(-1+1=0\).

If one of the rows is the last row, then we obtain the sum

\[-1+\sum_{x\neq 0}\left(\frac{x}{p}\right)+1.\]

Since exactly half the non-zero numbers mod \(p\) are quadratic residues, this is also 0. $\blacksquare$

Minkowski's conjecture

Let $I^2 + \Lambda$ be a lattice tiling in $E^2$ and let $b_1 = (1, \beta) \in \Lambda$ be a suitable point such that $I^2 + b_1$ meets $I^2$ at its boundary. If $\beta = 0$, then $I^2 + b_1$ meets $I^2$ at a whole edge. If $\beta \neq 0$, since $I^2 + \Lambda$ is a tiling in $E^2$, then we have $b_2 = (0, 1) \in \Lambda$ and therefore $I^2 + b_2$ meets $I^2$ at a whole edge. As a conclusion, if $I^2 + \Lambda$ is a lattice tiling of $E^2$, then $I^2$ meets one of its neighbors at a whole edge. By a similar argument this result can be easily extended to three dimensions. In 1896 Minkowski discovered this fact and promised to prove a similar statement in $E^n$. However, the promised proof did not appear. For this reason the $n$-dimensional case is known as Minkowski's conjecture. For convenience, we will call two $n$-dimensional cubes a twin whenever they share a whole facet.

Minkowski's conjecture: Every lattice tiling $I^n + \Lambda$ of $E^n$ has twins.

To approach this simple sounding conjecture in high dimensions, T. Schmidt proved the following intermediate result, which plays a very important role in the final proof of this conjecture.

Lemma 8: If there is a lattice tiling $I^{n}+\Lambda$ of $E^{n}$ without a twin, then there is a rational lattice tiling $I^{n}+\Lambda^{\prime}$ without a twin.

Of course, a rational lattice means all the lattice points have rational coordinates, or in other words it has a rational basis. Clearly, if $I^{n}+(a_{1},\cdots,a_{n})$ touches $I^{n}$ at its boundary and if $a_{1}$ is irrational, then $-1<a_{1}<1$ and therefore one can find a small $\epsilon$ such that $I^{n}+(a_{1}+\epsilon,\cdots,a_{n})$ touches $I^{n}$ at its boundary and $a_{1}+\epsilon$ is rational. Based on this observation the lemma can be proved by detailed analysis.

Let $\Lambda$ be a rational lattice with a basis $\mathbf{b}_{1}$, $\cdots$, $\mathbf{b}_{n}$, where
\[
\mathbf{b}_{i}=\left(\tfrac{c_{i1}}{d_{i1}},\cdots,\tfrac{c_{in}}{d_{in}}\right)
\]
and where $c_{ij}$ and $d_{ij}$ are integers. Let $q_{j}$ denote the common multiple of $d_{1j}$, $\cdots$, $d_{nj}$, and let $\overline{\Lambda}$ denote the lattice generated by $\mathbf{b}_{1}=\tfrac{1}{q_{1}}\mathbf{e}_{1}$, $\cdots$, $\mathbf{b}_{n}=\tfrac{1}{q_{n}}\mathbf{e}_{n}$, where $\mathbf{e}_{i}$ indicates the $i$-th unit axis. Then $\overline{\Lambda}/\Lambda$ can be uniquely expressed as
\[
\sum_{i=1}^{n}z_{i}\mathbf{\overline{b}}_{i}
\]
with $z_{i}\in \mathbb{Z}$ and $0\leq z_{i}\leq q_{i}-1$. Especially, we have $\mathbf{e}_{i}\in\Lambda$ for some $i$ whenever $I^{n}+\Lambda$ has a twin. Therefore Hajos [46] was able to reformulate Minkowski's conjecture into the following version.

Algebraic version of Minkowski's conjecture: Let $G$ be a finite abelian group with unit $1$. If $\mathbf{g}_{1}$, $\cdots$, $\mathbf{g}_{n}$ are elements of $G$ and $q_{1}$, $\cdots$, $q_{n}$ are positive integers such that each element of $G$ can be uniquely written in the form
\[
\prod_{i=1}^{n}\mathbf{g}_{i}^{z_{i}},\qquad 0\leq z_{i}\leq q_{i}-1,
\]
then $\mathbf{g}_{i}^{q_{i}}=1$ for some $i$ with $1\leq i\leq n$.

Let $\mathbb{Z}(G)$ denote the \emph{group ring} generated by $G$. In other words,
\[
\mathbb{Z}(G)=\Bigl\{\sum z_{i}\mathbf{g}_{i}:~z_{i}\in \mathbb{Z};~\mathbf{g}_{i}\in G\Bigr\}
\]
in which the addition is defined by
\[
\sum z_{i}\mathbf{g}_{i}+\sum z^{\prime}_{i}\mathbf{g}_{i}=\sum(z_{i}+z^{\prime}_{i})\mathbf{g}_{i}
\]
and the multiplication is defined by
\[
\Bigl(\sum z_{i}\mathbf{g}_{i}\Bigr)\Bigl{(}\sum z^{\prime}_{i}\mathbf{g}_{i}\Bigr{)}=\sum\left(\sum_{\mathbf{g}_{j}\mathbf{g}_{k}=\mathbf{g}_{i}}z_{j}z^{\prime}_{k}\right)\mathbf{g}_{i}.
\]

In 1942, by a detailed study of group rings, Hajos was able to prove Minkowski's conjecture.

The Minkowski-Hajos theorem: Every lattice tiling $I^{n}+\Lambda$ of $E^{n}$ has twins.

Keller's conjecture

Keller's conjecture: Every translative tiling $I^n + X$ of $E^n$ has a twin.

Similar to Minkowski's conjecture, Keller's conjecture also has an algebraic version, which was discovered by Hajós in 1950.

Algebraic version of Keller's conjecture:  Let $G$ be an abelian group with basis elements $g_1, \cdots, g_n$ of orders $2q_1, \cdots, 2q_n$ respectively. If $G = HA_1 \cdots A_n$ is a factorization, where $|H| = 2^n$ and $A_i = \{1, g_i, \cdots, g_i^{q_i-1}\}$, then
\[
H^{-1}H \cap \{g_1^{q_1}, \cdots, g_n^{q_n}\} \neq \emptyset.
\]

In 1940 O. Perron proposed an idea to reduce Keller's conjecture into finitely many cases for each $n$. In 1986 S. Szabó made this idea more explicit and proved the following statement.

Lemma 9: (Perron and Szabó) If Keller's conjecture is false in $E^n$, then there exists a counterexample tiling $I^m + X$ in some $E^m$ with $m \geq n$ such that $X \subseteq \frac{1}{2}\mathbb{Z}^m$ and $X$ is periodic with a period lattice containing $2\mathbb{Z}^m$.

Later, K. Corradi and S. Szabó introduced a graph $G_n$ and a graph-theoretic version of this lemma. The vertices of $G_n$ are vectors of length $n$ with entries from $\{0, 1, 2, 3\}$. Two such vectors $u$ and $v$ are adjacent if and only if $u_i - v_i \equiv 2 \pmod{4}$ for some $i$ and $u_j \neq v_j$ for some $j, j \neq i$.
 

Lemma 10: (Corradi and Szabó) There is a counterexample for Keller's conjecture if and only if for some $n$ the graph $G_n$ has a clique of size $2^n$.

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 2n 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.

In 1992 Lagarias and Shor 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, in 2002 Mackey 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, in 2011 it was shown that the Keller graph of dimension seven has a maximum clique of size 124. Because this is less than $2^7 = 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. Therefore, the Keller conjecture is true in seven dimensions or fewer but is false when there are more than seven dimensions.

Further Strengthenings

A family of unit cubes $I^n + Y$ will be called a $k$-fold tiling of $E^n$ if every point $x \notin \partial(I^n) + Y$ lies in exactly $k$ cubes. Clearly a tiling is a 1-fold tiling. To generalise Minkowski's conjecture to $k$-fold lattice tilings, Furtwängler made the following ambitious conjecture in 1936 and proved it for $n \leq 3$.

Furtwängler's conjecture: Every $k$-fold lattice tiling $I^n + \Lambda$ of $E^n$ has a twin.

When G. Hajós did prove Minkowski's conjecture, unaware of Furtwängler's work, he studied this generalisation again and restated it in the following version.

Algebraic version of Furtwängler's conjecture:If each element $g$ of a finite abelian group $G$ is expressible in exact $k$ distinct ways as a product of elements coming from the cyclic subsets $A_1, A_2, \cdots, A_n$ respectively, where $A_i = \{1, g_i, \cdots g_i^{q_i-1}\}$, then $g_i^{q_i} = 1$ for some $i, 1 \leq i \leq n$.

By a comprehensive study of the algebraic version, in 1979 R.M. Robinson was able to determine all the integer pairs $\{n,k\}$ such that Furtwängler's conjecture is false. Thus Furtwängler's conjecture has been completely solved.

Robinson's theorem: There is a $k$-fold lattice tiling $I^{n}+\Lambda$ of $E^{n}$ which has no twin if and only if one of the following holds:

•  $n=4$ and $k$ is a multiple of a square of an odd prime.
• $n=5$ and $k=3$ or $k\geq 5$.
• $n\geq 6$ and $k\geq 2$.