Proof for the successive minima being achieved by linearly independent lattice vectors?

Question

In https://arxiv.org/abs/2305.19777, there is a fact stated as folklore. Here it is.

Fact 2.7 (Folklore). For any $q\in\mathbb{N}$, lattice $\mathcal{L}\in\mathbb{R}^n$ of rank $k$ there exist linear independent vectors $u_1,\dots,u_k\in\mathcal{L}$ such that $\|u_i\|_q = \lambda_i^{(q)}(\mathcal{L})$.

In the statement, the $\lambda_i^{(q)}(\mathcal{L})$ are the successive minima defined with the $q$-norm.

This seems to be common knowledge. But as a novice in the field, I don't see how it follows from the definition of the successive minima. Can someone point me to some references that proves this common knowledge?

Answer 1

Let's revisit the definition of successive minima from Regev's lecture note.

Let $\mathcal{L} \in \mathbb{R}^n$ be a lattice of rank $k$. For $i \in [k]$, the $i^{th}$ successive minimum is defined as $$\lambda_i^{(q)}(\mathcal{L}) = \min \left\{r \;|\; dim \left(span(\mathcal{L} ) \cap \overline{B}^{(q)}(0, r) \right) \geq i \right\}$$ where $\overline{B}^{(q)}(0, r) = \{x \in \mathbb{R}^n \;|\; \|x\|_q \leq r\}$.

To put it simply, $\lambda_i^{(q)}(\mathcal{L})$ is the radius of the smallest $n$-dimensional sphere centered at the origin that contains at least $i$ linearly independent lattice vectors of $\mathcal{L}$. Consequently, $\lambda_1^{(q)}(\mathcal{L})$ corresponds to the length of the shortest vector of $\mathcal{L}$.

Now, let's show using induction that we can always find linearly independent $u_1, \dots, u_k \in \mathcal{L}$ such that $\|u_i\|_q = \lambda_i^{(q)}(\mathcal{L})$. Let $S_i = \{v \in \mathcal{L} \setminus \{0\} \;|\; \|v\|_q \leq \lambda_i^{(q)}(\mathcal{L})\}$, i.e., it is the set of all non-zero lattice vectors with norm less than equal to $\lambda_i^{(q)}(\mathcal{L})$. By the definition of successive minimum, we have $dim(span(S_i)) \geq i$. Clearly, $S_1$ contains all the shortest vectors of $\mathcal{L}$, allowing us to find $u_1$ as the shortest vector.

Suppose, we have picked $u_1, \dots, u_{i-1}$ such that $\|u_j\|_q = \lambda_j^{(q)}(\mathcal{L})$ for all $j < i$. Also, $\|u_j\|_q \leq \|u_{j+1}\|_q$ for all $j < i-1$. Observe that $u_1, \dots, u_{i-1} \in S_i$ by definition. Since there are at least $i$ linearly independent vectors in $S_i$, there is a vector $u_i \in S_i$ linearly independent from $u_1, \dots, u_{i-1}$. I claim that $\|u_i\|_q = \lambda_{i}^{(q)}(\mathcal{L})$. Assuming not, i.e., $\|u_i\|_q < \lambda_{i}^{(q)}(\mathcal{L})$, would contradict the definition of $\lambda_{i}^{(q)}(\mathcal{L})$ because it is the radius of the smallest sphere containing at least $i$ many linearly independent lattice vectors. However, $u_1, \dots, u_i$ would be contained in a smaller radius sphere and are linearly independent. Hence, it must be $\|u_i\|_q = \lambda_{i}^{(q)}(\mathcal{L})$.