MATHEMATICS

A. F. GAMETSKII

ON THE OPTIMALITY OF VORONOI’S PRINCIPAL LATTICE OF THE FIRST TYPE AMONG LATTICES OF THE FIRST TYPE OF ANY NUMBER OF DIMENSIONS

(Presented by Academician I. M. Vinogradov on 14 III 1963)

Let in the \(n\)-dimensional Euclidean space \(E^n\) there be given some lattice \(\Gamma\). To the lattice \(\Gamma\) there corresponds a number \(R_\Gamma\) such that balls of radius \(R_\Gamma\), with centers at the points of this lattice, cover the entire space \(E^n\), while balls of smaller radius do not cover it. By a lattice covering of the space \(E^n\) we shall mean only a covering of the space \(E^n\) by balls of radius \(R = R_\Gamma\) with centers at the points of the lattice \(\Gamma\).

The density of a lattice covering is defined as the ratio of the volume of an \(n\)-dimensional ball of radius \(R_\Gamma\) to the volume of the fundamental parallelepiped of the lattice \(\Gamma\). Obviously, the density is invariant under similarity.

The lattice of the \(n\)-dimensional space \(E^n\) constructed on the regular Selling frame, i.e., on a Selling frame with equal scalar products of its vectors, will be denoted by \(\Gamma_1^n\) and will be called the principal lattice of the first type of Voronoi \((^1)\).

The main result of this article is the following theorem.

Theorem. To the lattice \(\Gamma_1^n\) there corresponds the least value of the density of lattice coverings of the space \(E^n\) among lattices of the first type of Voronoi.

1. Let us denote by \(\Gamma\) a lattice of the space \(E^n\); by \(D\), its Dirichlet domain; and the distances from the center of the domain \(D\) to the vertices of the domain \(D\) by \(R_\lambda\) \((\lambda = 1, 2, \ldots, N\), where \(N\) is the number of vertices of the domain \(D\)), henceforth called the radii of the Dirichlet domain. Obviously, the radius \(R_\Gamma\) is the greatest among the radii \(R_\lambda\), or, what is the same, the greatest of the radii of the balls \((L)\) circumscribed about the polyhedra \(L\) of the star of the decomposition \(\{L\}\) corresponding to the domain \(D\) \((^2)\). The problem reduces to finding the least value of the expression \(\max_\lambda (R_\lambda^n/V)\), or, what is the same,

\[ \max_\lambda \left(R_\lambda^2/\sqrt[n]{V^2}\right), \]

where by \(V\) is denoted the volume of the fundamental parallelepiped of the lattice \(\Gamma\).

The proof of the theorem is based on B. N. Delone’s idea of seeking the least value of the expression

\[ M = \sum_{\lambda=1}^{N}\left(R_\lambda^2/\sqrt[n]{V^2}\right) \]

and on the following lemma:

Lemma. If in the space \(E^n\) there is given a system of \(q\) points \(\{A_i\}\) \((i = 1, 2, \ldots, q)\), then the sum of the squares of the distances from any point \(C\) to the points of the system \(\{A_i\}\) is equal to the sum of the squares of the distances from the center of gravity \(O\) of the system of points \(\{A_i\}\) to the points of this system, added to the product of the number of points of the system by the square of the distance between \(O\) and \(C\).

Indeed, let \(\overrightarrow{CA_i}\) be the vector going from the point \(C\) to the point \(A_i\), \(\overrightarrow{OA_i}\) the vector going from the center of gravity \(O\) to the point \(A_i\), and \(\overrightarrow{CO}\) the vector from the point \(C\) to the point \(O\).

Then

\[ \overrightarrow{CA_i}=\overrightarrow{OA_i}+\overrightarrow{CO}, \]

\[ \overrightarrow{CA_i}^{\,2}=\overrightarrow{OA_i}^{\,2}+\overrightarrow{CO}^{\,2} +2\overrightarrow{CO}\cdot \overrightarrow{OA_i}, \]

whence we have that

\[ \sum_{i=1}^{q}\overrightarrow{CA_i}^{\,2} = \sum_{i=1}^{q}\overrightarrow{OA_i}^{\,2} +q\cdot \overrightarrow{CO}^{\,2}, \]

since \(\sum_{i=1}^{q}\overrightarrow{OA_i}=0\). We note that this lemma is equivalent to the theorem of mechanics on the moment of inertia of a system of point masses with respect to an axis.

2. Derivation of a formula. Let \((\mathbf a_1,\mathbf a_2,\ldots,\mathbf a_{n+1})\) be a reduced Selling frame of some lattice \(\Gamma\) of the first type. In what follows, by the words “the lattice \(\Gamma\)” we shall mean a lattice \(\Gamma\) of the first type \({}^{(3)}\) and, in addition, shall assume that the lattice \(\Gamma\) is primitive, since nonprimitive lattices are limiting cases of primitive ones \({}^{(2)}\). A snake \(\langle \mathbf a_{k_0},\mathbf a_{k_1},\ldots,\mathbf a_{k_n}\rangle\) of the vectors of the reduced Selling frame \((\mathbf a_1,\mathbf a_2,\ldots,\mathbf a_{n+1})\) is called a closed broken line with links \(\mathbf a_{k_0},\mathbf a_{k_1},\ldots,\mathbf a_{k_n}\), where \(k_0,k_1,\ldots,k_n\) is some permutation of the numbers \(1,2,\ldots,n+1\) \({}^{(4)}\). From the works of G. F. Voronoi \({}^{(3)}\) it follows that the simplexes (the convex hulls of snakes) constructed on all possible snakes of the vectors of the reduced Selling frame of the lattice \(\Gamma\), with the beginning of the first link at the point \(A_0\), are simplexes \(L\) and together form the star of the point \(A_0\) in the partition \(\{L\}\).

Consider some simplex \(L_k\) of the star of the point \(A_0\) of the lattice of the partition \(\{L\}\); let \(O_k\) and \(C_k\) be, respectively, the center of gravity and the center of the circumscribed sphere of the simplex \(L_k\), and let \(A_0,A_1,\ldots,A_n\) be its vertices.

Introduce the notation:
\(\overrightarrow{O_kA_i}=\mathbf b_{ki}\), \(\overrightarrow{C_kA_i}=\mathbf R_{ki}\), \(|\mathbf R_{ki}|=R_k\), \(\overrightarrow{O_kC_k}=\mathbf c_k\).
Then, by the lemma,

\[ R_k^2=\frac{1}{n+1}\sum_{i=0}^{n}\mathbf b_{ki}^{2}+\mathbf c_k^{2}, \]

and the sum of the squares of the radii of the domain \(D\) will have the form

\[ \sum_{k=1}^{(n+1)!} R_k^2 = \frac{1}{n+1}\sum_{k=1}^{(n+1)!}\sum_{i=0}^{n}\mathbf b_{ki}^{2} + \sum_{k=1}^{(n+1)!}\mathbf c_k^{2}. \]

Express

\[ \sum_{k=1}^{(n+1)!}\sum_{i=0}^{n}\mathbf b_{ki}^{2} \]

in terms of the sum of the squares of the vectors of the reduced Selling frame of the lattice \(\Gamma\). Let the simplex \(L_k\) be constructed on the snake
\(\langle \mathbf a_{k_0},\mathbf a_{k_1},\ldots,\mathbf a_{k_n}\rangle\). Then the coordinates of its vertices \(A_i,A_{i+1},\ldots,A_{n-i}\) \((i=0,1,\ldots,n)\) with respect to the frame \(\mathbf a_{k_i},\mathbf a_{k_{i+1}},\ldots,\mathbf a_{k_{n-i}}\) of \(n\) vectors of the reduced Selling frame will be \((0,0,\ldots,0)\), \((1,0,0,\ldots,0)\), \((1,1,0,\ldots,0),\ldots,(1,1,\ldots,1)\), and the vector \(\mathbf b_{ik}\), going from the vertex \(A_i\) to the center of gravity \(O_k\) of the simplex \(L_k\), is expressed through the vectors of the snake
\(\mathbf a_{k_0},\mathbf a_{k_1},\ldots,\mathbf a_{k_n}\) as follows:

\[ \mathbf b_{ik}= \frac{n\mathbf a_{k_i}+(n-1)\mathbf a_{k_{i+1}}+\cdots+\mathbf a_{k_{i+n-1}}}{n+1}, \]

where \(i=0,1,\ldots,n\), \(\mathbf a_{k_{i+n-1}}=\mathbf a_{k_{i-2}}\) for \(i=2,3,\ldots,n\), whence for

\[ \sum_{k=1}^{(n+1)!}\sum_{i=0}^{n}\mathbf b_{ik}^{2} \]

after some elementary computations, taking into account the rela-

using

\[ 2\sum_{i=1}^{n} a_i a_{i+1}=-\sum_{j=1}^{n+1} a_j^2, \]

which follows from the fact that

\[ \sum_{j=1}^{n+1} a_j=0, \]

we find the expression

\[ \sum_{k=1}^{(n+1)!}\sum_{i=0}^{n} b_{ik}^{2} = \frac{(n+1)!}{12}(n+2)\sum_{j=1}^{n+1} a_j^2, \]

and, consequently, the sum of the squares of the radii of the Dirichlet domain of the lattice \(\Gamma\) takes the form:

\[ \sum_{k=1}^{(n+1)!} R_k^2 = \frac{(n+1)!}{12}\cdot\frac{n+2}{n+1} \sum_{j=1}^{n+1} a_j^2 + \sum_{k=1}^{(n+1)!} c_k^2 . \tag{1} \]

3. Proof of the theorem. Let \(g_{ms}=a_m a_s\) \((m<s,\ m=1,2,\ldots,n,\ s=2,3,\ldots,n+1)\) be the Selling parameters of the lattice \(\Gamma\). We shall show that on the surface \(\Delta=(n+1)^{n-1}\) in the \(n(n+1)/2\)-dimensional space of the Selling parameters \(g_{ms}\) of lattices, where \(\Delta\) is the square of the volume of the fundamental parallelepiped of the lattice \(\Gamma\), the sum of the squares of the radii of the Dirichlet domain attains its least value at the point \(P=(-1,-1,\ldots,-1)\), which corresponds to the lattice \(\Gamma_1^n\). Let us examine the expression \(B=\sum_{j=1}^{n+1} a_j^2\), which enters the first term of formula (1). In the space of the parameters \(g_{ms}\),

\[ \sum_{j=1}^{n+1} a_j^2=-2(g_{12}+g_{13}+\cdots+g_{n\,n+1}). \]

Therefore \(B=\sum_{j=1}^{n+1} a_j^2\) in the space of these parameters is the equation of a hyperplane \(Q\). The discriminant surface \(\Delta=\mathrm{const}\), as Minkowski showed \((^5)\), is convex toward the origin. It is obvious that for a certain value of \(B\) the hyperplane \(Q\) is tangent to the surface \(\Delta=(n+1)^{n-1}\) at the point \(P=(-1,-1,\ldots,-1)\). Consequently, the function \(\sum_{j=1}^{n+1} a_j^2\) on the surface \(\Delta=(n+1)^{n-1}\) has at this point a unique minimum, which is also its least value. The expression \(\sum_{k=1}^{(n+1)!} c_k^2\geqslant 0\) at the point \(P\) is equal to zero, since for the simplexes \(L\) of the partition \(\{L\}\) of the lattice \(\Gamma_1^n\), as is easy to see, the centers of gravity coincide with the centers of the circumscribed spheres.

Consequently, the expression \(M\) of item 1 for the lattice \(\Gamma_1^n\) attains its least value. But since at the point \(P\) all \(R_k\) are equal, the largest of the \(R_k\), for fixed \(\Delta\), also attains its least value at the point \(P=(-1,-1,\ldots,-1)\).

The author expresses gratitude to B. N. Delone for valuable advice and constant interest in the work.

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

Received
14 III 1963

CITED LITERATURE

\(^1\) A. F. Gametskii, DAN, 146, No. 5, 991 (1962).
\(^2\) B. N. Delone, UMN, issue 3, 16 (1937).
\(^3\) G. F. Voronoi, Collected Works, 2, Kiev, 1952, p. 342.
\(^4\) S. S. Ryshkov, DAN, 146, No. 5 (1962).
\(^5\) H. Minkowski, Diskontinuitätsbereich für arithm. Äquivalenz, Ges. Abh., 2, 1911.