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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think you mean $o(1)$ rather than $o(n)$. (Or the term should be taken out of the bracket.) $\endgroup$ – Emil Jeřábek Jul 25 '19 at 10:13
  • $\begingroup$ Right, thanks, that was a typo. Fixed. $\endgroup$ – Huck Bennett Jul 25 '19 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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