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

<p>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 <span class="math-container">$1/\pi$</span>. In other words, the bound that you state is already off by a factor larger than 2.</p>

<p>Oded Regev's <a href="https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/transference.pdf" rel="nofollow noreferrer">lecture notes</a> 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.)</p>

CC BY-SA 4.0
2019-07-25T10:13:44.150Z
I think you mean $o(1)$ rather than $o(n)$. (Or the term should be taken out of the bracket.)
Emil Jeřábek
CC BY-SA 4.0
2019-07-25T15:01:02.557Z
Right, thanks, that was a typo. Fixed.
Huck Bennett
CC BY-SA 4.0
2019-07-23T22:56:42.173Z
2019-07-25T15:06:16.753Z
2019-07-25T15:06:16.753Z
Huck Bennett
<p>Banaszczyk's theorem states that if <span class="math-container">$\Lambda$</span> is a rank-<span class="math-container">$m$</span> lattice with dual lattice <span class="math-container">$\Lambda^*$</span>, then <span class="math-container">$\lambda_1(\Lambda) \cdot \lambda_m(\Lambda^*) \leq m$</span>. </p>

<p>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.</p>

<integer-lattice>
Banaszczyk's theorem
user6584
# Banaszczyk's theorem

(Asked by: username_0 on 2019-07-23)

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.

**Tags:** integer-lattice

---

## 1 answers

### Answer by username_1 on 2019-07-23. Score: 7

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](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/transference.pdf) 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.)

> **Comments:**
> **username_2**: I think you mean $o(1)$ rather than $o(n)$. (Or the term should be taken out of the bracket.)  
> **username_1**: Right, thanks, that was a typo. Fixed.  

---

