Lattice basis consisting of minimal vectors

Question

I have the following theorem that I would like to prove:

Let $\Lambda$ be an $m$-dimensional lattice of $\mathbb{R}^n$, then $\Lambda$ has a basis consisting of $b_1,...,b_m$ with $\|b_j\|= \lambda_j(\Lambda)$ for $1 \leq j \leq min(m,4)$ where $\lambda_j(\Lambda)$ denotes the $j$-th successive minima.

For smaller dimensions, however, I can only find examples that confirm the theorem. How would one prove something like this in general?

I think this is an interesting question that may be of interest to the community here.

Answer 1

The following can be found in Chapter 7 of the textbook "Complexity of Lattice Problems - A Cryptographic Perspective".

There is a polynomial time algorithm that on input a lattice basis $B$ and linearly independent lattice vectors $S \subset \mathcal{L}(B)$ such that $\|s_1\| \leq \|s_2\| \leq \dots \leq \|s_n\|$ outputs a basis $R$ equivalent to $B$ such that $\|r_k\| \leq max\{ (\sqrt{k}/2) \|s_k\|, \|s_k\|\}$ for all $k = 1, \dots, n$. Moreover, the new basis satisfies $span(r_1, \dots, r_k) = span(s_1, \dots, s_k)$ and $\|r_k^*\| \leq \|s_k^*\|$ for all $k = 1, \dots, n$.

In the above, $s_1^*, s_2^*, \dots, s_n^*$ ($r_1^*, r_2^*, \dots, r_n^*$) denotes the Gram-Schmidt orthogonalization of $s_1, s_2, \dots, s_n$ ($r_1, r_2, \dots, r_n$). An immediate corollary which is also stated in the same chapter is as follows.

For any lattice $\Lambda$ of rank $n$, there exists a basis $B$ such that $\|b_k\| \leq max\{1, \sqrt{k}/2\} \cdot \lambda_k(\Lambda)$ for all $k = 1, \cdots, n$.

To find the basis $R$, we can write $S = B V$ where $V \in \mathbb{Z}^{n \times n}$. Observe that $V$ is full-rank but not always unimodular. We can find a unimodular matrix $U$ that represents row-reductions on $V$ to obtain an integer upper triangular matrix $T = UV$.

To get the required basis $R$, we start with $R = BU^{-1}$ and process each vector one at a time so that it meets the required norm bounds. Firstly, we get $S = (BU^{-1})(UV) = RT$ which implies $s_i^* = r_i^* t_{i,i}$ where $t_{i,i}$ is the $i^{th}$ diagonal entry in $T$. Suppose, for all $k < i$, the vector $r_k$ satisfies the bounds. Then, either

• $t_{i,i} = \pm 1$. In this case, we have $r_i^* = \pm s_i^*$ and we can replace $r_i$ with $s_i$. Observe that after this modification, $R$ is still a basis and we get $\|r_i\| = \|s_i\|$.
• $t_{i,i} \neq \pm 1$. In this case, we consider the vector $r' = r_i - r_i^*$ which lies in the space spanned $r_1, \dots, r_{i-1}$. From lattice theory, there exists a lattice vector $v \in \mathcal{L}(r_1, \dots, r_{i-1})$ such that $\|r' - v\| \leq \sqrt{\sum_{k < i} \|r_k^*\|^2}/2$. A simple calculation shows that $\|r_i - v\| \leq \sqrt{i} \|s_i\|/2$ by considering $r_i - v$ as a sum of two orthogonal components - $r_i^*$ and $r' - v$. Therefore, we replace $r_i$ with $r_i - v$.