Skip to main content
added 3 characters in body
Source Link
Michael Hardy
  • 1
  • 12
  • 85
  • 126

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)}$$$$\|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)}$$\|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)}$$\|v_i\|\leq \gamma_{i,n} \det(\Lambda)^{1/(n-i+2)}$?

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

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

edited tags
Link
GH from MO
  • 105.3k
  • 8
  • 293
  • 398
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

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