An improved constant in Banaszczyk's transference theorem

An improved constant in Banaszczyk's transference theorem. Aggarwal, D. & Stephens-Davidowitz, N. 2019.

$ \newcommand{\R}{\ensuremath{ℝ}} \newcommand{łat}{\mathcal{L}} \newcommand{\ensuremath}[1]{#1} $We show that \[ μ(łat) λ_1(łat^*) < \big( 0.1275 + o(1) \big) · n , \] where $μ(łat)$ is the covering radius of an $n$-dimensional lattice $łat ⊂ \R^n$ and $λ_1(łat^*)$ is the length of the shortest non-zero vector in the dual lattice $łat^*$. This improves on Banaszczyk's celebrated transference theorem (Math. Annal., 1993) by about 20%. Our proof follows Banaszczyk exactly, except in one step, where we replace a Fourier-analytic bound on the discrete Gaussian mass with a slightly stronger bound based on packing. The packing-based bound that we use was already proven by Aggarwal, Dadush, Regev, and Stephens-Davidowitz (STOC, 2015) in a very different context. Our contribution is therefore simply the observation that this implies a better transference theorem.

@unpublished{ASImprovedConstant19,
	title = {An improved constant in {{Banaszczyk}}'s transference theorem},
	url = {http://arxiv.org/abs/1907.09020},
	author = {Aggarwal, Divesh and {Stephens-Davidowitz}, Noah},
	year = {2019},
	abstract = {$ \newcommand{\R}{\ensuremath{\mathbb{R}}} \newcommand{\lat}{\mathcal{L}} \newcommand{\ensuremath}[1]{#1} $We show that \[ \mu(\lat) \lambda_1(\lat^*) < \big( 0.1275 + o(1) \big) \cdot n \; , \] where $\mu(\lat)$ is the covering radius of an $n$-dimensional lattice $\lat \subset \R^n$ and $\lambda_1(\lat^*)$ is the length of the shortest non-zero vector in the dual lattice $\lat^*$. This improves on Banaszczyk's celebrated transference theorem (Math. Annal., 1993) by about 20%. Our proof follows Banaszczyk exactly, except in one step, where we replace a Fourier-analytic bound on the discrete Gaussian mass with a slightly stronger bound based on packing. The packing-based bound that we use was already proven by Aggarwal, Dadush, Regev, and Stephens-Davidowitz (STOC, 2015) in a very different context. Our contribution is therefore simply the observation that this implies a better transference theorem.},
}

Downloads: 40