MATHEMATICS

S. S. RYSHKOV

SOME REMARKS

ON THE TYPES OF \(n\)-DIMENSIONAL PARALLELOHEDRA

AND ON THE DENSITY OF LATTICE COVERINGS OF THE SPACE \(E^n\)

BY EQUAL SPHERES

(Presented by Academician I. M. Vinogradov on 30 XI 1964)

In paper (1) G. F. Voronoi established that there exist three and only three affine types of primitive decompositions \((L)\) corresponding to four-dimensional lattices. With the help of the algorithm given by Voronoi in the same paper, one can show that the number of such types already in five-dimensional space is counted in the dozens and that all types, once they have arisen, remain, in a certain sense, in all higher dimensions. In §§ \(1^0\) and \(2^0\) of the present paper the author gives a more convenient, than Voronoi’s, description of the affine structure of decompositions \((L)\) for \(n\)-dimensional lattices of the second type, and gives a description of the affine structure of decompositions \((L)\) for \(n\)-dimensional lattices of the third and of one more—the fourth—type. In §§ \(3^0\) and \(4^0\) this description is applied to the study of the density of the corresponding lattice coverings of \(n\)-dimensional space by equal spheres. It is proved that for any \(n \ge 4\) lattices of the second and third, and for \(n \ge 6\) also of the fourth types, give a denser covering than the lattice \(\Gamma_1^n\)—the principal lattice of the first type. We note that a similar theorem for all three types of lattices of four-dimensional space was proved in paper (2), and for the \(n\)-dimensional first type in paper (3).

\(1^0\). Let us denote by \(Z(a_1,\ldots,a_{n+1})\) the Selling frame of some \(n\)-dimensional lattice \(\Gamma\), i.e. an arbitrary basic frame \(a_1,a_2,\ldots,a_n\) of the lattice \(\Gamma\), completed by the vector \(a_{n+1}=-(a_1+\cdots+a_n)\). It is known that all scalar products \(g_{ij}=a_i a_j\), where \(i\ne j;\ i,j=1,2,\ldots,n+1\), are parameters completely determining the lattice \(\Gamma\). In these parameters the linear inequalities defining the principal domain of quadratic forms, i.e. the principal domain \(G_{\mathrm I}\) of lattices of the first type, have the form

\[ -g_{ij}>0. \tag{1} \]

In the same parameters the inequalities

\[ g_{12}>0;\qquad -g_{1i}-g_{12}>0;\qquad -g_{2i}-g_{12}>0;\qquad -g_{ij}>0, \tag{2} \]

where \(i\ne j\) and \(i,j=3,4,\ldots,n+1\), determine, for \(n\ge 4\), one of the domains adjacent to the principal one. All domains of lattice types adjacent* to the principal one are equivalent to this domain \(G_{\mathrm{II}}\), and the inequalities defining them are obtained from inequalities (2) by replacing the pair of indices \(1,2\) by all possible other pairs (see (1)).

The following fact is proved by carrying out Voronoi’s algorithm one more step.

The domains \(G_{\mathrm{III}}\) and \(G_{\mathrm{IV}}\), given by the inequalities

\[ g_{34}>0;\quad g_{12}-g_{34}>0;\quad -g_{ij}-g_{12}>0,\quad \text{where } i=1,2 \text{ and } j=3,4,\ldots,n+1; \tag{3} \]

\[ -g_{ij}-g_{34}>0,\quad \text{where } i=3,4 \text{ and } j=5,6,\ldots,n+1; \]

\[ -g_{ij}>0,\quad \text{where } i\ne j \text{ and } i,j=5,6,\ldots,n+1; \]

* By adjacent domains we here and below mean domains adjacent along an \(\bigl(n(n+1)/2-1\bigr)\)-dimensional face.

\[ g_{12}+g_{32}>0;\qquad -g_{31}+g_{32}>0;\qquad -g_{32}>0;\qquad -g_{ij}-g_{12}>0, \tag{4} \]

\[ \text{where } i=1,2,\ \text{and } j=4,5,\ldots,n+1; \]

\[ -g_{ij}>0,\quad \text{where } i\ne j \text{ and } i,j=3,4,\ldots,n+1, \]

are, for \(n\ge 5\), regions of types of lattices adjacent to the region \(G_{\mathrm{II}}\), and all regions adjacent to the region \(G_{\mathrm{II}}\) (except for the single principal one) are equivalent to the regions \(G_{\mathrm{III}}\) and \(G_{\mathrm{IV}}\), and are given by inequalities obtained from (3) and (4) by replacing, respectively, the indices 3, 4 and 3 by other indices not equal to 1 and 2.

In what follows, if some Selling frame of a given lattice \(\Gamma\) satisfies conditions (1), (2), (3), or (4), we shall say that we are given a Voronoi-reduced Selling frame of the lattice belonging, respectively, to type I, II, III, or IV.

\(2^\circ\). In paper \((^4)\), chains of simplexes of the star of the decomposition \((L)\) were described for lattices of the first type. The following assertions give a description of the chains of all simplexes of the star of the decomposition \((L)\) for lattices of the second, third, and fourth types. (From these chains one can find the combinatorial structure of the parallelohedra of the corresponding types.)

Let us denote by \(\mathcal Z(a_1,a_2,\ldots,a_{n+1})\), where \(n\ge 4\), a Voronoi-reduced Selling frame of an arbitrary lattice \(\Gamma\) of the second type; then the chains of all simplexes of the star of the decomposition \((L)\) for this lattice can be obtained, by means of parallel translation and central symmetry, from the following:
\(\langle a_1,a_{i_2},a_{i_3},\ldots,a_{i_{k-1}},a_2,a_{i_{k+1}},\ldots,a_{i_{n+1}}\rangle\) and
\(\langle a_1,a_2-a_1,a_{i_3}+a_1,a_{i_4},a_{i_5},\ldots,a_{i_{n+1}}\rangle\), i.e. the totality of all chains of this form gives the complete totality of pairwise nonhomologous \(L\)-simplexes of the lattice \(\Gamma\).

Let us denote by \(\mathcal Z(a_1,a_2,\ldots,a_{n+1})\), where \(n\ge 4\), a Voronoi-reduced Selling frame of an arbitrary lattice \(\Gamma\) of the third type; then the complete totality of mutually nonhomologous \(L\)-simplexes of the lattice \(\Gamma\) is given by chains of the following form:
\(\langle a_{i_1},a_{i_2},\ldots,a_{i_{n+1}}\rangle\), where neither the vectors \(a_1\) and \(a_2\), nor the vectors \(a_3\) and \(a_4\), occur next to one another;
\(\langle a_3,a_4-a_3,a_3+a_{i_3},a_{i_4},\ldots,a_{i_{n+1}}\rangle\), where the vectors \(a_1\) and \(a_2\) do not occur next to one another;
\(\langle a_1,a_2-a_1,a_1+a_{i_3},a_{i_4},\ldots,a_{i_{n+1}}\rangle\), where the vectors \(a_3\) and \(a_4\) do not occur next to one another;
\(\langle a_1,a_2-a_1,a_3+a_1,a_4,a_{i_5},\ldots,a_{i_{n+1}}\rangle\),
\(\langle a_1,a_2-a_1,a_4+a_1,a_3,a_{i_5},\ldots,\ldots,a_{i_{n+1}}\rangle\);
\(\langle a_1,a_2-a_1,a_1+a_{i_3},a_{i_4},\ldots,a_{i_{k-1}},a_{i_k}+a_3,a_4-a_3,a_3,a_{i_{k+3}},\ldots,\ldots,a_{i_{n+1}}\rangle\);
\(\langle a_1,a_2-a_1,a_1+a_{i_3}+a_3,a_4-a_3,a_3,a_{i_6},\ldots,a_{i_{n+1}}\rangle\);
\(\langle a_1,a_2-a_1,a_1+a_{i_3},\ldots,a_3,a_4-a_3,a_3+a_{i_{k-2}},a_{i_{k+3}},\ldots,a_{i_{n+1}}\rangle\);
\(\langle a_3,a_4-a_3,a_3+a_1,a_2-a_1,a_1+a_{i_5},a_{i_6},\ldots,a_{i_{n+1}}\rangle\).

Let us denote by \(\mathcal Z(a_1,a_2,\ldots,a_{n+1})\), where \(n\ge 5\), a Voronoi-reduced Selling frame of an arbitrary lattice \(\Gamma\) of the fourth type; then the complete totality of mutually nonhomologous \(L\)-simplexes of the lattice is given by chains of the following form:
\(\langle a_{i_1},a_{i_2},\ldots,a_{i_{n+1}}\rangle\), where the vectors \(a_1\) and \(a_2\) do not occur next to one another, and also the sequence of vectors \(a_1,a_3,a_2\) does not occur;
\(\langle a_1,a_2-a_1,a_1+a_{i_3},\ldots,a_{i_{n+1}}\rangle\), where \(a_{i_3}\ne a_3\);
\(\langle a_2,a_1-a_2,a_3,a_2+a_{i_4},a_{i_5},\ldots,a_{i_{n+1}}\rangle\);
\(\langle a_2,a_3,a_1-a_2,a_2+a_{i_4},a_{i_5},\ldots,a_{i_{n+1}}\rangle\).

\(3^\circ\). Take an arbitrary \(n\)-dimensional lattice \(\Gamma\) and the corresponding decomposition \((L)\) of the space \(E^n\). Let \(Y\) denote the sum of the squares of the distances from the point \(O\in\Gamma\) to the centers of gravity of the simplexes of the star of the decomposition \((L)\) surrounding this point. Since \(L\)-simplexes homologous to each given one enter the star exactly \(2(n+1)\) times, and each vertex twice, in order to compute the value \(Y\) one may compute the sum of the squares of the distances from the center of gravity of each simplex to all its vertices (an analogue of the central moment of a system of concentrated unit masses), and then sum the resulting quantity over all nonhomologous

simplices. Direct computations give the following form of the sum \(Y\) for \(n\)-dimensional lattices of the first, second, third, and fourth types:

\[ Y_{\mathrm I}=-\frac{(n+2)!}{6(n+1)}\sum g_{ij},\qquad Y_{\mathrm{II}}=Y_{\mathrm I}-\frac{(n+1)!\,2}{n(n+1)^2}g_{12}; \]

\[ Y_{\mathrm{III}}=Y_{\mathrm{II}}-\frac{(n+2)!\,2(n-3)}{(n+1)^2(n-1)(n+2)}g_{34},\qquad Y_{\mathrm{IV}}=Y_{\mathrm{II}}-\frac{(n+2)!\,4}{(n+1)^2n(n-1)}(g_{12}+g_{23}). \]

Let us note that the formula for computing the sum \(Y_{\mathrm I}\) is known from work \((^3)\).

Lemma. The following relations hold:

1. \((\min Y_{\mathrm{II}}/\overline{Y}_{\mathrm I})^n=1+24(n-2)(n-3)/n^2(n+1)^3.\)

2. \((\min Y_{\mathrm{III}}/\overline{Y}_{\mathrm I})^n=1+48(n-3)(n^7-6n^6+9n^5+13n^4-160n^3+\)
   \[ +717n^2-2998n+3740)/(n+1)^5n^2(n-1)^2(n-2)^2. \]

3. \((\min Y_{\mathrm{IV}}/\overline{Y}_{\mathrm I})^n>1+24(n-6)/n^2(n+1)(n-1).\)

Here the minima are taken over all \(n\)-dimensional lattices of the corresponding types having a fixed volume of the fundamental domain, and by \(\overline{Y}_{\mathrm I}\) is denoted the function \(Y_{\mathrm I}\), computed for the lattice \(\Gamma_1^n\), having the same volume of the fundamental domain.

Proof. Consider, in the space of parameters, the plane \(Y_{\mathrm{II}}=C\) and that part \(D\) of the discriminant surface \(\Delta=\mathrm{const}\;(=\Delta_0)\) which lies in the domain of positive definite forms. Clearly, the question of the minimum of the function \(Y_{\mathrm{II}}\) for a fixed value \(\Delta_0\) of the determinant \(\Delta\) reduces to finding the least value \(C_0\) of the parameter \(C\) for which the plane \(Y_{\mathrm{II}}\) has common points with that part of the surface \(D\) which corresponds to lattices of the second type. We shall weaken our problem and shall seek the least value of the parameter \(C\) (a priori less than \(C_1\)) for which the plane \(Y_{\mathrm{II}}=C\) has common points with the surface \(D\).

Let us note that, from the geometric meaning of the function \(Y_{\mathrm{II}}\), it follows, first, that for negative values of the parameter \(C\) the plane \(Y_{\mathrm{II}}=C\) has no common points with the surface \(D\), and, second, that there exist such \(C\) for which the plane \(Y_{\mathrm{II}}=C\) and the surface \(D\) intersect. From the homogeneity of the functions \(Y_{\mathrm{II}}\) and \(\Delta\), and also from the convexity of the surface \(D\) toward the origin (the latter see \((^5)\) or \((^6)\)), it follows that if the plane \(Y_{\mathrm{II}}=C>0\) intersects the surface \(D\), then the plane \(Y_{\mathrm{II}}=C_2>C_1\) also intersects the surface \(D\). From these facts and from the connectedness of the surface \(D\) it follows that, as the parameter \(C\) varies from \(-\infty\) to \(+\infty\), there exists a first point of encounter of the plane \(Y_{\mathrm{II}}=C\) with the surface \(D\), but there does not exist a last point of encounter. That is, there exists such a unique value of the parameter \(C\) for which the surface \(Y_{\mathrm{II}}=C\) either is tangent to the plane \(Y_{\mathrm{II}}=C\), or approaches it asymptotically. In other words, if there exists a critical point of the function \(Y_{\mathrm{II}}\) on the surface \(D\), then it is unique (since every plane tangent to the surface \(D\) has with it only one common point \((^5)\)) and at it the minimum of the function \(Y_{\mathrm{II}}\) is attained.

Let us now note that the minimum of the function \(Y_{\mathrm{II}}\) on the surface \(D\) can lie only in the intersection of the surface \(D\) with the plane given by the equations \(g_{1i}=g_{1j}=g_{2i}=g_{2j}\) and \(g_{ij}=g_{kl}\), where \(i,j,k,l=1,\ldots,n+1\), but \(i\ne j\) and \(k\ne l\). Indeed, suppose the function \(Y_{\mathrm{II}}\) at the point \(M(g_{12},g_{13},g_{14},\ldots,\ldots,g_{n,n+1})\) takes some value \(C\) and suppose, for example, \(g_{13}\ne g_{14}\); then consider the point \(N(g_{12},g_{14},g_{13},\ldots,g_{1,n+1},g_{24},g_{23},g_{25},\ldots,g_{n,n+1})\). The point \(N\), by virtue of the fact that the group of such substitutions of variables which do not change the value of the function \(\Delta\) coincides with the group of permutations of the edges of the \(n\)-dimensional simplex determined by all its rotations, lies on the surface \(D\). The value of the function \(Y_{\mathrm{II}}\) at the point \(N\) is, obviously, equal to \(C\), and since the points \(M\) and \(N\) are distinct, the number \(C\) cannot be the minimum of the function \(Y_{\mathrm{II}}\), since it can be attained only at one point. Hence it follows that at the point of minimum of the function \(Y_{\mathrm{II}}\) the variables of the form \(g_{1i}\), as well as the variables of the form \(g_{2i}\), coincide with one another. The proof of the equalities \(g_{1i}=g_{2i}\) and \(g_{ij}=g_{kl}\) at the point of minimum differs hardly at all from the one just given.

Let us now write out, taking into account the equalities \(g_{12}=x\), \(g_{1i}=g_{2i}=g\), and \(g_{ij}=h\) for \(i\ne j\) and \(i,j=3,4,\ldots,n+1\), the function
\[ Y_{\mathrm{II}}=\frac{(n-1)!}{6(n+1)} \left\{-(n^2+n+12)x-2n(n+1)g-\frac{(n+1)!}{(n-3)!}h\right\} \]
and the function
\[ \Delta=(-1)^n g[2x+(n-1)g]\,[2g+(n-1)h]^{\,n-2}. \]
Direct calculations give the value
\[ -\frac{(n+2)!\,n}{12(n+1)}(n^3+2n^2-11n+12)v \]
of the minimum of the function \(Y_{\mathrm{II}}\) at the critical point \(M\), having coordinates
\[ x=\frac{n(n+1)(n^2-11n+12)v}{n^2+n+12},\qquad h=(n^3-13n+12)v,\qquad g=n(n+1)v, \]
where
\[ v=-\sqrt[n]{\Delta_0 n^{-2}(n+1)^{-1}(n^3+2n^2-11n+12)^{1-n}(n^2+n-12)}. \]
Comparing now the \(n\)-th power of the minimum obtained with the \(n\)-th power of the number
\[ \bar Y_{\mathrm I}=\frac{(n+2)!}{12(n+1)}\sqrt[n]{(n+1)\Delta_0} \]
and noting that the point \(M\) belongs to the domain \(G_{\mathrm{II}}\), we obtain the first formula of the lemma.

The proof of the second formula is analogous.

In the proof of the third formula, direct calculations already for \(n=5\) lead to equations that are difficult to solve; therefore we shall resort to the following simplification. We note that in the domain \(G_{\mathrm{IV}}\) the parameter \(g_{32}\) is negative; therefore the omission of the term
\[ -\frac{(n+2)!\,4g_{32}^{\,2}}{(n+1)^2 n(n-1)} \]
can only decrease the value of the function \(Y_{\mathrm{IV}}\) in this domain. The function obtained after omitting this term has all the symmetries of the function \(Y_{\mathrm{II}}\), and finding its minimum, i.e. estimating the minimum of the function \(Y_{\mathrm{IV}}\), no longer presents almost any new difficulties.

\(4^\circ\). Theorem 1. For every \(n\ge 4\), the covering density of \(n\)-dimensional Euclidean space by equal spheres whose centers are at the points of any lattice of the second or third type is greater than the covering density corresponding to the lattice \(\Gamma_1^n\).

Proof. Denoting by \(\sum R_i^2\) the sum of the squares of the radii of the spheres circumscribed about all simplices of the star of the subdivision \((L)\) corresponding to an arbitrary lattice \(\Gamma\), we have, by the well-known theorem of Steiner on the central moment, for this lattice the inequality
\[ \sum R_i^2 \ge Y. \]
By virtue of the lemma proved, the sum \(Y\) for any \(n\)-dimensional lattice of the second and third types is greater than the analogous sum for the lattice \(\Gamma_1^n\), which has the same volume of the fundamental domain. Since in the lattice \(\Gamma_1^n\) the centers of gravity of all \(L\)-simplices coincide with the centers of the circumscribed spheres, for it the inequality
\[ \sum R_i^2 \ge Y \]
turns into an equality, and we obtain that the sum \(\sum R_i^2\) for any lattice of the second and third types is greater than the sum \(\sum R_i^2\) computed for the lattice \(\Gamma_1^n\) having the same volume of the fundamental domain. From this latter fact and from the equiradiality of the lattice \(\Gamma_1^n\), the assertion of the theorem follows immediately.

Theorem 2. For every \(n\ge 6\), the covering density of \(n\)-dimensional Euclidean space by equal spheres whose centers are at the points of any lattice of the fourth type is greater than the covering density corresponding to the lattice \(\Gamma_1^n\).

The proof is analogous. Let us note that the fourth type already exists in five-dimensional space, but apparently only because of the difficulties indicated in item \(3^\circ\) we were unable to prove Theorem 2 for \(n=5\).

Steklov Mathematical Institute
Academy of Sciences of the USSR

Received
16 XI 1964

REFERENCES

1. G. F. Voronoi, Collected Works, 2, Kiev, 1952, pp. 342–368.
2. B. N. Delone, S. S. Ryshkov, DAN, 152, No. 3 (1963).
3. F. Tammekänd, DAN, 151, No. 3 (1963).
4. S. S. Ryshkov, DAN, 146, No. 5 (1962).
5. B. A. Venkov, in the book G. F. Voronoi, Collected Works, 3, Kiev, 1952, p. 239.
6. H. Minkowski, Ges. Abh., 2, Leipzig—Berlin, 1911, S. 53–103.