Saturday, 28 June 2008

mg.metric geometry - How to define a Voronoi reduced basis?

Let Lambda be an n-dimensional lattice with basis b1,ldots,bn. 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 nle3.




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




Central to the construction of the Voronoi region of Lambda are the 2n cosets of 2Lambda. In particular, for any xinLambda 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 b1,ldots,bn for Lambda is Voronoi reduced if, for any xinLambda and any yinS(Lambda,x) the integers y1,ldots,yn in the expansion y=sumni=1yibi always satisfy the bound |yi|lecn.




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




The Conway-Sloane paper shows that cn=1 for nle3. 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 cn grow with n? Does it grow at all?

No comments:

Post a Comment