Minkowski reduced

Definition

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

bij=idcjbjgcd(cj)=1\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

λi(L)2bi2max(1,(54)i4)λi(L)2\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. Letbib_ibe a Minkowski-reduced basis for some latticeLL. The lower bound is immediate and for i=1i=1, the upper bound is immediate as well.

Let v1,v2viv_1,v_2\dots v_ibe linearly independent vectors such thatvj=λj(L)\left\lVert v_j\right\rVert=\lambda_j(L). Let Li1L_{i-1}be the sublattice generated by b1,b2,bi1b_1,b_2,\dots b_{i-1}. Evidently somekkmust exist such thatvkv_kis not in Li1L_{i-1}. Consider the new lattice L=Lspan(b1,b2,bi1,vk)L'=L\cap\text{span}\left(b_1,b_2,\dots b_{i-1},v_k\right). Letvkv'_kbe the shortest vector inLLi1L'-L_{i-1}such thatb1,b2,,bi1,vkb_1,b_2,\dots,b_{i-1},v'_kis a basis for LL'and we have

vk=a1b1+a2b2++ai1bi1+nvkai,nZbivkv_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

Ifn=1n=1, then we are done sincevkv_kcan be extended to a basis of LL, so bivk=λk(L)λi(L)\left\lVert b_i\right\rVert\leq\left\lVert v_k\right\rVert=\lambda_k(L)\leq\lambda_i(L). Otherwise, we have n24n^2\geq4. Let vk=p+qv_k'=p+qwhereppis the projection ofvkv'_kinLi1L_{i-1}. Since by definition we havep2p±bi2\left\lVert p\right\rVert^2\leq\left\lVert p\pm b_i\right\rVert^2, we must have

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

Furthermore, since

λk2=vk2=a1b1+a2b2+ai1bi1+p2+n2q2\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 q214λk2\left\lVert q\right\rVert^2\leq\frac14\lambda_k^2, hence we have

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

Exercises

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

2) Consider the lattice L=(2000002000002000002011111)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 all22but no basisbib_ican satisfy bi=λi\left\lVert b_i\right\rVert=\lambda_i, show that for any Minkowski reduced basis bib_i, the basis must satisfy bi2=max(1,(54)i4)λi(L)2\left\lVert b_i\right\rVert^2=\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2