Paper 2018/188

Kissing numbers and transference theorems from generalized tail bounds

Stephen D. Miller and Noah Stephens-Davidowitz

Abstract

We generalize Banaszczyk's seminal tail bound for the Gaussian mass of a lattice to a wide class of test functions. From this we obtain quite general transference bounds, as well as bounds on the number of lattice points contained in certain bodies. As applications, we bound the lattice kissing number in $\ell_p$ norms by $e^{n+o(n)}/p$ for $0<p\leq2$, and also give a proof of a new transference bound in the $\ell_1$ norm.

Note: Preprint, 15 pages.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. SIDMA, 2019
Keywords
lattice techniquesnumber theory
Contact author(s)
miller @ math rutgers edu
noahsd @ gmail com
History
2019-07-21: revised
2018-02-20: received
See all versions
Short URL
https://ia.cr/2018/188
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/188,
      author = {Stephen D.  Miller and Noah Stephens-Davidowitz},
      title = {Kissing numbers and transference theorems from generalized tail bounds},
      howpublished = {Cryptology ePrint Archive, Paper 2018/188},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/188}},
      url = {https://eprint.iacr.org/2018/188}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.