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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ So the scaling $n-i+1$ cannot be improved to $n-i+1+\epsilon$ for any fixed $\epsilon>0$? $\endgroup$
    – Turbo
    Jan 11, 2019 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, 2019 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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