Banaszczyk's theorem

Question

Banaszczyk's theorem states that if $\Lambda$ is a rank-$m$ lattice with dual lattice $\Lambda^*$, then $\lambda_1(\Lambda) \cdot \lambda_m(\Lambda^*) \leq m$.

Can someone point me to a clean proof of this theorem? The proofs I am aware of in various lecture notes all lose a factor of 2 in the bound. And while Banaszczyk's paper is available, it is hard to read and seems to have this theorem buried among other results.

Answer 1

Divesh Aggarwal and Noah Stephens-Davidowitz very recently posted a preprint improving the constant in the upper bound of Banaszczyk's theorem: https://arxiv.org/abs/1907.09020. Specifically, they show that $\lambda_1(\Lambda)\mu(\Lambda^*) \leq (0.1275 + o(1)) n$, which combined with the upper bound $\lambda_n(\Lambda^*) \leq 2 \mu(\Lambda^*)$ implies that $\lambda_1(\Lambda)\lambda_n(\Lambda^*) \leq (2 \cdot 0.1275 + o(1)) n$. (Here $\mu$ denotes the covering radius of a lattice.)

Note that you state the upper bound with constant 1 (as is commonly done for convenience), whereas Banaszczyk's original work already shows that the bound holds with the improved constant $1/\pi$. In other words, the bound that you state is already off by a factor larger than 2.

Oded Regev's lecture notes also give a self-contained proof without worrying about getting the best possible constant. (It seems that you're likely already aware of these notes.)