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
    Commented 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
    Commented Jan 11, 2019 at 4:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .