Successive minima and the basis of lattice

Question

I am able to prove the following two propositions: Recall that the $i$-th successive minimum of $L\in \mathcal L$, denoted $\lambda_i(L)$ is the infimum of the radii of the balls containing $i$-linearly independent vectors in $L$. All norms are Euclidean 2-norm.

Let $\Lambda$ be a lattice $\mathbb R^d$. Assume that $d\le 4$, then there exist a basis $\{v_1,\dots,v_d\}$ of $\Lambda$ such that $$\|v_j\|=\lambda_j(\Lambda), ~\text{for}~ j=\{1,2,\dots,d\}.$$

and

Let $\Lambda$ be a lattice in $\mathbb R^d$. Then there exist a basis $v_1,v_2,\dots,v_d$ of $\Lambda$ such that $$\|v_1\|=\lambda_1(\Lambda),\|v_2\|_d \asymp_d \lambda_2(\Lambda),\dots,\|v_d\| \asymp_d \lambda_d(\Lambda).$$

But I am very puzzled if the follow combination of the above two is true:

Let $\Lambda$ be a lattice in $\mathbb R^d$. Then there exist a basis $v_1,v_2,\dots,v_d$ of $\Lambda$ such that $$\|v_i\|=\lambda_i(\Lambda) (1\le i \le 4),\|v_5\|_d \asymp_d \lambda_5(\Lambda),\dots,\|v_d\| \asymp_d \lambda_d(\Lambda).$$

Is the last statement correct? I don't see how it follows from the previous two statements directly. There is some magic with the dimension 4. The example $\text{Span}\{e_1,e_2,\dots, e_d, \frac{1}{2}(e_1+\dots+e_d)\}$ provides the obstruction for the reduction process for $d\ge 5$.

Answer 1

Jacques Martinet has a paper that proves a result like this "on average". For a lattice $\Lambda$, define $H_b(\Lambda) = \min_{\{v_i\}_i\text{ a basis of }\Lambda}\frac{\prod_{i}^n \lVert v_i\rVert_2}{\det \Lambda}$, $M(\Lambda) = \frac{\prod_{i = 1}^n \lambda_i(\Lambda)}{\det \Lambda}$, and $Q_b(\Lambda) = \frac{H_b(\Lambda)}{M(\Lambda)}$.

Then

Theorem 1.2 For $n\geq 4$, we have that $Q_b(\Lambda) \leq \sqrt{5/4}^{n-4}$

Theorem 1.3 For $4\leq n\leq 8$, we have that $Q_b(\Lambda) \leq\sqrt{n}/2$.

Note that Martinet's quantities are actually the square of what I quote, but his convention is to define things in terms of the squares of the relevant norms.

Anyway, I say this establishes your result "on average" as the two sequences can only differ "on average" by a constant multiplicative factor $\sqrt{5/4}$ on each term.

Answer 2

It seems that there is a positive, and optimal answer to the question asked by the OP, which makes the number $d = 4$ appear naturally.

For every lattice $\Lambda \subseteq \mathbb{R}^d$ there exists a basis $v_1,\dots,v_d$ of $\Lambda$ such that $\lVert v_j \rVert \leq \max(1,\frac{1}{2}\sqrt{j}) \lambda_j(\Lambda)$ for every $j \in \{1,\dots,d\}$.

For such a basis, we clearly have that $\lVert v_j \rVert = \lambda_j(\Lambda)$ whenever $j \in \{1,\dots,4\}$.

The proof of such a theorem seems surprisingly simple, as it uses only the possibility of performing a form Gauss's reduction algorithm over the integers (e.g. the existence of Hermite's normal form), and the fact that if $b_1,\dots,b_r$ is a basis of a lattice $L$, and $v \in \langle b_1,\dots,b_r \rangle_\mathbb{R}$ then there exists a lattice vector $w \in L$ such that $4 \lVert v - w \rVert^2 \leq \sum_{j=1}^r \lVert b_j \rVert^2$.

A proof of this result can be found in Lemma 7.1 of the book "Complexity of Lattice Problems" by Micciancio and Goldwasser. I personally learnt about this result on Math Stackexchange (Question 4532410), where a similar question was asked.