# Other norms for Lattice reduction techniques (LLL, PSLQ)?

LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $\varepsilon$ as its shortest vector, $\varepsilon \in \mathbb{Z}^n$, find a short vector s.t. $b \in \mathbb{Z}^n, ||b||_2 < ||c^n \varepsilon||_2$.

Has there been any work done to find short vectors based on other, potentially higher, norms? Is this a meaningful question?

-
All norms on a finite-dimensional vector space are equivalent, so a short vector in any one norm will be a (fairly) short vector in any other norm, no? – Gerry Myerson Sep 3 '10 at 3:04
Gerry, I think you're right about the equivalence and thus the short vector for all norms. It looks like $\forall p, \exists r_p, R_p s.t. r_p ||x||_p \le ||x||_2 \le R_p ||x||_p$. – dorkusmonkey Sep 3 '10 at 20:07

The state of the art (of the possible) is covered in Khot's paper "Inapproximability Results for Computational Problems on Lattices". Here is a link to a brief section on $\ell^p$ norms.

-
Thank you. I think I was hoping for better algorithms with higher norms, but this is essentially saying that they're pretty much all equivalent computationally, yes? – dorkusmonkey Sep 4 '10 at 11:40

There is an LLL analogue for arbitrary norms; the original paper by Lovász and Scarf can be found here. I recently found a bachelor thesis on lattice reduction in infinity norm, which contains several other references (for example, work by Kaib and Ritter).

-