New upper bound for lattice covering by spheres
Jun Gao, Xizhi Liu, Oleg Pikhurko, Shumin Sun · 2025
Read New upper bound for lattice covering by spheres by Jun Gao, Xizhi Liu, Oleg Pikhurko, Shumin Sun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06446.txt.
Introduction
Jun Gao, Xizhi Liu, Oleg Pikhurko, and Shumin Sun tighten a classic bound on covering space with a lattice of equal balls. A lattice covering places ball centers on a neat grid so no point is left out. The cost is the density, roughly how much the balls overlap. Rogers set the best known bound back in 1959. Their 2025 paper beats it.
The new bound keeps the same broad shape but trims the power on the log term. That power drops from just above two to just below one point nine. In high dimensions the trim compounds into a real saving. Covering bounds feed coding theory and signal packing. Small trims at this level tend to take decades, which marks the step as notable.
Catalog record
| CREATOR | Jun Gao, Xizhi Liu, Oleg Pikhurko, Shumin Sun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-06446
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New upper bound for lattice covering by spheres Jun Gao, Xizhi Liu, Oleg Pikhurko, Shumin Sun Abstract We show that there exists a lattice covering of ℝ n \mathbb{R}^{n} by Eucledian spheres of equal radius with density O ( n ln β n ) O\big(n\ln^{\beta}n\big) as n → ∞ n\to\infty , where β ≔ 1 2 log 2 ( 8 π e 3 3 ) = 1.85837 … . \displaystyle\beta\coloneqq\frac{1}{2}\log_{2}\left(\frac{8\pi\mathrm{e}}{3\sqrt{3}}\right)=1.85837...\,. This improves upon the previously best known upper bound by Rogers from 1959 of O ( n ln α n ) O\big(n\ln^{\alpha}n\big) , where α ≔ 1 2 log 2 ( 2 π e ) = 2.0471 … \alpha\coloneqq\frac{1}{2}\log_{2}(2\pi\mathrm{e})=2.0471... . 1 Introduction Given n , we would like to cover the entire space \mathbb{R}^{n} by placing spheres 1 1 1 Throughout this work, we adopt the convention that ‘sphere’ means a closed Euclidean ball. of the same radius r at each element of a lattice \Lambda , that is, we require that \displaystyle\Lambda+B_{r}^{n}=\mathbb{R}^{n}, (1) where B_{r}^{n}:=\{\mathbf{x}\in\mathbb{R}^{n}\colon\|\mathbf{x}\|_{2}\leq r\} denotes the Euclidean sphere of radius r in \mathbb{R}^{n} centred at the origin and X+Y\coloneqq\left\{\mathbf{x}+\mathbf{y}\colon\text{$\mathbf{x}\in X$ and $\mathbf{y}\in Y$}\right\} denotes the sum of two sets X,Y\subseteq\mathbb{R}^{n} . We call any such pair (\Lambda,B_{r}^{n}) a (sphere) lattice covering of \mathbb{R}^{n} and define its density as \displaystyle\Theta(\Lambda,B_{r}^{n})\coloneqq\frac{\operatorname{vol}(B^{n}_{r})}{|\det(\Lambda)|}, where \operatorname{vol}(B^{n}_{r}) denotes the volume of B^{n}_{r} and \det(\Lambda) is the determinant of \Lambda which can be defined as \displaystyle\det(\Lambda)\coloneqq\det\left[\mathbf{b}_{1},\ldots,\mathbf{b}_{n}\right], the determinant of the matrix made of some (equivalently, any) linearly independent vectors 2 2 2 Unless otherwise specified, all vectors in this work are considered column vectors. \mathbf{b}_{1},\ldots,\mathbf{b}_{n}\in\mathbb{R}^{n} that generate the lattice \Lambda , i.e., satisfy \displaystyle\Lambda=\left\{\lambda_{1}\mathbf{b}_{1}+\cdots+\lambda_{n}\mathbf{b}_{n}\colon\text{$\lambda_{i}\in\mathbb{Z}$ for $i\in[n]$}\right\}, (2) where [n]:=\{1,\ldots,n\} . The covering density of \Lambda is then defined as \displaystyle\Theta(\Lambda)\coloneqq\min_{r\geq 0}\left\{\Theta(\Lambda,B_{r}^{n})\colon\mathbb{R}^{n}=\Lambda+B_{r}^{n}\right\}. The classical lattice covering problem , a central topic in combinatorial geometry (see e.g. books [ 22 , 16 , 6 ] ), asks for the optimal lattice covering density in dimension n , defined as \displaystyle\Theta_{n}\coloneqq\inf\left\{\Theta(\Lambda)\colon\text{$\Lambda\subseteq\mathbb{R}^{n}$ is a lattice}\right\}. Determining \Theta_{n} seems a very difficult problem, with exact values known only for n\leq 5 (see [ 17 , 2 , 4 , 15 , 10 , 23 ] ) and with many questions (such as, for example, whether the Leech lattice is optimal) being still open. Various lower and upper bounds for \Theta_{n} were obtained in a large number of works, starting with the classical papers [ 3 , 8 , 13 , 20 , 7 ] from the 1950s; we refer the reader to the papers [ 24 , 12 ] that contain overviews of more recent results. In general, for any convex body K\subseteq\mathbb{R}^{n} , one can similarly define the optimal lattice covering density \Theta_{n,K} of K (see e.g. [ 22 ] for details). Improving upon Rogers’ [ 20 ] upper bound \Theta_{n,K}=O\left(n^{\log_{2}\ln n+O(1)}\right) from 1959, a recent breakthrough by Ordentlich–Regev–Weiss [ 18 ] shows that \Theta_{n,K}=O(n^{2}) holds universally for all convex bodies K\subseteq\mathbb{R}^{n} . However, in perhaps the most fundamental case when K is the sphere, this general upper bound does not improve upon Rogers’ other result from the same paper [ 20 ] that \Theta_{n}=O\left(n\ln^{\alpha}n\right) , where \alpha\coloneqq\tfrac{1}{2}\log_{2}(2\pi\mathrm{e})=2.0471... . In this work, we establish the following upper bound for \Theta_{n} , improving upon the above mentioned bound of Rogers [ 20 ] . Theorem 1.1 . There exists a constant C such that for every integer n\geq 1 , it holds that \displaystyle\Theta_{n}\leq Cn\ln^{\beta}n,\quad\text{where}\quad\beta\coloneqq\frac{1}{2}\log_{2}\left(\frac{8\pi\mathrm{e}}{3\sqrt{3}}\right)=1.85837...\,. Let us remark that the factor n in Theorem 1.1 is necessary, as shown by Coxeter–Few–Rogers [ 7 ] who proved that \Theta_{n}\geq\left(\mathrm{e}^{-3/2}+o(1)\right)n , improving upon earlier results of Bambah–Davenport [ 3 ] and Erdős–Rogers [ 13 ] . Another obstacle to improving the upper bound of \Theta_{n} is that, even when the condition that \Lambda\subseteq\mathbb{R}^{n} is a lattice is removed and arbitrary sphere coverings of \mathbb{R}^{n} are allowed, the best known asymptotic upper bound still has order n\ln n (see e.g. [ 19 , 14 , 21 , 5 , 11 ] ). Theorem 1.1 follows relatively quickly from the following more general theorem, which provides a general strategy for proving upper bounds on \Theta_{n} . To state the result, we first introduce some necessary definitions. Given a point \mathbf{x}\in\mathbb{R}^{n} and n linearly independent vectors \mathbf{b}_{1},\ldots,\mathbf{b}_{n}\in\mathbb{R}^{n} , the parallelepiped \mathrm{P}=\mathrm{P}_{\mathbf{x}} starting at \mathbf{x}\in\mathbb{R}^{n} and generated by \{\mathbf{b}_{1},\ldots,\mathbf{b}_{n}\} is defined as the convex hull of \displaystyle V_{\mathbf{x}}(\mathbf{b}_{1},\ldots,\mathbf{b}_{n})\coloneqq\left\{\mathbf{x}+\lambda_{1}\mathbf{b}_{1}+\cdots+\lambda_{n}\mathbf{b}_{n}\colon\text{$\lambda_{i}\in\{0,1\}$ for $i\in[n]$}\right\}. Trivially, V_{\mathbf{x}}(\mathbf{b}_{1},\ldots,\mathbf{b}_{n}) is exactly the set of the vertices of the polytope \mathrm{P} and we will refer to this set as V(\mathrm{P}) . We say a parallelepiped \mathrm{P}\subseteq\mathbb{R}^{n} is a \Lambda -parallelepiped if V(\mathrm{P})\subseteq\Lambda . If, in addition, \operatorname{vol}(\mathrm{P})=|\mathrm{det}(\Lambda)| , then \mathrm{P} is called a fundamental parallelepiped of \Lambda . For example, any set of vectors that generates \Lambda as in ( 2 ) produces a fundamental parallelepiped. The following concept will be crucial for our result. Definition 1.2 (Robust lattice covering) . Let d\geq 1 be an integer and r\geq 0 be a real number. A lattice covering (\Lambda,B_{r}^{d}) of \mathbb{R}^{d} is robust if every closed ball of radius r in \mathbb{R}^{d} contains a fundamental parallelepiped of \Lambda . Extending the definition of \Theta_{n} , we define the optimal robust lattice covering density of \mathbb{R}^{n} as \displaystyle\tilde{\Theta}_{n}\coloneqq\inf\{\Theta(\Lambda,B_{r}^{n})\colon\text{$(\Lambda,B_{r}^{n})$ is a robust lattice covering of $\mathbb{R}^{n}$}\}. For every integer d\geq 1 , define \displaystyle\nu_{d}\coloneqq\operatorname{vol}\left(B_{\sqrt{d}}^{d}\right)=\frac{(\pi d)^{\frac{d}{2}}}{\Gamma\left(\frac{d}{2}+1\right)}, where \Gamma denotes the gamma function. The following result provides an asymptotic upper bound for \Theta_{n} in terms of \tilde{\Theta}_{d} . Theorem 1.3 . For every integer d\geq 1 , there exists a constant C_{\ref{THM:general-parallelepiped}}=C_{\ref{THM:general-parallelepiped}}(d) such that for n\geq d , \displaystyle\Theta_{n}\leq C_{\ref{THM:general-parallelepiped}}n\ln^{\gamma}n,\quad\text{where}\quad\gamma=\gamma_{d}\coloneqq\frac{1}{2}\log_{2}(2\pi\mathrm{e})-\frac{1}{d}\log_{2}\left({\nu_{d}}/{\tilde{\Theta}_{d}}\right). It is straightforward to verify that \left(\mathbb{Z}^{d},B^{d}_{\sqrt{d}}\right) is a robust lattice covering of \mathbb{R}^{d} with density \nu_{d} for any d\geq 1 . Hence, \tilde{\Theta}_{d}\leq\nu_{d} . Thus that \gamma_{d}\leq\frac{1}{2}\log_{2}(2\pi\mathrm{e}) , which recovers Rogers’ bound by Theorem 1.3 (applied with any chosen d\geq 1 ). Theorem 1.1 follows immediately from Theorem 1.3 and the following upper bound for \tilde{\Theta}_{2} . Lemma 1.4 . There exists a robust lattice covering of \mathbb{R}^{2} with density \frac{8\pi}{3\sqrt{3}} . In particular, \displaystyle\tilde{\Theta}_{2}\leq\frac{8\pi}{3\sqrt{3}}. Proof of Lemma 1.4 . Let \displaystyle\mathbf{v}_{1}\coloneqq(1,0)^{t},\quad\mathbf{v_{2}}\coloneqq\big(1/2,\sqrt{3}/2\big)^{t},\quad\text{and}\quad r\coloneqq 2/\sqrt{3}, where \mathbf{v}^{t} denotes the transposition of a vector \mathbf{v} . Let \Lambda\subseteq\mathbb{R}^{2} denote the lattice generated by \{\mathbf{v}_{1},\mathbf{v}_{2}\} (see Figure 1 ). We claim that \left(\Lambda,B^{2}_{r}\right) is a robust lattice covering of \mathbb{R}^{2} . By definition, it amounts to showing that for every point \mathbf{w}\in\mathbb{R}^{2} , the sphere B_{r}^{2}(\mathbf{w}) of radius r centred at \mathbf{w} contains a fundamental parallelepiped of \Lambda . By symmetry, it suffices to prove this statement for all points \mathbf{w} contained in the equilateral triangle \triangle_{ABE} shown in Figure 1 . O A B D E G X Figure 1: The lattice generated by \mathbf{v}_{1}=(1,0)^{t} and \mathbf{v}_{2}=\bigl(1/2,\sqrt{3}/{2}\bigr)^{t} , three balls of radius 2/\sqrt{3} centred at the origin O , D=2\mathbf{v}_{1} and G=2\mathbf{v}_{2} , and three different fundamental parallelepipeds OAEB,DABE,GBAE . The point X is the centre of the triangle ABE . Let X denote the centre of \triangle_{ABE} . It is easy to see that • if \mathbf{w}\in\triangle_{AXB} , then the ball B_{r}^{2}(\mathbf{w}) contains the fundamental parallelepiped \mathord{\text{ \hbox to10.4pt{\vbox to6.86pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower 0.23056pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{\lx@inpgf@ignorespaces}{}}{{}}{} {\lx@inpgf@ignorespaces}{} {\lx@inpgf@ignorespaces}{}