Mazzola, Guerino / Noll, Thomas / Lluis-Puebla, Emilio: Perspectives in Mathematical and Computational Music Theory

(Minkowski, 1896). Recalling the story of the last theorem of Fermat, which was solved more than century and a half after its first formulation, we could call this problem the last theorem of Minkowski. For, although he was determined to furnish a proof in a short time, the problem »turned out to be unexpectedly difficult« (Robinson, 1979). So difficult, in fact, that Hajós’ solution to Minkowski’s problem has been described as »the most dramatic work in factoring« (Stein, 1974). I will not describe in details the transition from the original number-theoretical conjecture to Hajós’ final formulation (and solution) in terms of the tiling of finite abelian groups. Rather, I will look at it »as the metamorphosis of a caterpillar to a butterfly« (Stein, 1974), from an advanced geometrical state concerned with tiling the $n$ -dimensional Euclidean space $n |R$ with a family of congruent cubes (i.e. cubes which are translated of each other). Some preliminary definitions are necessary. By lattice tiling (or lattice tessellation) of the $n$ -dimensional Euclidean space, we mean a collection of congruent cubes that cover the space in such a way that the cubes do not have interior intersection and that the translation vectors form a lattice. This kind of lattice is sometimes called »simple«, to distinguish it from multiple tilings in which cubes can intersect in such a way that they are such that every point of the Euclidean space (which does not belong to the boundary of one cube) lies in exactly $k$ cubes ( $k < oo$ ). In this case we speak of a $k$ -fold tiling (or a tiling of multiplicity $k$ ).¹¹

¹¹: For a detailed account on the algebraic and geometric properties of cube tilings with respect to Minkowski’s conjecture and some possible generalisations see Szabó (1993) and Stein and Szabó (1994).

The first geometric formulation of the last theorem of Minkowski, which requires the »lattice property« is the following:
Minkowski’s Conjecture: in a simple lattice tiling of $| n R$ by unit cubes, some pairs of cubes must share a complete ( $n$ -1)-dimensional face.¹²

¹²: Such cubes are sometimes called »twin« (Szabó, 1993). Note that in general the latticity condition cannot be removed. Minkowski’s condition without latticity is historically due to O. H. Keller. He conjectured (Keller, 1930) that in any tiling of the $n$ -dimensional Euclidean space by unit cubes there exists at least a pair of cubes sharing a complete $(n- 1)$ -dimensional face. J. C. Lagarias and P. W. Shor proved that this conjecture is false for all $n > 10$ (Lagarias and Shor, 1992). The conjecture is true for $n< 6$ , as it was already known since 1940 (Perron, 1940) but the case $6< n <10$ remains open.

Let us consider Hajós’ translation of Minkowski’s conjecture in algebraic terms Hajós (1942) as it appears, for example, in Stein (1974). For an exposition of Hajós proof the reader should refer to Fuchs (1960); Robinson (1979); Rédei (1967); Stein and Szabó (1994).
Hajós Theorem:
let $G$ be a finite abelian group and let $a1,a2,...,an$ be $n$ elements of $G$ . Assume that $G$ can be factored into $n$ sets:

m1-1 m2-1 mn- 1 A1 = {1,a1,...,a1 },A2 = {1,a2,...,a2 },...,An = {1,an,...,an }

where $mi > 0,i = 1,2,...,n$ in such a way that each element $g$ of $G$ is uniquely expressible in the form:

g = ae1.ae2...aen, 1 2 n

$0 < ei < mi(i = 1,...,n,ai (- Ai)$ . Then at least one of the factors is a group (i.e. there is at least one integer i such that $mi ai = 1).$ ¹³

¹³: For a proof of Hajós’ Theorem, in the generalisation proposed by L. Rédei see Stein and Szabó (1994). A new axiomatic approach has been recently suggested by K. Corrádi and S. Szabó (Corrádi and Szabó, 1997).