Score:3

The successive minima of a lattice

vu flag

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,

Score:6
ng flag

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.

vinod avatar
eu flag
what a great, unambiguous answer ! thanks a lot.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.