4
$\begingroup$

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.

$\endgroup$

1 Answer 1

7
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ I think you mean $o(1)$ rather than $o(n)$. (Or the term should be taken out of the bracket.) $\endgroup$ Commented Jul 25, 2019 at 10:13
  • $\begingroup$ Right, thanks, that was a typo. Fixed. $\endgroup$ Commented Jul 25, 2019 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.