Minkowski reduced

Definition

The basis$\left\{b_i\right\}_{i=1}^d$ is Minkowski-reduced if $b_i$has minimum length among all vectors in $L$ linearly independent from$\left\{b_j\right\}_{j=1}^{i-1}$. Equivalently, $b_i$has minimum length among all vectors $v$such that $\left\{b_1,\dots,b_{i-1},v\right\}$can be extended to form a basis of$L$. Such a notion is strongest among all lattice reduction notions and is generally extremely hard to compute. Another equivalent definition is

$$\left\lVert b_i\right\rVert\leq\left\lVert\sum_{j=i}^dc_jb_j\right\rVert\quad\gcd\left(c_j\right)=1$$

Bounds

$$\lambda_i(L)^2\leq\left\lVert b_i\right\rVert^2\leq\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2$$

The proof presented here is based off [Waerden 1956]. We proceed by induction. Let$b_i$be a Minkowski-reduced basis for some lattice$L$. The lower bound is immediate and for $i=1$, the upper bound is immediate as well.

Let $v_1,v_2\dots v_i$be linearly independent vectors such that$\left\lVert v_j\right\rVert=\lambda_j(L)$. Let $L_{i-1}$be the sublattice generated by $b_1,b_2,\dots b_{i-1}$. Evidently some$k$must exist such that$v_k$is not in $L_{i-1}$. Consider the new lattice $L'=L\cap\text{span}\left(b_1,b_2,\dots b_{i-1},v_k\right)$. Let$v'_k$be the shortest vector in$L'-L_{i-1}$such that$b_1,b_2,\dots,b_{i-1},v'_k$is a basis for $L'$and we have

$$v_k=a_1b_1+a_2b_2+\dots+a_{i-1}b_{i-1}+nv'_k\quad a_i,n\in\mathbb Z\\ \left\lVert b_i\right\rVert\leq\left\lVert v'_k\right\rVert$$

If$n=1$, then we are done since$v_k$can be extended to a basis of $L$, so $\left\lVert b_i\right\rVert\leq\left\lVert v_k\right\rVert=\lambda_k(L)\leq\lambda_i(L)$. Otherwise, we have $n^2\geq4$. Let $v_k'=p+q$where$p$is the projection of$v'_k$in$L_{i-1}$. Since by definition we have$\left\lVert p\right\rVert^2\leq\left\lVert p\pm b_i\right\rVert^2$, we must have

$$\left\lVert p\right\rVert^2\leq\frac14\sum_{j=1}^{i-1}\left\lVert b_j\right\rVert^2$$

Furthermore, since

$$\lambda_k^2=\left\lVert v_k\right\rVert^2=\left\lVert a_1b_1+a_2b_2+\dots a_{i-1}b_{i-1}+p\right\rVert^2+n^2\left\lVert q\right\rVert^2$$

we have $\left\lVert q\right\rVert^2\leq\frac14\lambda_k^2$, hence we have

$$\begin{align*} \left\lVert b_i\right\rVert&\leq\frac14\sum_{j=1}^{i-1}\left\lVert b_j\right\rVert^2+\frac14\lambda_k^2\\ &\leq\frac14\sum_{j=1}^{i-1}\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_j(L)^2+\frac14\lambda_k(L)^2\\ &\leq\frac14\left(1+\sum_{j=1}^{i-1}\max\left(1,\left(\frac54\right)^{i-4}\right)\right)\lambda_i(L)^2\\ &\begin{cases}=\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2&i\geq4\\<\lambda_i(L)^2&i=2,3\end{cases}\\ \end{align*}$$

but since $\lambda_i(L)^2\leq \left\lVert b_i\right\rVert^2$by definition, the case of $i=2,3$cannot occur here (hence $n=1$in these cases).

Exercises

1) Show that both definitions of Minkowski-reduced lattice are equivalent

2) Consider the lattice $L=\begin{pmatrix}2&0&0&0&0\\0&2&0&0&0\\0&0&2&0&0\\0&0&0&2&0\\1&1&1&1&1\end{pmatrix}$. We have showed in a previous exercise that the successive minima are all$2$but no basis$b_i$can satisfy $\left\lVert b_i\right\rVert=\lambda_i$, show that for any Minkowski reduced basis $b_i$, the basis must satisfy $\left\lVert b_i\right\rVert^2=\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2$