Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for an algorithm to compute the $n$ shortest lattice vectors in $\mathcal{R}^2$. The problem statement is as follows:

Given a lattice $L: \{ m \vec{u}+n\vec{v} \} \in \mathcal{R}^2$, a norm $\left\lVert\cdot\right\rVert$, and an integer $N>0$, compute a set of $N$ shortest lattice vectors $S$ such that if $\vec{x}\in S$, then for all $\vec{y} \notin S$, $\left\lVert\vec{y}\right\rVert \ge \left\lVert\vec{x}\right\rVert$. One may assume that $\vec{u}$ and $\vec{v}$ are reduced basis vectors returned from Gauss' algorithm.

Ideally, the algorithm can take an existing $S$ and expand it by adding in the next "ring" of vectors with the next greatest norm. I have a rough idea of how to go about doing this for the Euclidean norm; you can move along the perimeter of the already-found vectors and add in new vectors of minimal norm, but I am wondering if it is possible to generalize this to any norm. Even generalizing to $L_1$ or $L_\infty$ norms would be good.

Edit: Description of my algorithm for the $L_2$ norm.

The algorithm seeks to find the next ring of points with the next largest norm (radius from the origin) given an existing ring. We accomplish this by scanning along the "perimeter" of the existing ring, in only one of the dimensions since the other length in the other dimension is roughly known based on the equation of a circle.

  1. Assume you are given the reduced lattice basis vectors $\vec{u}$ and $\vec{v}$, integer coefficients $(a,b)$ such that $a \vec{u} + b\vec{v}$ is one of the points on the existing ring of radius $r$.
  2. Determine the maximum extent we need to scan in the $\vec{u}$ direction: Compute $m>0$ such that $\left\lVert m\vec{u}+n\vec{v} \right\rVert = r$ has no solution for any $n$. This is a simple quadratic equation. Round $m$ away from zero by one to be safe. The amount of time it will take to complete the scan is proportional to $m$.
  3. Initialize $r_b = \infty$, the radius of the best next candidate ring. Initialize the set $S$ of next ring points to empty.
  4. For each $i$ in $-m \le i \le m$, determine $j$ so that $r_c = \left\lVert i\vec{u}+j\vec{v} \right\rVert > r$. If $r_c \lt r_b$, then we found an even smaller ring: set $r_b = r_c$ and set $S = \{i,j\}$. Otherwise if $r_c = r_b$ we found another point on the ring and add $\{i,j\}$ to $S$. Otherwise, if $r_c \gt r_b$, do nothing.

A little thought should convince you that this works. This only works for the $L_2$ norm since it explicitly makes use of the shape of the equi-norm contours. For a general norm, the shape is not known ahead of time.

share|improve this question
    
How do you do it for the Euclidean norm? I can imagine that for arbitrary $\vec{u}$ and $\vec{v}$, the shortest lattice vector can have very large $m$ and $n$. (P.S. You need to escape your curly braces with a backslash, maybe two, to have them show up.) –  Rahul Nov 11 '10 at 1:48
    
@Rahul: See method GetNextPointRing in this file I wrote. That implementation has a number of issues, but the idea is right. –  Victor Liu Nov 11 '10 at 5:40
1  
I hope you agree that understanding someone else's C++ code to answer their mathematics question is a bit of a tall order! Can you edit your question to add the basic idea of your algorithm? –  Rahul Nov 11 '10 at 6:03
1  
Ah, I think I understand your algorithm. Well, a simple approach that would work would be to bound your $L_p$ norm conservatively by the $L_2$ norm when you choose $m$, then in step 4 use the correct $L_p$ norm to compute $r_c$. This way, you'll do at most twice the work in the scan (because $\frac{1}{\sqrt{2}}\lVert x \rVert_2 \le \lVert x \rVert_p \le \sqrt{2}\lVert x \rVert_2$ for all $p \in [1,\infty)$), but you won't miss anything. –  Rahul Nov 11 '10 at 6:54
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.