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

| cite | improve this question | | | | |
$\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).

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ So the scaling $n-i+1$ cannot be improved to $n-i+1+\epsilon$ for any fixed $\epsilon>0$? $\endgroup$ – T.... Jan 11 '19 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 '19 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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