# 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$$