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 $nle 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 $2Lambda$. In particular, for any $xin Lambda$ one is interested in the set of minimal norm elements in $x+2Lambda$. 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 $xin Lambda$ and any $yin 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 $nle 3$. In other words, in dimension three and lower there always exists a basis such that the minimal norm vectors of the $2Lambda$ 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?
No comments:
Post a Comment