# Banaszczyk's theorem

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.

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.
• I think you mean $o(1)$ rather than $o(n)$. (Or the term should be taken out of the bracket.) – Emil Jeřábek Jul 25 '19 at 10:13