New bounds on the density of lattice coverings
HTML articles powered by AMS MathViewer
- by Or Ordentlich, Oded Regev and Barak Weiss;
- J. Amer. Math. Soc. 35 (2022), 295-308
- DOI: https://doi.org/10.1090/jams/984
- Published electronically: July 28, 2021
- HTML | PDF | 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, New York, 1948, pp. 187–204. MR 30135
- 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 [Results in Mathematics and Related Areas], Band 68, Springer-Verlag, New York-Heidelberg, 1972. MR 507234
- 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 172183
- 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
Bibliographic 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