## New bounds on the density of lattice coverings

HTML articles powered by AMS MathViewer

- by
Or Ordentlich, Oded Regev and Barak Weiss
**HTML**| PDF - J. Amer. Math. Soc.
**35**(2022), 295-308 Request permission

## Abstract:

We obtain new upper bounds on the minimal density $\Theta _{n, \mathcal {K}}$ of lattice coverings of ${\mathbb {R}}^n$ by dilates of a convex body $\mathcal {K}$. We also obtain bounds on the probability (with respect to the natural Haar-Siegel measure on the space of lattices) that a randomly chosen lattice $L$ satisfies $L+\mathcal {K}= {\mathbb {R}}^n$. As a step in the proof, we utilize and strengthen results on the discrete Kakeya problem.## References

- G. J. Butler,
*Simultaneous packing and covering in euclidean space*, Proc. London Math. Soc. (3)**25**(1972), 721–735. MR**319054**, DOI 10.1112/plms/s3-25.4.721 - H. S. M. Coxeter, L. Few, and C. A. Rogers,
*Covering space with equal spheres*, Mathematika**6**(1959), 147–157. MR**124821**, DOI 10.1112/S0025579300002059 - Laurent Clozel, Hee Oh, and Emmanuel Ullmo,
*Hecke operators and equidistribution of Hecke points*, Invent. Math.**144**(2001), no. 2, 327–351. MR**1827734**, DOI 10.1007/s002220100126 - J. H. Conway and N. J. A. Sloane,
*Sphere packings, lattices and groups*, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 290, Springer-Verlag, New York, 1988. With contributions by E. Bannai, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov. MR**920369**, DOI 10.1007/978-1-4757-2016-7 - Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan,
*Extensions to the method of multiplicities, with applications to Kakeya sets and mergers*, SIAM J. Comput.**42**(2013), no. 6, 2305–2328. MR**3143848**, DOI 10.1137/100783704 - Zeev Dvir,
*On the size of Kakeya sets in finite fields*, J. Amer. Math. Soc.**22**(2009), no. 4, 1093–1097. MR**2525780**, DOI 10.1090/S0894-0347-08-00607-3 - Uri Erez, Simon Litsyn, and Ram Zamir,
*Lattices which are good for (almost) everything*, IEEE Trans. Inform. Theory**51**(2005), no. 10, 3401–3416. MR**2236418**, DOI 10.1109/TIT.2005.855591 - P. M. Gruber and C. G. Lekkerkerker,
*Geometry of numbers*, 2nd ed., North-Holland Mathematical Library, vol. 37, North-Holland Publishing Co., Amsterdam, 1987. MR**893813** - Peter Gritzmann,
*Lattice covering of space with symmetric convex bodies*, Mathematika**32**(1985), no. 2, 311–315 (1986). MR**834499**, DOI 10.1112/S0025579300011086 - Ishay Haviv, Vadim Lyubashevsky, and Oded Regev,
*A note on the distribution of the distance from a lattice*, Discrete Comput. Geom.**41**(2009), no. 1, 162–176. MR**2470075**, DOI 10.1007/s00454-008-9123-5 - Fritz John,
*Extremum problems with inequalities as subsidiary conditions*, Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, Interscience Publishers, Inc., New York, N. Y., 1948, pp. 187–204. MR**0030135** - Swastik Kopparty, Vsevolod F. Lev, Shubhangi Saraf, and Madhu Sudan,
*Kakeya-type sets in finite vector spaces*, J. Algebraic Combin.**34**(2011), no. 3, 337–355. MR**2836365**, DOI 10.1007/s10801-011-0274-8 - D. Y. Kleinbock and G. A. Margulis,
*Logarithm laws for flows on homogeneous spaces*, Invent. Math.**138**(1999), no. 3, 451–494. MR**1719827**, DOI 10.1007/s002220050350 - M. S. Raghunathan,
*Discrete subgroups of Lie groups*, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 68, Springer-Verlag, New York-Heidelberg, 1972. MR**0507234** - C. A. Rogers,
*Lattice covering of space: The Minkowski-Hlawka theorem*, Proc. London Math. Soc. (3)**8**(1958), 447–465. MR**96639**, DOI 10.1112/plms/s3-8.3.447 - C. A. Rogers,
*Lattice coverings of space*, Mathematika**6**(1959), 33–39. MR**124820**, DOI 10.1112/S002557930000190X - C. A. Rogers,
*Packing and covering*, Cambridge Tracts in Mathematics and Mathematical Physics, No. 54, Cambridge University Press, New York, 1964. MR**0172183** - Wolfgang M. Schmidt,
*The measure of the set of admissible lattices*, Proc. Amer. Math. Soc.**9**(1958), 390–403. MR**96638**, DOI 10.1090/S0002-9939-1958-0096638-X - Carl Ludwig Siegel,
*A mean value theorem in geometry of numbers*, Ann. of Math. (2)**46**(1945), 340–347. MR**12093**, DOI 10.2307/1969027 - Andreas Strömbergsson,
*On the limit distribution of Frobenius numbers*, Acta Arith.**152**(2012), no. 1, 81–107. MR**2869212**, DOI 10.4064/aa152-1-7

## Additional Information

**Or Ordentlich**- Affiliation: School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem 91905, Israel
- MR Author ID: 990513
- ORCID: 0000-0002-5791-7923
**Oded Regev**- Affiliation: Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012
- MR Author ID: 146145
- ORCID: 0000-0002-8616-3163
**Barak Weiss**- Affiliation: School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel
- MR Author ID: 335552
- ORCID: 0000-0002-9296-3343
- Received by editor(s): June 11, 2020
- Received by editor(s) in revised form: April 8, 2021
- Published electronically: July 28, 2021
- Additional Notes: The authors were supported by grants ISF 2919/19, ISF 1791/17, BSF 2016256, the Simons Collaboration on Algorithms and Geometry, a Simons Investigator Award, and by the National Science Foundation (NSF) under Grant No. CCF-1814524.
- © Copyright 2021 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**35**(2022), 295-308 - MSC (2020): Primary 11H31, 94B75, 11T30
- DOI: https://doi.org/10.1090/jams/984
- MathSciNet review: 4322394