A. F. Gametskii

On the Theory of Covering \(n\)-Dimensional Euclidean Space by Equal Balls

(Presented by Academician I. M. Vinogradov on 10 VII 1962)

A lattice covering of \(n\)-dimensional Euclidean space \(E^n\) by equal balls is a covering of the space \(E^n\) by equal balls such that the centers of the balls forming this covering constitute a lattice. Obviously, to every lattice \(\Gamma\) there corresponds a number \(R_\Gamma\) such that the balls of radius \(R_\Gamma\), with centers at the points of this lattice, cover the whole space \(E^n\), whereas balls of smaller radius do not cover it. In all that follows, by the words “lattice covering” we shall mean only lattice coverings of the space by balls having radius \(R = R_\Gamma\).

The density of a lattice covering is the ratio of the volume of an \(n\)-dimensional ball of radius \(R_\Gamma\) to the volume of a fundamental region of the lattice \(\Gamma\). Obviously, similar lattices give one and the same value of the covering density; therefore, in what follows, from each class of similar lattices we shall consider only one.

We denote by \(\Gamma_1^n\) the lattice of \(n\)-dimensional space constructed on a regular Zelling frame, i.e., on a Zelling frame with equal scalar products of its vectors. The metric form of the basic frame of this lattice, formed by any \(n\) vectors of this regular Zelling frame, is the so-called principal form of the first type of Voronoi \((^1)\) and has the form

\[ \sum_{i=1}^{n} n x_i^2 - \sum_{i=1}^{n} \sum_{j=1}^{n} x_i x_j \quad i \ne j. \tag{1} \]

Obviously, in the two-dimensional case \(\Gamma_1^2\) (this lattice is constructed on regular triangles) gives the minimum, and moreover the unique minimum, of the density of a covering of the plane by equal circles. Bambah showed \((^2)\) that in the three-dimensional case the lattice \(\Gamma_1^3\) gives the absolute minimum of the density of a lattice covering. He also, estimating the density of a lattice covering in four-dimensional space \((^3)\), put forward the conjecture that the lattice \(\Gamma_1^4\) gives the absolute minimum of the density of lattice coverings in four-dimensional space. On the other hand, Davenport \((^4)\), and later Watson \((^5)\), showed the existence, for large \(n\), of such lattices that give a covering density of space less than \((1.15)^n\) (Davenport) and \((1.107)^n\) (Watson). These numbers are less than the covering density corresponding to the lattice \(\Gamma_1^n\), equal to \((1.17)^n\). Very interesting results connected with estimating the density of arbitrary, not necessarily lattice, coverings of \(n\)-dimensional Euclidean space by equal balls were obtained by Coxeter, Few, and Rogers \((^6)\).

The main result of our paper is the following theorem.

Theorem. The lattice \(\Gamma_1^n\) corresponds to a local minimum of the density among lattice coverings of the space \(E^n\), i.e., the lattice \(\Gamma_1^n\) is one of the extreme lattices in the theory of coverings in the sense in which this term was used in the theory of packings by Korkin, Zolotarev, and Voronoi.

1. We denote by \(\Gamma\) a lattice of \(n\)-dimensional space and by \(D\) its Dirichlet region. Join the vertices of the Dirichlet region to its center and denote the lengths of these segments, henceforth called radii of the Dirichlet region, by \(R_\lambda\), where \(\lambda = 1, 2, \ldots, N\), and denote by \(N\) the number of vertices of the Dirichlet region. As is easy to see, the radius \(R_\Gamma\) defined above is found—

among the radii \(R_\lambda\) and is the largest of them. The problem of finding a lattice with the least density of the corresponding lattice covering reduces to finding a lattice that realizes the minimum of the expression
\[ \max_\lambda (R_\lambda^n/V), \]
or, what is the same thing,
\[ \max_\lambda (R_\lambda^2/\sqrt[n]{V^2}), \]
where \(V\) denotes the volume of the fundamental region of the lattice \(\Gamma\).

B. N. Delone proposed that, instead of the expression
\[ \max_\lambda (R_\lambda^n/V), \]
one should investigate for a minimum the quantity
\[ \sum_{\lambda=1}^{n} (R_\lambda^2/\sqrt[n]{V^2}). \]
The point is that the solution of this problem leads to the solution of the main problem in the case when the minimum is attained in a lattice for which all radii of the Dirichlet region are equal.

On the way to solving Delone’s problem, the author, for Dirichlet regions of lattices of the first type, found by complicated computations, for \(n=3\) and \(4\), the formula
\[ \sum_{\lambda=1}^{(n+1)!} R_\lambda^2 = -\frac{(n+1)!}{12\Delta} \left[ 2\sum_{i<j}^{n}\sum^{\,n+1} g_{ij}\Delta + \sum_{i<j}^{n}\sum^{\,n+1} g_{ij}^2 \frac{\partial \Delta}{\partial g_{ij}} \right], \tag{2} \]
where \(g_{ij}\) are the parameters of the reduced Selling frame (7), and noted that this formula has the following geometric meaning:
\[ \sum_{\lambda=1}^{(n+1)!} R_\lambda^2 = \frac{(n+1)!}{12} \left[ \sum_{i=1}^{n+1} a_i^2 + \sum_{t=1}^{\frac{(n+1)n}{2}} \alpha_t^2 \right], \tag{3} \]
where \(R_\lambda\) denote the radii of the Dirichlet region, \(a_i\) the lengths of the vectors of the reduced Selling frame, and \(\alpha_t\) the lengths of the edges of the Dirichlet region*. S. S. Ryshkov found a general geometric proof of formula (3), which is given in Sec. 4 only for the three-dimensional case. On the basis of the results of (8), this proof extends inductively to any natural number \(n\). The rather complicated induction mentioned uses the fact that an \(n\)-dimensional parallelohedron of the first type has faces that are \((n-1)\)-dimensional primitive parallelohedra of the first type, as well as faces that are prisms over \((n-2)\)-dimensional primitive parallelohedra of the first type.

1. Let \((\bar a_1,\bar a_2,\ldots,\bar a_{n+1})\) be a reduced Selling frame of a certain lattice \(\Gamma\) of the first type, and let \(g_{ij}=\bar a_i\bar a_j\) be the Selling parameters of this lattice. If the frame is chosen from the vectors \(\bar a_1,\bar a_2,\ldots,\bar a_{k-1},\bar a_{k+1},\ldots,\bar a_{n+1}\), then any quadratic form \(f\) of the first type can be written as \((1)\):
   \[ f=\sum_{i<j}\sum g_{ij}(x_i-x_j)^2,\qquad \text{where } x_k=0. \]
   The determinant \(\Delta\) of this form is the square of the volume of the Dirichlet region of the lattice \(\Gamma\).

Lemma 1. The square of the length of each edge \(\alpha\) of a Dirichlet region of the first type is expressed by the formula
\[ \alpha^2=-g_{ij}^2\Delta^{-1}\frac{\partial\Delta}{\partial g_{ij}}. \]

The lemma is proved in the same way as was done in (9) for three-dimensional space. On the basis of this lemma and the fact that
\[ \sum \bar a_i^2=-2\sum_{i<j}\sum g_{ij}, \]
formula (3) is written in the form (2).

Lemma 2. The partial derivative
\[ \partial^m\Delta/\partial g_{i_1j_1}\partial g_{i_2j_2}\cdots \partial g_{i_mj_m} \]
of order \(m\) of the determinant \(\Delta\) is, in absolute value, equal to the square of the volume of the fundamental parallelepiped of some \((n-m)\)-dimensional sublattice of the lattice \(\Gamma\).

The \((n-2)\)-dimensional sublattices whose squared volumes, by Lemma 2, are the second derivatives of the determinant \(\Delta\), split into two classes:

* Analogous formulas have been found for all four-dimensional parallelohedra.

sublattices of the first class are constructed on \((n-2)\) vectors of the original Selling frame, and sublattices of the second class are constructed on \((n-3)\) vectors of the original Selling frame of the lattice \(\Gamma\) and the vector \(\bar a_i+\bar a_k\).

For the principal form (1) of the first type, determined by the values \(g_{ij}=-1\), the following values of the quantities considered here hold:
\[ \Delta=(n+1)^{n+1},\qquad \frac{\partial\Delta}{\partial g_{ik}}=-2(n+1)^{n-2},\qquad \frac{\partial^2\Delta}{\partial g_{ik}\partial g_{sq}}=4(n+1)^{n-3}; \tag{4} \]
\[ \frac{\partial^2\Delta}{\partial g_{ik}\partial g_{iq}} =3(n+1)^{n-3}, \]
where \(i,k,s,q=1,2,\ldots,n+1;\ i\ne s;\ k\ne s;\ i\ne q;\ k\ne q,\ i<k;\ s<q\).

1. Proof of the theorem. The expression \(\mathfrak D\) from item 1, written for a Dirichlet region of the first type with the use of formula (2) and the equality \(V=\sqrt{\Delta}\), has the form
   \[ -\frac{(n+1)!}{12}\, \frac{ 2\sum_{i<j}\sum g_{ij}\Delta+\sum_{i<j}\sum g_{ij}^{2}\,\partial\Delta/\partial g_{ij} }{ \Delta^{\frac{n+1}{n}} }. \tag{5} \]

Let us split expression (5) into two summands \(F_1(M)\) and \(F_2(M)\):
\[ F_1(M)= -\frac{(n+1)!}{6}\cdot \frac{\sum_{i<j}\sum g_{ij}}{\Delta^{1/n}}, \qquad F_2(M)= -\frac{(n+1)!}{12}\cdot \frac{\sum_{i<j}\sum g_{ij}^{2}\,\partial\Delta/\partial g_{ij}} {\Delta^{\frac{n+1}{n}}}, \]
where by \(M=(g_{12},g_{13},\ldots,g_{n,n+1})\) we denote a point belonging to the domain of positive definite forms of the parameter space \(g_{12},g_{13},\ldots,g_{n,n+1}\). We shall show that on the surfaces \(\Delta=(n+1)^{n-1}\) and, respectively, \(g_{12}=-1\) of the parameter space, the functions \(F_1(M)\) and, respectively, \(F_2(M)\) have a minimum at the point
\[ M_1=(-1,-1,\ldots,-1). \]

Investigating the function \(F_1(M)\) for an extremum by the method of Lagrange multipliers, we obtain that the derivatives \(\partial\Delta/\partial g_{ij}\) are equal to one another. Considering the lattice reciprocal to the sought lattice \(\Gamma\), we obtain that all Selling parameters of the lattice \(\Gamma\) are equal to one another and, since \(\Delta=(n+1)^{n-1}\), are equal to minus one. Thus, the function \(F_1(M)\) on the surface \(\Delta=(n+1)^{n-1}\) has only one critical point. It turns out that when the point \(M\) tends to infinity in any direction along the surface \(\Delta=(n+1)^{n-1}\), the function \(F_1(M)\) tends to infinity. Hence, by the Weierstrass theorem, one may conclude that at the unique critical point of the function \(F_1(M)\) this function has the least value and, consequently, a minimum.

We now investigate the function \(F_2(M)\). Direct calculations give the following values of the derivatives of the function \(F_2(M)\) at the point \(M_1\):
\[ \frac{\partial F_2}{\partial g_{ij}}=0,\qquad \frac{\partial^2 F_2}{\partial g_{ij}^{2}} = \frac{4(n-1)(n+1)^{n-2}} {n\Delta^{\frac{n+1}{n}}}, \qquad \frac{\partial^2 F_2}{\partial g_{ij}\partial g_{lp}} = -\frac{4(n+1)^{n-3}} {n\Delta^{\frac{n+1}{n}}}, \]
\[ \frac{\partial^2 F_2}{\partial g_{ij}\partial g_{ip}} = -\frac{(n+4)(n+1)^{n-3}} {n\Delta^{\frac{n+1}{n}}}, \]
where \(i,j,l,p=1,2,\ldots,n+1;\ i\ne l;\ i\ne p;\ j\ne l;\ j\ne p;\ i<j,\ l<p\).

It follows from these formulas, in particular, that the point \(M_1\) is critical for the function \(F_2(M)\). Expanding the function \(F_2(M)\) at the point \(M_1\) in a Taylor series, after minor transformations the quadratic part of the expansion can be represented in the form
\[ \frac{1}{n\Delta^{\frac{n+1}{n}}} \left[ (n+4)\sum(\varepsilon_{ij}-\varepsilon_{lp})^2 + 4\sum(\varepsilon_{ij}-\varepsilon_{lp})^2 \right], \tag{6} \]

where \(i<j;\ l<p;\ i<p;\ i\ne l;\ j\ne l;\ j\ne p\), and the increments of the parameters \(g_{ij}\) are denoted by \(\varepsilon_{ij}\). Setting \(\varepsilon_{12}=0\) in formula (6), we easily verify the positive definiteness of the resulting form. Hence it follows that the function \(F_2(M)\) has a minimum at the point \(M_1\), and expression (5) has a minimum on the ray \(OM_1\). To complete the proof it remains to point out that the Dirichlet region of the lattice \(\Gamma_1^n\) is inscribed in a ball and, consequently, being a local solution of Delone’s problem, the lattice \(\Gamma_1^n\) is also a local solution of our main problem.

Fig. 1

We note that the density \(d\) of the lattice \(\Gamma_1^n\) is expressed by the formula

\[ d=I_n\left[n^n(n+2)^n/12^n(n+1)^{n-1}\right]^{1/2}, \]

where \(I_n\) is the volume of the \(n\)-dimensional unit ball.

1. Denote by \(\Pi\) the primitive \(n\)-dimensional parallelohedron that is the image, under an affine transformation \(\varphi\), of the Dirichlet region \(D\) of a lattice of the first type. Let \((\bar a_1,\bar a_2,\ldots,\bar a_{n+1})\) be the image, under the affine mapping \(\varphi\), of the reduced Selling edge of the lattice associated with the region \(D\). The vectors \(\bar a_1,\bar a_2,\ldots,\bar a_{n+1}\), issuing from the center of the parallelohedron, we shall call the attached vectors. We now denote by \(R_\lambda\) the lengths of the radii of the parallelohedron \(\Pi\), by \(\alpha_t\) the lengths of its incongruent edges, and by \(a_i\) the lengths of the attached vectors. In these notations formula (3) is valid for the parallelohedron \(\Pi\).

Proof of the formula for \(n=3\). Consider, together with the parallelohedron \(\Pi\) with center at the point \(O\), a parallelohedron \(\Pi_1\) with center at the point \(O_1\), and join their centers (see Fig. 1). From the parallelograms \(OA_1O_1A_3\) and \(OA_2O_1A_4\) we obtain
\[ (A_1A_3)^2+(A_2A_4)^2+2(OO_1)^2 =(OA_1)^2+(OA_2)^2+(OA_3)^2+(OA_4)^2+(O_1A_1)^2+(O_1A_2)^2+(O_1A_3)^2+(O_1A_4)^2, \]
and from the parallelogram \(A_1A_2A_3A_4\) we have
\[ 2\left[(A_1A_2)^2+(A_2A_3)^2\right]=(A_1A_3)^2+(A_2A_4)^2. \]
Combining these formulas, we obtain
\[ R_1^2+R_2^2+R_3^2+R_4^2=(A_1A_2)^2+(A_2A_3)^2+(OO_1)^2. \]
Writing analogous equalities for the other faces of the parallelohedron \(\Pi\) that are parallelograms, and summing them all, we obtain the required formula, if we take into account that each vector \(\overrightarrow{OO_k}\) is equal to the sum of two definite attached vectors of the parallelohedron.

The author takes this opportunity to express his deep gratitude to B. N. Delone for his initiative in the search for extremal lattices in the theory of coverings and for his constant interest in this work, and also to S. S. Ryshkov for communicating a geometric proof of formula (3) for arbitrary \(n\).

Mathematical Institute named after V. A. Steklov
Academy of Sciences of the USSR

Received
5 VII 1962

REFERENCES CITED

1. G. F. Voronoi, Collected Works, 2, Kiev, 1952, pp. 239–368.
2. R. P. Bambah, Proc. Nat. Inst. Sci. India, 20, 25 (1954).
3. R. P. Bambah, Proc. Camb. Phil. Soc., 56, 203 (1954).
4. H. Davenport, Rend. Circolo mat. Palermo, ser. II, 1, 92 (1952).
5. G. L. Watson, Rend. Circolo mat. Palermo, ser. II, 5, 93 (1956).
6. H. S. M. Coxeter, L. Few, C. A. Rogers, J. Pure and Appl. Math., 6, part 2, no. 12, 147 (1959).
7. B. N. Delone, Uspekhi Mat. Nauk, vol. 3, 16 (1937).
8. S. S. Ryshkov, Dokl. Akad. Nauk SSSR, 146, no. 5 (1962).
9. B. N. Delone, Uspekhi Mat. Nauk, vol. 4, 102 (1938).