How to define a Voronoi reduced basis?

Question

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?

Answer 1

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?

Answer 2

While this question is quite old, a recent paper is perhaps of significant intrerest to it. Hunkenschröder, Reuland, and Schymura in on compact representations of Voronoi cells of lattices. They show (among other things) that:

1. For any lattice, one can find a basis $B$ such that $c_n \leq n^2$
2. There exists a family of lattices $\Lambda_n$ in dimension $n$ such that one must take $c_n = \Omega(n)$