I am new to lattice theory. I hope(will be grateful) that one could explain to me this claim 7 in REGEV course(this claim appears in this file page 6 : https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/introduction.pdf) which states that : The successive minima of a lattice are achieved i.e., for every 1 ≤ i ≤ n, there exists a vector vi ∈ Λ with ‖v_{i}‖ = λi(Λ).

Thank you,


1 Answer 1


Claim 7: The successive minima of a lattice are achieved i.e., for every $1 \leq i \leq n$, there exists a vector $v_i \in \Lambda$ with $\lVert v_{i}\rVert = \lambda_i(\Lambda)$.

There is a proof of that claim

Proof: By Corollary 6, the ball of radius (say) $2\lambda_i(\Lambda)$ contains only finitely many lattice points. It follows from the definition of $\lambda_i$ that one of these vectors must have length $\lambda_i(\Lambda)$.

This suggests we should look at two places

Corollary 6: Let $\Lambda$ be a lattice. Then there exists some $\epsilon > 0$ such that $\lVert x − y\rVert > \epsilon$ for any two non-equal lattice points $x, y \in\Lambda$.

Definition 7: Let $\Lambda$ be a lattice of rank $n$. For $i \in \{1, \dots , n\}$ we define the $i$th successive minimum as $\lambda_i(\Lambda) = \inf \{r \mid \dim(\mathsf{span}(\Lambda ∩ \overline{B}(0, r))) \geq i\}$ where $\overline{B}(0, r) = \{x \in\mathbb{R}^m \mid \lVert x\rVert \leq r\}$ is the closed ball of radius $r$ around $0$.

How does this proof follow? Consider $\overline{B}(0, \lambda_i(\Lambda))\cap \Lambda$. By definition, this contains at least $i$ linearly independent lattice vectors (and is the smallest ball such that this occurs). This is to say that shrinking the ball leads to a set containing at most $i-1$ linearly independent lattice vectors, i.e. the $i$th linearly independent lattice vector is on the surface of this ball.

Why does the claim state

the ball of radius (say) $2\lambda_i(Λ)$R contains only finitely many lattice points $\dots$

$\lambda_i(\Lambda)$ is defined with an infimum. This is an "infinite" version of $\min$ (similarly to how $\sup$ is an "infinite" version of $\max$). In particular, it is important to know that for a sequence $a_i$, $\inf a_i = a$ does not mean there is any particular index $i^*$ such that $a_{i^*} = a$. For example, $a_i = i^{-1}$ (for $i > 0$) has an infimum of $0$ (as $i\mapsto 0^+$), but never achieves this limit.

This means that there was some risk that there is some infinite sequence of lattice points such that $\lVert \vec v_i\rVert\mapsto \lambda_i(\Lambda)$ in the limit, but there is no index $i$ such that this equality holds. The proof handles this via noting that infimum (supremum) and min (max) agree on finite sets. Since we are restricting to a finite set, we can replace the $\inf$ with a $\min$, and note that it must be achieved by some element of the finite set.

  • $\begingroup$ what a great, unambiguous answer ! thanks a lot. $\endgroup$
    – vinod
    Feb 14 at 14:40

Your Answer

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

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