Let $\Lambda$ be an $n$-dimensional lattice with basis $b_1,\ldots,b_n$. The problem of finding a "good" basis for $\Lambda$, or reducing a "bad" basis into a good one, is a very active area of research. Most basis reduction schemes try to optimize the norms of the basis vectors and their inner products. The goal is to have a basis that is as nearly orthogonal as possible. A more ambitious goal might be for the basis to make the specification of the Voronoi region (i.e. its face vectors) as simple as possible. The expression "Voronoi reduction" is taken from a publication by Conway and Sloane (Proc. Royal Soc. London A, 436 (1992), 55-68) where it is applied to lattices in dimensions $n\le 3$.

What exactly should be the definition of a Voronoi reduced basis?

Central to the construction of the Voronoi region of $\Lambda$ are the $2^n$ cosets of $2\Lambda$. In particular, for any $x\in \Lambda$ one is interested in the set of minimal norm elements in $x+2\Lambda$. Call this set $S(\Lambda,x)$. One definition of a Voronoi reduced basis might therefore be the following:

A basis $b_1,\ldots,b_n$ for $\Lambda$ is Voronoi reduced if, for any $x\in \Lambda$ and any $y\in S(\Lambda,x)$ the integers $y_1,\ldots,y_n$ in the expansion $y=\sum_{i=1}^n y_i b_i$ always satisfy the bound $|y_i|\le c_n$.

If this is a good definition, then what is the best constant $c_n$?

The Conway-Sloane paper shows that $c_n=1$ for $n\le 3$. In other words, in dimension three and lower there always exists a basis such that the minimal norm vectors of the $2\Lambda$ cosets can be expressed as sums with coefficients limited to $-1, 0, 1$. How fast does $c_n$ grow with $n$? Does it grow at all?


Excellent question. I don't know the answer and perhaps what I am suggesting is obvious. Nevertheless, I think it's on the right track.

Let $B$ be a basis for $\Lambda$ and let $P$ be the corresponding (origin centred) fundamental parallelepiped. That is, $P$ is the region given by $Bu$ where $u \in [-0.5,0.5]^n$. Clearly $2P \cap \Lambda$ contains representatives of $\Lambda/2\Lambda$. However, the elements in $2P \cap \Lambda$ are generally not the minimal length representatives for $\Lambda/2\Lambda$, those are contained in $2\mathcal{V} \cap \Lambda$ where $\mathcal{V}$ is the (closed) Voronoi cell of $\Lambda$.

Let $d$ be the smallest real number such that $\mathcal{V} \subseteq dP$. Clearly $2dP \cap \Lambda$ is a superset of $2\mathcal{V} \cap \Lambda$ and a suitable value of $c$ is therefore $\lfloor d \rfloor$. We can refine this a little by asking for the diagonal matrix $D$ such that $\mathcal{V} \subseteq DP$. Then we have $n$ different $c$'s, specifically $c_i = \lfloor d_i \rfloor$ where $d_i$ are the diagonal elements of $D$.

The problem is now to find the value $d$ (or matrix $D$). That is, how much do we need to scale the fundamental parallelepiped so that it completely contains the Voronoi cell? Perhaps if $R$ is suitably reduced, say LLL reduced or Korkine–Zolotareff reduced, then bounds on $d$ can be found?

| cite | improve this answer | |
  • $\begingroup$ The enclosing parallelepiped is an interesting idea but I don't see how it brings us closer to a bound on $c$. And unless someone comes up with a lattice for which $c>1$, we should probably try to prove $c=1$. $\endgroup$ – Veit Elser Apr 20 '10 at 1:52
  • $\begingroup$ My suspicion is that c will grow with $n$ in general and that even the parallelepiped corresponding to the optimal 'Voronoi reduced basis' (i.e. the basis that yields minimum c) will need to be scaled in order for the Voronoi cell to fit inside the parralellepiped. In 2 and 3 dimensions I am sure that the parallelepiped does need to be scaled, but the optimal scaling in these dimensions, say $d$, is always less than 2 and therefore $c = \lfloor d \rfloor = 1$. I need to have a look at how Conway and Sloane prove that $c=1$ for $n \leq 3$, I haven't had a chance to do this yet. $\endgroup$ – Robby McKilliam Apr 20 '10 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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