2
$\begingroup$

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)}$?

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ So the scaling $n-i+1$ cannot be improved to $n-i+1+\epsilon$ for any fixed $\epsilon>0$? $\endgroup$ – Freeman. Jan 11 at 4:20
  • $\begingroup$ @Freeman. That's right. You cannot even change $\gamma_{1,n}$ to $o(1)$ in the origial bound. $\endgroup$ – GH from MO Jan 11 at 4:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.