MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this 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
up vote 5 down vote accepted

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.

share|cite|improve this answer
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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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