# Lowering $i$th shortest vector of a lattice

LLL guarantees that we can find a basis $$v_1,\dots,v_n$$ of a lattice in $$\mathbb R^n$$ with

$$\|v_i\|\leq \gamma_{i,n} \det(\Lambda)^{1/(n-i+1)}$$ where $$\gamma_i$$ is a function only of $$i$$ and $$n$$.

1. Are there lattices where this cannot be improved to $$\|v_i\|\leq \gamma_{i,n} \det(\Lambda)^{1/(n-i+2)}$$?

2. In general are there algorithms (possibly in exponential time) which can guarantee $$\|v_i\|\leq \gamma_{i,n} \det(\Lambda)^{1/(n-i+2)}$$?

There are lattices where your requirement cannot be met. In fact if you fix any lattice $$\Lambda_0$$ and you dilate it by a factor of $$R$$, then its determinant gets scaled by $$R^n$$, while its shortest lattice vector gets scaled by $$R$$. However, your inequality $$\|v_1\|\ll_n\det(\Lambda)^{1/(n+1)}$$ would yield that the shortest lattice length grows at most at the rate of $$R^{n/(n+1)}$$, which is a contradiction.
You can get further lower bounds on the lengths of the basis vectors by using Minkowski's theorem that the successive minima of $$\Lambda$$ satisfy $$\lambda_1\lambda_2\dots\lambda_n\asymp_n\det(\Lambda).$$ Note also that the reduced basis produced by the LLL algorithm is optimal in the sense that the length of the $$i$$-th basis vector is $$\asymp_n\lambda_i$$. This is explicitly mentioned in the original paper of Lenstra-Lenstra-Lovász (1982), see their remark below (1.13).
• So the scaling $n-i+1$ cannot be improved to $n-i+1+\epsilon$ for any fixed $\epsilon>0$? – T.... Jan 11 '19 at 4:20
• @Freeman. That's right. You cannot even change $\gamma_{1,n}$ to $o(1)$ in the origial bound. – GH from MO Jan 11 '19 at 4:22