Let $\Lambda$ be an $n$-dimensional lattice and $\Lambda^*$ be its dual lattice.

For any $k \in \{1, 2, ..., n\}$, let $\lambda_k(\Lambda)$ be the $k$-th successive minima of $\Lambda$ (analogously for $\lambda_k(\Lambda^*)$).

How can we prove that $\lambda_k(\Lambda) \cdot \lambda_{n-k+1}(\Lambda^*) \ge 1$ ?

That comes from the following exercise of a Micciancio's course from 2014:

Prove that for any $n$-dimensional lattice $\Lambda$, $\lambda_1(\Lambda)\cdot \lambda_{n}(\Lambda^*) \ge 1$. More generally, prove that for any $k$, $\lambda_k(\Lambda) \cdot \lambda_{n-k+1}(\Lambda^*) \ge 1$. [Hint: For the first part, consider the scalar products between a shortest lattice vector and $n$ short linearly independent vectors from the dual lattice.]

Using the hint, I could solve the first part like this:

Take $v \in \Lambda$ and $x_i \in \Lambda^*$ such that $||v|| = \lambda_1(\Lambda)$ and $||x_i|| = \lambda_i(\Lambda^*)$ for $1 \le i \le n$.

Observe that $\langle v, x_i \rangle \in \mathbb{Z}- \{0\}$ for some $i$, because $\langle v, x_i \rangle$ must be different from zero for some $i$ (otherwise, we would have $n+1$ orthogonal vectors in an $n$-dimensional space) and $\langle v, x_i \rangle$ is integer by definition of dual lattice.

So, $1 \le |\langle v, x_i \rangle| \le ||v|| \cdot ||x_i|| \le \lambda_1(\Lambda)\cdot \lambda_i(\Lambda^*) \le \lambda_1(\Lambda)\cdot \lambda_n(\Lambda^*)$.

But how to generalize that argument for any $k$?


Your Answer

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

Browse other questions tagged or ask your own question.