UDC 513

MATHEMATICS

S. S. RYSHKOV

EFFECTIVIZATION OF ONE OF DAVENPORT’S METHODS IN THE THEORY OF COVERINGS

(Presented by Academician I. M. Vinogradov on 24 IX 1966)

Let a lattice \(\Gamma\) be given in Euclidean space \(E^n\), and from each of its points as center let a ball of radius \(R\) be described; if the radius \(R\) is such that the resulting system of balls forms a covering of the space \(E^n\), and no smaller radius satisfies this condition, then one says that a covering of the space \(E^n\) by equal balls corresponding to the lattice \(\Gamma\) (a lattice covering) is given, and the radius \(R\) is called the covering radius of the lattice \(\Gamma\). The ratio \(\theta(\Gamma)\) of the volume of a ball of radius \(R\) to the volume of a fundamental domain of the lattice \(\Gamma\) is called the density of the corresponding covering.

A special role in the theory of coverings is played by the lattice \(\Gamma_1^n\), i.e., the lattice constructed on the basis with metric form

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

“the principal form of the first type of Voronoi.”

Indeed, this lattice gives the minimum density (the “best” one) among all lattices of two, three, and four dimensions. The first is obvious, since the lattice \(\Gamma_1^2\) is constructed on a regular triangle; the second was proved by the Indian mathematician Bambah \((^1)\), the third by B. N. Delone and S. S. Ryshkov \((^2)\). In addition, it is known that the lattice \(\Gamma_1^n\) is the best among a rather broad class of \(n\)-dimensional lattices (see A. F. Gametskii \((^3)\) and S. S. Ryshkov \((^4)\)). On the other hand, from the asymptotic estimates of Davenport \((^5)\), Watson \((^6)\), and, finally, Rogers \((^7)\), it follows that for sufficiently large \(n\) there exist lattices giving a density smaller than the lattice \(\Gamma_1^n\). However, no estimate of such a number \(n\) was obtained in these works.

In the present note the author, using one lemma from Davenport’s paper \((^5)\), constructs, for all even \(n \ge 114\) and for all odd \(n \ge 201\), lattices better than the lattice \(\Gamma_1^n\).

\(1^\circ\). The following Lemma 1 is a somewhat modified formulation of Lemma 1 from Davenport’s paper \((^5)\).

Lemma 1. Let a lattice be constructed on a basis given by a metric form with matrix \(\|\Gamma\|=\|A\|\otimes\|B\|\), where the square matrix \(\|A\|\) of order \(m+1\) has the form

\[ \left\| \begin{array}{ccccc} 1 & 0 & 0 & \ldots & 1/N\\ 0 & 1 & 0 & \ldots & 1/N\\ 0 & 0 & 1 & \ldots & 1/N\\ \cdots & \cdots & \cdots & \cdots & \cdots\\ 1/N & 1/N & 1/N & \ldots & (m+1)/N^2 \end{array} \right\|; \]

the matrix \(\|B\|\) is the metric matrix of some basic basis of an arbitrary \(k\)-dimensional lattice \(B\), and the symbol \(\otimes\) denotes the Kronecker product of matrices. Then the formula holds

\[ R^2 < (m+1)\left[\int r^2\,dv \big/ \int dv\right]+\varepsilon N^2, \]

where \(R\) denotes the covering radius of the lattice \(\Gamma\), the integration being taken over the Dirichlet region of the lattice \(B\), \(\lim_{N\to\infty}\varepsilon_N=0\).

For what follows it is important to know the geometry of the principal sublattice of the lattice \(\Gamma\). First consider the orthogonal product of \(m+1\) copies of lattices specified by the matrix \(B\). The resulting \((m+1)k\)-dimensional lattice has as its metric matrix the matrix \(\|E\|\otimes\|B\|\), where \(\|E\|\) denotes the identity matrix of order \(m+1\). We shall further denote the vectors of each of the factors by \(a_j^{(i)}\), where the lower index is the number of the vector in the lattice \(B\) and runs from \(1\) to \(k\), while the upper index is the number of the factor and runs from \(1\) to \(m+1\). It is now easy to verify that the matrix \(\|\Gamma\|\) is the metric matrix of the sublattice

\[ \left\{ a_1^{(1)},\ldots,a_k^{(1)},\ a_1^{(2)},\ldots,a_k^{(2)},\ldots,\ a_1^{(m)},\ldots,a_k^{(m)},\ \frac1N\bigl(a_1^{(1)}+a_1^{(2)}+\ldots+a_1^{(m+1)}\bigr),\ldots \right. \]

\[ \left. \ldots,\frac1N\bigl(a_k^{(1)}+a_k^{(2)}+\ldots+a_k^{(m+1)}\bigr) \right\}. \]

Lemma 2. Let the lattice \(\Gamma_*\) be specified by a sublattice with metric matrix

\[ \|\Gamma_*\|=\frac1{m+1}\|\Gamma_1^m\|\otimes\|B\|, \]

where \(\|\Gamma_1^m\|\) denotes the matrix of the principal form of the first type, and \(\|B\|\) the metric matrix of some principal sublattice of an arbitrary \(k\)-dimensional lattice \(B\). Then the formula

\[ R^2\leqslant (m+1)\left[\int r^2\,dv\bigg/\int dv\right], \]

holds, where \(R\) denotes the covering radius of the lattice \(\Gamma_*\), and the integration is carried out over the Dirichlet region of the lattice \(B\).

For the proof, first we shall show that the lattice \(\Gamma_*\) is the orthogonal projection of the lattice \(\Gamma\) described above along the space specified by the sublattice

\[ \mathfrak A=\left\{ \bigl(a_1^{(1)}+a_1^{(2)}+\ldots+a_1^{(m+1)}\bigr),\ldots, \bigl(a_k^{(1)}+a_k^{(2)}+\ldots+a_k^{(m+1)}\bigr) \right\}. \]

Indeed, the vector

\[ b_j^{(i)}=a_j^{(i)}-\frac1{m+1}\bigl(a_j^{(1)}+a_j^{(2)}+\ldots+a_j^{(m+1)}\bigr), \]

where \(i=1,\ldots,m+1\) and \(j=1,\ldots,k\), is perpendicular to all vectors of the sublattice \(\mathfrak A\), i.e. is the projection we need of the vector \(a_j^{(i)}\). Computing the scalar products and the squares of the vectors \(b_j^{(i)}\), we are convinced of the validity of our first assertion.

It remains now to note that the covering radius of the lattice \(\Gamma\) is not less than the covering radius of the lattice \(\Gamma_*\) (for the orthogonal projection of a ball is a ball!) and that the covering radius of the lattice \(\Gamma_*\) does not depend on the number \(N\), which, consequently, may be chosen arbitrarily large. This last observation completely proves our lemma.

\(2^\circ\). Since

\[ \det[\|A\|\otimes\|B\|]=(\det\|A\|)^k(\det\|B\|)^m, \]

where \(k\) and \(m\) are, respectively, the orders of the matrices \(\|B\|\) and \(\|A\|\), the density of the covering corresponding to the lattice \(\Gamma_*\) described in Lemma 2 is estimated with the aid of the inequality

\[ \theta(\Gamma_*^{km})\leqslant \frac{\sqrt{(m+1)^{km}\,\bar r^{km}}}{\sqrt{D_k^m/(m+1)_k}}\,I_{mk}. \]

Here \(D_k\) denotes the determinant of the matrix \(\|B\|\), \(I_{mk}\) denotes the volume of the \(mk\)-dimensional ball of unit radius, and

\[ \bar r=\left[\int r^2\,dv\bigg/\int dv\right]^{1/2}, \]

where the integration is carried out over the Dirichlet region of the lattice \(B\).

In the special case when the lattice \(B\) is taken to be the lattice \(\Gamma_1^2\), this inequality has the form

\[ \theta(\Gamma_*^{2m})\leqslant \left[\frac5{18\sqrt3}(m+1)\right]^m (m+1)I_{2m}. \]

On the other hand, for the lattice \(\Gamma_1^n\) the density \(\theta(\Gamma_1^n)\) is computed exactly (see, for example, \((^3)\), p. 994):

\[ \theta(\Gamma_1^n)=\left[\frac{n(n+2)}{12(n+1)}\right]^{n/2}\sqrt{n+1}\,I_n, \]

or, for \(n=2m\),

\[ \theta(\Gamma_1^{2m})=\left[\frac{m(m+1)}{3(2m+1)}\right]^m \sqrt{2m+1}\,I_{2m}. \]

Hence it follows that

\[ \frac{\theta(\Gamma_1^{2m})}{\theta(\Gamma_*^{2m})} \ge \left(\frac{6\sqrt{3}}{5}\,\frac{m}{2m+1}\right)^m \frac{\sqrt{2m+1}}{m+1}. \]

This last number is greater than one for all \(m\ge 57\).

Thus we have proved the following theorem:

Theorem. The density of the lattice covering of the space \(E^n\) by equal balls corresponding to the lattice \(\Gamma_1^{2m}\) is greater than the density corresponding to the lattice \(\Gamma_*^{2m}\), given by the reper with metric matrix

\[ \|\Gamma_*^{2m}\|=\frac{1}{m+1}\,\|\Gamma_1^m\|\otimes \|\Gamma_1^2\| \]

for all \(m\ge 57\).

\(3^\circ\). Multiplying the lattice \(\Gamma_*^{2m}\) described above by a specially chosen one-dimensional lattice, we obtain a lattice of \(2m+1\) dimensions which is better than the lattice \(\Gamma_1^{2m+1}\), beginning with \(m=100\).

\(4^\circ\). It would be interesting to find the first dimension \(n\) for which there exists a lattice \(\Gamma^n\) satisfying the condition

\[ \theta(\Gamma^n)<\theta(\Gamma_1^n). \]

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

Received
19 IX 1966

CITED LITERATURE

\(^{1}\) R. P. Rambah, Proc. Nat. Inst. Sci. India. 20, 25 (1954).
\(^{2}\) B. N. Delone, S. S. Ryshkov, DAN, 152, No. 3 (1963).
\(^{3}\) A. F. Gamedskii, DAN, 151, No. 3 (1963).
\(^{4}\) S. S. Ryshkov, DAN, 162, No. 2 (1965).
\(^{5}\) H. Davenport, Rend. Circolo mat. Palermo, ser. II, 1, No. 1 (1952).
\(^{6}\) G. L. Watson, Rend. Circolo mat. Palermo, ser. II, 5, No. 1 (1956).
\(^{7}\) C. A. Rogers, Pacing and Covering, Cambridge, 1964.