Covering large-dimensional Euclidean spaces by random translates of a given convex body
Boris Bukh, Jun Gao, Xizhi Liu, Oleg Pikhurko, Shumin Sun · 2025
Read Covering large-dimensional Euclidean spaces by random translates of a given convex body by Boris Bukh, 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-2510-25685.txt.
Introduction
Boris Bukh, Jun Gao, Xizhi Liu, Oleg Pikhurko, and Shumin Sun cover Euclidean spaces. Their 2025 mathematics paper uses random translates of convex bodies. Minimum covering density in high dimensions is a major problem. Unit ball coverings remain open as dimension grows. Best known bounds come from decades of work. They prove ball coverings attaining best known density.
Additionally, every point is covered limited times. Maximum multiplicity is bounded by a constant times density scale. That strengthens an Erdos and Rogers result from sixties. Their constant improves on the earlier exponential constant. The method behind best coverings also has limits. Random lattice-periodic constructions fail below best density. That failure holds replacing balls by any convex body. A worst convex body in this sense is a cube. Its random packing density is only lower order. Covering geometry in high dimensions gains sharper picture. Multiplicity control matters for applications needing bounded overlap.
Catalog record
| CREATOR | Boris Bukh, 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/2510-25685
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Covering large-dimensional Euclidean spaces by random translates of a given convex body Boris Bukh, Jun Gao, Xizhi Liu, Oleg Pikhurko, Shumin Sun Abstract Determining the minimum density of a covering of ℝ n \mathbb{R}^{n} by Euclidean unit balls as n → ∞ n\to\infty is a major open problem, with the best known results being the lower bound of ( e − 3 / 2 + o ( 1 ) ) n \left(\mathrm{e}^{-3/2}+o(1)\right)n by Coxeter, Few and Rogers [ Mathematika 6 , 1959] and the upper bound of ( 1 / 2 + o ( 1 ) ) n ln n \left(1/2+o(1)\right)n\ln n by Dumer [ Discrete Comput. Geom. 38 , 2007]. We prove that there are ball coverings of ℝ n \mathbb{R}^{n} attaining the asymptotically best known density ( 1 / 2 + o ( 1 ) ) n ln n \left(1/2+o(1)\right)n\ln n such that, additionally, every point of ℝ n \mathbb{R}^{n} is covered at most ( 1.79556 … + o ( 1 ) ) n ln n \left(1.79556...+o(1)\right)n\ln n times. This strengthens the result of Erdős and Rogers [ Acta Arith. 7 , 1961/62] who had the maximum multiplicity at most ( e + o ( 1 ) ) n ln n \left(\mathrm{e}+o(1)\right)n\ln n . On the other hand, we show that the method that was used for the best known ball coverings (when one takes a random subset of centres in a fundamental domain of a suitable lattice in ℝ n \mathbb{R}^{n} and extends this periodically) fails to work if the density is less than ( 1 / 2 + o ( 1 ) ) n ln n (1/2+o(1))n\ln n ; in fact, this result remains true if we replace the ball by any convex body K K . Also, we observe that a “worst” convex body K K here is a cube, for which the packing density coming from random constructions is only ( 1 + o ( 1 ) ) n ln n (1+o(1))n\ln n . 1 Introduction The fundamental result of Rogers [ 14 ] states that, for every convex body K (i.e. a compact convex set with non-empty interior) in the n -dimensional Euclidean space \mathbb{R}^{n} , there exists a covering of \mathbb{R}^{n} by translates of K with density at most (1+o(1))n\ln n as n\to\infty . If K is a ball then the covering density was improved to (1/2+o(1))n\ln n by Dumer [ 7 ] while the best known lower bound is \left(\mathrm{e}^{-3/2}+o(1)\right)n by Coxeter, Few and Rogers [ 5 ] . Closing this gap for ball covering is a major open problem. In brief, the new results proved in this paper are as follows. First, Theorem 1.1 proves that there are ball coverings of \mathbb{R}^{n} attaining the asymptotically best known density \left(1/2+o(1)\right)\cdot n\ln n such that, additionally, every point of \mathbb{R}^{n} is covered at most \left(1.79556...+o(1)\right)n\ln n times. This strengthens a result of Erdős and Rogers [ 8 ] who had the maximum multiplicity at most \left(\mathrm{e}+o(1)\right)n\ln n . Also, Theorem 1.3 shows that, for any given convex body K\subseteq\mathbb{R}^{n} , the method that was used in [ 14 , 7 ] (when one takes a random subset of centres in a fundamental domain of a suitable lattice in \mathbb{R}^{n} and extends this periodically) fails with high probability to produce a K -covering if the appropriately defined density is strictly less than (1/2+o(1))n\ln n . Finally, Theorem 1.5 gives that, somewhat surprisingly, a “worst” convex body K for this method is a cube, for which the packing density coming from random constructions is only (1+o(1))n\ln n (which matches the bound of Rogers [ 14 ] ). Let us provide the details. Let B_{r}^{n}(\mathbf{x})\coloneqq\{\mathbf{y}\in\mathbb{R}^{n}\colon\|\mathbf{x}-\mathbf{y}\|\leq r\} denote the closed ball of radius r centred at \mathbf{x} , where \|\cdot\| denotes the Euclidean norm. When \mathbf{x}=\mathbf{0} is the origin of \mathbb{R}^{n} , we write B_{r}^{n} for brevity. Let \operatorname{vol}(\cdot) denote the Lebesgue measure on \mathbb{R}^{n} . Also, we define \nu_{n}\coloneqq\operatorname{vol}(B_{1}^{n}) to be the volume of the n -dimensional unit ball B_{1}^{n} . Let K\subseteq\mathbb{R}^{n} be a convex body. A (discrete) set P\subseteq\mathbb{R}^{n} is called a K -covering of a set A\subseteq\mathbb{R}^{n} if A is a subset of \displaystyle P+K\coloneqq\left\{\mathbf{p}+\mathbf{x}\colon\text{$\mathbf{p}\in P$ and $\mathbf{x}\in K$}\right\}, that is, the union of the translates of K by the elements of P contains every point of A . For a measurable A\subseteq\mathbb{R}^{n} of finite measure, the covering density of a set P\subseteq\mathbb{R}^{n} over A is defined as \displaystyle\vartheta_{K}(P,A)\coloneqq\sum_{\mathbf{p}\in P}\frac{\operatorname{vol}\big(A\cap(K+\mathbf{p})\big)}{\operatorname{vol}(A)}. The covering multiplicity of a point \mathbf{x}\in A is defined as \displaystyle\mu_{K}(P,\mathbf{x})\coloneqq\left|\left\{\mathbf{p}\in P\colon\mathbf{x}\in K+\mathbf{p}\right\}\right|. The covering multiplicity of P is then defined as \displaystyle\mu_{K}(P,A)\coloneqq\sup\left\{\mu_{K}(P,\mathbf{x})\colon\mathbf{x}\in A\right\}, i.e., the maximum number of times that a point of A is covered by the translates of K by the elements of P . The K -covering density and K -covering multiplicity of P over \mathbb{R}^{n} are defined by \displaystyle\vartheta_{K}(P)\coloneqq\limsup_{r\to\infty}\vartheta_{K}\big(P,[-r,r]^{n}\big)\quad\text{and}\quad\mu_{K}(P)\coloneqq\sup_{r\to\infty}\mu_{K}\big(P,[-r,r]^{n}\big). In the case when K is the unit ball B_{1}^{n} , we may omit the subscript K and write just \vartheta(P,A) , \mu(P,\mathbf{x}) , \mu(P,A) , etc. Thus, for example, Dumer’s result [ 7 ] gives a unit ball covering P of \mathbb{R}^{n} with \vartheta(P)\leq\left(1/2+o(1)\right)n\ln n . Our first result shows that, additionally, one can assume that the covering multiplicity of P is at most (1.795...+o(1))n\ln n , improving on the previous multiplicity bound (\mathrm{e}+o(1))n\ln n of Erdős and Rogers [ 8 ] , where \mathrm{e}=2.718... is the base of the natural logarithm. Theorem 1.1 . There exists a unit ball covering P of \mathbb{R}^{n} such that \displaystyle\vartheta(P)\leq\left(\frac{1}{2}+o(1)\right)n\ln n\quad\text{and}\quad\mu(P)\leq\big(\xi+o(1)\big)n\ln n, where \xi=1.79556... is the unique (positive) real root of \displaystyle\ln\left(\frac{2x}{\mathrm{e}}\right)=\frac{1}{2x}. (1) Recall that a lattice \Lambda\subseteq\mathbb{R}^{n} is a set of the form \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\}, for some linearly independent vectors \mathbf{b}_{1},\ldots,\mathbf{b}_{n}\in\mathbb{R}^{n} , where we use the shorthand [n]\coloneqq\{1,\dots,n\} . For a convex body K\subseteq\mathbb{R}^{n} , we call a lattice \Lambda\subseteq\mathbb{R}^{n} a packing lattice of K if, for every distinct elements \mathbf{p},\mathbf{p}^{\prime}\in P , the translates K+\mathbf{p} and K+\mathbf{p}^{\prime} are disjoint. The corresponding quotient \mathbb{T}_{\Lambda}\coloneqq\mathbb{R}^{n}/\Lambda (of the topological Abelian group (\mathbb{R}^{n},+) by the discrete subgroup \Lambda ) is then called a packing torus of K . Slightly abusing notation, we use \operatorname{vol}(\cdot) also to denote the measure on \mathbb{T}_{\Lambda} obtained by identifying the torus with a fundamental domain of \Lambda and using the Lebesgue measure on the latter. Likewise, we may use the same symbol A to refer to the projection of A\subseteq\mathbb{R}^{n} to \mathbb{T} , etc. Recall that a discrete random variable \mathbf{X} has the Poisson distribution with mean \lambda>0 , denoted \mathbf{X}\sim\mathrm{Pois}(\lambda) , if for each integer k\geq 0 the probability of \mathbf{X} assuming value k is {\lambda^{k}\mathrm{e}^{-\lambda}}{k!} . A random set \mathbf{X}\subseteq A is said to be sampled from the Poisson point process on measurable subset A\subseteq\mathbb{R}^{n} with intensity \rho if the following conditions hold: (i) For every bounded measurable set S\subseteq A , the number of points in S , that is, |\mathbf{X}\cap S| , has the Poisson distribution with mean \rho\cdot\operatorname{vol}(S) . (ii) For any disjoint bounded measurable sets S_{1},\dots,S_{k}\subseteq A , the random variables |\mathbf{X}\cap S_{1}|,\dots,|\mathbf{X}\cap S_{k}| are mutually independent. Such a distribution is known to exist