arXiv:math/0408122v3 [math.NT] 6 Mar 2005 Perfect Delaunay polytopes and Perfect Inhomogeneous Forms Robert Erdahl, Andrei Ordine, and Konstantin Rybnikov June 11, 2004 Abstract A lattice Delaunay polytope D is called perfect if it has the prop- erty that there is a unique circumscribing ellipsoid with interior free of lattice points, and with the surface containing only those lattice points that are the vertices of D. An inhomogeneous quadratic form is called perfect if it is determined by such a circumscribing ”empty ellipsoid” uniquely up to a scale factor. Perfect inhomogeneous forms are associated with perfect Delaunay polytopes in much the way that perfect homogeneous forms are associated with perfect point lattices. We have been able to construct some infinite sequences of perfect De- launay polytopes, one perfect polytope in each successive dimension starting at some initial dimension; we have been able to construct an infinite number of such infinite sequences. Perfect Delaunay poly- topes are intimately related to the theory of Delaunay polytopes, and to Voronoi’s theory of lattice types. 1 Introduction Consider the lattice Z d , and a lattice polytope D. If D can be circumscribed by an ellipsoid E = ∂ { x ∈ R d f (x) ≤ R 2 }, where f is a quadratic function in x 1 ,...,x d , with no Z d -elements interior to { x ∈ R d vert f (x) ≤ R 2 }, and with all Z d -elements on E being the vertices of D, we will say that D is a Delaunay polytope with respect to the metric form defined by E; more informally, we will say that D is Delaunay if it can be circumscribed by an empty ellipsoid E. Typically there is a family of empty ellipsoids that 1
Transcript
arX
iv:m
ath/
0408
122v
3 [
mat
h.N
T]
6 M
ar 2
005 Perfect Delaunay polytopes and Perfect
Inhomogeneous Forms
Robert Erdahl, Andrei Ordine, and Konstantin Rybnikov
June 11, 2004
Abstract
A lattice Delaunay polytope D is called perfect if it has the prop-
erty that there is a unique circumscribing ellipsoid with interior free
of lattice points, and with the surface containing only those lattice
points that are the vertices of D. An inhomogeneous quadratic form
is called perfect if it is determined by such a circumscribing ”empty
ellipsoid” uniquely up to a scale factor. Perfect inhomogeneous forms
are associated with perfect Delaunay polytopes in much the way that
perfect homogeneous forms are associated with perfect point lattices.
We have been able to construct some infinite sequences of perfect De-
launay polytopes, one perfect polytope in each successive dimension
starting at some initial dimension; we have been able to construct an
infinite number of such infinite sequences. Perfect Delaunay poly-
topes are intimately related to the theory of Delaunay polytopes, and
to Voronoi’s theory of lattice types.
1 Introduction
Consider the lattice Zd, and a lattice polytope D. If D can be circumscribed
by an ellipsoid E = ∂{x ∈ Rd f(x) ≤ R2}, where f is a quadratic function
in x1, . . . , xd, with no Zd-elements interior to {x ∈ R
d vert f(x) ≤ R2},and with all Z
d-elements on E being the vertices of D, we will say that Dis a Delaunay polytope with respect to the metric form defined by E; moreinformally, we will say that D is Delaunay if it can be circumscribed byan empty ellipsoid E. Typically there is a family of empty ellipsoids that
can be circumscribed about a given Delaunay polytope D but, if there isonly one, so that E is uniquely determined by D, we will say that D is aperfect Delaunay polytope. Perfect Delaunay polytopes are distinguished inthat they cannot fit properly inside other lattice Delaunay polytopes. PerfectDelaunay polytopes are fascinating geometrical objects – examples are thesix and seven dimensional Gossett polytopes with 27 and 56 vertices knownas 221 and 321 in Coxeter’s notation, which appear in the Delaunay tilingsfor the quadratic forms corresponding to the root lattices E6 and E7.
We have studied perfect Delaunay polytopes by constructing infinite se-quences of them, one perfect Delaunay polytope in each successive dimension,starting at some initial dimension. We have been able to construct an infi-nite number of infinite sequences of perfect Delaunay polytopes. One of ourconstructions is the sequence of G-topes, Gd, d = 6, 7, ... , with the initialterm being the six-dimensional Gossett polytope 221 with 27 vertices; eachG-tope is asymmetric with respect to central inversion, and Gd has
(d+22
)− 1
vertices. Another construction is the sequence of C-topes, Cd, d = 7, 8, ... ,with initial term the seven-dimensional Gossett polytope 331 with 56 vertices;each C-tope is symmetric with respect to central inversion, and Cd has 2
(d+12
)
vertices. Just as the six-dimensional Gossett polytope can be represented asa section of the seven dimensional one, each term Gd of the asymmetric se-quence can be represented as a section of the term Cd+1 of the symmetricsequence.
Each perfect Delaunay polytope in the sequence of G-topes uniquely de-termines a lattice that is an analogue of the root lattice E6, and each termin the sequence of C-topes uniquely determines a lattice that is an analogueof the root lattice E7. The Voronoi and Delaunay tilings for the lattices inthese sequences of lattices show many features of the lead terms, namely, theVoronoi and Delaunay tilings for the quadratic forms corresponding to theroot lattices E6 and E7.
There is a number of reasons why perfect Delaunay polytopes are fas-cinating objects for study. First, as mentioned before, they are ”perfect”inhomogeneous analogs of perfect lattices. This alone seems to be a naturalmotivation for a geometer of numbers. If the empty ellipsoid E circumscrib-ing a perfect Delaunay polytope D with the vertex set vertD is defined byan equation f(x) = 0, where f is an inhomogeneous quadratic form, thenall the coefficients of f are uniquely determined (up to a common scalingfactor) from the system {f(x) = 1 | x ∈ vertD}. Clearly, vertD is then the
2
set of all points on which f attains its minimum over Zd. An analogous prop-
erty for homogeneous quadratic forms is called perfection after Korkin andZolotareff (1873) (see Martinet (2003) and Conway and Sloane (1988) formodern treatment of perfect homogeneous forms). Naturally, in our contextf is called an inhomogeneous perfect form and E is referred to as a perfectellipsoid. The vertices of a perfect Delaunay polytope are analogs of theminimal vectors for a perfect form: the minimal possible number of verticesof a perfect Delaunay polytope is n(n+1)
2+ n, while the minimal number of
shortest vectors of a perfect forms is n(n+1)2
.Perfect Delaunay polytopes were first considered by Erdahl in 1975 in con-
nection with lattice polytopes arising from the quantum mechanics of manyelectrons. He showed (1975) that there are perfect Delaunay polytopes inone-dimensional lattices, and showed that the Gosset polytope G6 = 221
with 27 vertices was a perfect Delaunay polytope in the root lattice E6. Healso showed that there were no perfect Delaunay polytopes in dimensions 2,3, and 4. These results were extended by Erdahl (1992) by showing thatthe 7-dimensional Gosset polytope C7 = 331 with 56 vertices is perfect, andthat there are no perfect Delaunay polytopes in lattices with dimension lyingbetween one and six. Erdahl also proved that [0, 1], G6, and C7 are the onlyperfect Delaunay polytopes existing in root lattices. Deza, Grishukhin, andLaurent (1992,1995) found more examples of perfect Delaunay polytopes indimensions 15, 16, 22, and 23. The first construction of infinite sequencesof perfect Delaunay polytopes was first announced at the Conference ded-icated to the Seventieth Birthday of Sergei Ryshkov (Erdahl, 2001), andlater reported by Rybnikov (2001) and Erdahl and Rybnikov (2002). PerfectDelaunay polytopes have been classified up to dimension 7 – Dutour (2004)proved that G6 = 221 is the only Gosset polytope for d = 6. It is strongly sus-pected that the existing lists of seven and eight dimensional perfect Delaunaypolytopes are complete (see http://www.liga.ens.fr/ dutour/).
Perfect Delaunay polytopes are important in the study of strongly regulargraphs or, more generally, theory of association schemes. In fact, the Schlafligraph and the Gosset graph can be constructed as 1-skeletons of Gossetpolytopes G6 and C7, and that is precisely how the Gosset graph has beendiscovered. A maximal family of equiangular lines is a metrical concept,closely related to the combinatorial notion of strongly regular graph (seeDeza et al (1992), Deza and Laurent (1997) for details). All Delaunaypolytopes found by Deza et al have been derived from such families of lines.
Perfect Delaunay polytopes play an important role in the L-type reduc-tion theory of Voronoi and Delaunay for positive (homogeneous) quadraticforms. An L-type domain is the collection of all possible quadratic metricforms that give the same Delaunay tiling D for Z
d. L-type domains arerelatively open polyhedral cones, with boundary cells that are also L-typedomains – these conical cells fit together to tile the cone of metrical quadraticforms, which is described in the next section in detail. Simplicial Delaunaytilings label the full dimensional conic ”tiles”, and all other possible Delau-nay tilings label the lower dimensional cones. A significant role for perfectDelaunay polytopes is that they provide labels for a subclass of edge formsfor L-types. Edges-forms are forms lying on extreme rays of full-dimensionalL-type domains, which are labels by simplicial Delaunay tilings. Prior to thediscovery of the sequence {Gd} of G-topes by Erdahl and Rybnikov in 2001only finitely many edge forms were known. All of the infinite sequencesof perfect Delaunay polytopes that we report on correspond to infinite se-quences of edge forms for L-type domains. The significance of extreme L-types is much due to their relation to the structure of Delaunay and Voronoitilings for lattices. The Delaunay tilings that correspond to edge forms playan important role: The Delaunay tiling for an L-type domain is the inter-section of the Delaunay tilings for edge forms for the L-type. (Erdahl, 2000)There is a corresponding dual statement on the structure of Voronoi poly-topes: The Voronoi polytope Vϕ for a form ϕ contained in an L-type domainis a weighted Minkowski sum of linear transforms of Voronoi polytopes foreach of the edge forms. The latter dual result was first established by H.-F.Loesch in his 1990 doctoral dissertation, although it was first published byRyshkov (1998, 1999), who independently rediscovered Loesh’s theorem; thisdual result was given a shorter and simpler proof by Erdahl (2000).
Edge forms that are interior to the cone of metric forms are rare in lowdimensions. They first occur in dimension 4: D4 has an extreme L-type. Agood proportion, but not all, of the edge forms appearing in lower dimensionsrelate either directly or indirectly to perfect Delaunay polytopes. As shownby Dutour and Vallentin (2003) this situation does not persist in higherdimensions: there is an explosion of edge forms in six dimensions, and thatonly a tiny fraction of these are inherited from perfect Delaunay polytopes.
All of our sequences of perfect Delaunay polytopes determine correspond-ing sequences of lattices with similar combinatorial properties. Our construc-tions are first steps of a program to explore the geometry of higher dimen-sional lattices through infinite sequences of lattices. The infinite sequences
4
we have constructed are particularly interesting because of the role they playin the structure theory of Delaunay polytopes and Delaunay tilings, whichare described in the following section.
2 Homogeneous and Inhomogeneous
Forms on Lattices
The Voronoi and Delaunay tilings for point lattices are constructed using theEuclidean metric, but are most effectively studied by mapping the latticeonto Z
d, and replacing the Euclidean metric by an equivalent metrical form.For a d-dimensional point lattice Λ with a basis b1,b2, ...,bd this is done asfollows. If v is a lattice vector with coordinates z1, z2, ..., zd relative to thisbasis, then v can be written as v = Bz, where B = [b1,b2, ...,bd] is the basismatrix. The squared Euclidean length, is given by |v|2 = zTBTBz =ϕB(z),where z is the column vector given by [z1, z2, ..., zd]
T . This squared lengthcan equally well be interpreted as the squared length of the integer vectorz ∈Z
d relative to the metrical form ϕB. Therefore, the Voronoi and Delaunaytilings for Λ, constructed using the Euclidean metric, can be studied usingthe corresponding Voronoi and Delaunay tilings for Z
d constructed using themetrical form ϕB. Moreover, variation of the Voronoi and Delaunay tilingsfor Λ in response to variation of the lattice basis b1,b2, ...,bd can be studiedby varying the metrical form ϕ for the fixed lattice Z
d. In the discussionbelow we will keep the lattice fixed at Z
d, and vary the metrical form ϕ.With slight abuse of terminology we call any semidefinite form metric.
Definition: The squared length of a vector v with respect to a metric formϕ is called the norm of v relative to ϕ.
The inhomogeneous domain of a Delaunay polytope: The followingdiscussion of the geometry of P is a summary of some results contained in(Erdahl, 1992). Let P be the cone of quadratic functions on R
d defined by:
P = { f ∈ R[x1, . . . , xn] deg f = 2, ∀z ∈ Zd f(z) ≥ 0 }.
The condition ∀z ∈ Zd f(z) ≥ 0 requires the quadratic part of f to be
positive semi-definite, and requires any subset of Rd where f assumes negative
values to be free of Zd-elements. The real surface determined by the equation
5
f(x) = 0 might be empty set, it might be a subspace, or it might have theform
Ef = E0 ×K,
where E0 is an ellipsoid and K a complementary subspace. The last case isthe interesting one - depending on the dimension of K, Ef is either an empty(of lattice points) ellipsoid or an empty cylinder with ellipsoid base.
We denote by V (f) the set Ef ∩ Zd. In the case where the surface Ef
includes integer points and is an empty ellipsoid, V (f) = Ef ∩Zd is the vertex
set for the corresponding Delaunay polytope Df = conv V (f). Conversly,if D is a Delaunay polytope in Z
d, there is a circumscribing empty ellipsoidED determined by a function fD ∈ P. More precisely, since D is assumedDelaunay there is a metrical form ϕD, a center c and radius R, so thatfD(x) = ϕD(x − c) − R2 = 0 is the equation of a circumscribing emptyellipsoid ED. Since fD is non-negative on Z
d, it is an element of P.In the case where Ef is an empty cylinder, there will be an infinite number
of integer points lying on this surface. When this happens V (f) = Ef ∩ Zd
is the vertex set for a non-bounded Delaunay polyhedron Df = conv V (f),which is a cylinder with a base, which is also called a Delaunay polytope.Recall than a convex polyhedron is called a polytope when it is bounded.
Definition: LetD be a Delaunay polyhedron. Then, the (inhomogeneous)domain PD for D is:
PD = { f ∈ P Df = D }
Such domains are relatively open convex cones that partition int P (in fact,they partition a larger subset of P, which includes int P).
The elements f ∈ PD satisfy the homogeneous linear equations f(z) = 0, z ∈vert D = D ∩ Z
d, so the dimensions of domains vary depending upon therank of this system. When D is a single edge, the rank is one and PD is arelatively open facet of the partition with dimension dimP − 1 =
(d+22
)− 1.
When the rank is equal to(
d+22
)−1, which is the maximum possible in order
that PD not be empty, PD is an extreme ray of P.
Definition: Let V (p) be the set of integer points lying on the boundaryof a d-dimensional Delaunay polyhedron. A function p ∈ P is perfect if andonly if the equations p(z) = 0, z ∈ V (p) uniquely determine p up toscaling. In this case we will call the subset V (p) ⊂ Z
d perfect, and will callDp = conv V (p) perfect.
6
The elements of a 1-dimensional inhomogeneous domain are perfect, and theDelaunay polytopes that determine such domains are perfect. The perfectsubsets V (p) must be maximal among the subsets { V (f) ⊂ Z
d f ∈ P }.Perfect inhomogeneous forms are analogues of perfect homogeneous forms—
both achieve their minimum value on Zd sufficiently often that the represen-
tations of the minimum determine the form. In the homogeneous case theminimum is taken on the non-zero elements of Z
d; if the minimum value mϕ
is achieved on the set V (ϕ), then ϕ is uniquely determined by the equationsϕ(z) = mϕ, z ∈V (ϕ). Similarly, in the inhomogeneous case the minimumis taken on Z
d, and the minimum value is zero; if this minimum value isachieved on the set V (f) ⊂ Z
d, then f is uniquely determined (up to a scalefactor) by the equations f(z) = 0, z ∈V (f).
Theorem 1 If p ∈ P is perfect, then there is an ellipsoid E0, where 0 ≤dim(E0) ≤ d, and complementary subspace K so that Ep = E0 ×K, and sothat E0 and K satisfy the following arithmetic conditions:
E0 ∩ Zd are the vertices of a perfect Delaunay polytope in (aff E0) ∩ Z
d;
K ∩ Zd is a sublattice such that Z
d = ((aff E0) ∩ Zd) ⊕ (K ∩ Z
d).
In this case we have V (p) = Ep ∩ Zd = (E0 ∩ Z
d)⊕
(K ∩ Zd). Conversely,
any ellipsoid E0 and an affine complementary subspace K, satisfying thesearithmetic conditions, determine a surface E0 ×K for a perfect element p ofP and, therefore, determine a perfect element up to a scale factor.
By this theorem, if p is perfect, then Dp is either a perfect Delaunay poly-tope or, in the degenerate case when dimK > 0, a cylinder with a perfectDelaunay polytope as base.
A Zd-vector [u1, . . . , ud] is called primitive if GCD(u1, . . . , ud) = 1. As
an example, consider primitive vectors a,b ∈ Zd such that a · b =1. Then
E0 = {0,b} is an empty ellipsoid in the 1-dimensional lattice (aff E0) ∩ Zd,
and K = a⊥ ={x ∈ R
d | x · a = 0}
is a complementary subspace. Thesubset {0,b} = E0 ∩ Z
d is also the vertex set for a Delaunay polytope inaff(E0∩Z
d), and K is defined so that Zd = ((aff E0)∩Z
d))⊕
(K∩Zd). These
are the arithmetic conditions stated in the theorem, so that {0,b} × K isthe surface for a perfect element p of P, which, up to a scale factor, is givenby p(x) = (a · x)(a · x−1). The preimages of negative real values of p liebetween two hyperplanes with equations a · x =0 and a · x =1, a region whichis a degenerate Delaunay polyhedron.
7
With the exception of the one-dimensional perfect domains, all inhomo-geneous domains PD have proper faces that are inhomogeneous domains oflesser dimensions. If D is inscribed into another Z
d-polytope D′ so thatvertD′ ⊃ vertD, then PD′ ⊂ ∂PD.
In the following definition the Delaunay polyhedron D may be of anydimension.
Definition: Let D be a lattice Delaunay polyhedron. Then, the inhomo-geneous domain for D is defined as:
PD = { f ∈ P vertD = V (f) }
If D is a d-dimensional Delaunay simplex then dim PD =(
d+12
), but if D is
a perfect Delaunay polyhedron, then dim PD = 1.
Theorem 2 Let D be a d-dimensional Delaunay polyhedron. Then
PD = {∑
{p | V (p)⊇vert D}
ωpp ωp ∈ R>0 },
where the summation is over all perfect elements p such that vertD ⊆ V (p).
In general, not all relatively open faces on the boundary of an inhomo-geneous domain PD are inhomogeneous domains. However, in the specialcase where D is d-dimensional, all extreme rays are perfect inhomogeneousdomains and all relatively open faces are inhomogeneous domains (see Er-dahl 1992). In this case an arbitrary element f ∈ PD has the followingrepresentation:
f =∑
{p V (p)⊇vert D}
ωpp,
where ωp > 0. The summation is over the perfect elements p with theproperty that vertD ⊆ V (p).
These last two paragraphs, and our representation theorem for Delaunaypolytopes, show the important role played by perfect Delaunay polytopes inthe theory.
The homogeneous domain of a Delaunay tiling: Voronoi’s classifica-tion theory for lattices, his theory of lattice types (L-types), was formulatedusing metrical forms and the fixed lattice Z
d. In this theory two lattices are
8
considered to be the same type if their Delaunay tilings are affinely equiva-lent. Consider a positive definite quadratic form ϕ. Then a lattice polytopeD is Delaunay relative to ϕ if it can be circumscribed by so called emptyellipsoid E with equation of the form
ϕ(x − c) = R2,
where c ∈ Rd and R ∈ R>0; in addition, conv E must have no interior
Zd-elements, and vertD must be given by E∩Z
d. The collection of allsuch Delaunay polytopes fit together facet-to-facet to tile R
d, a tiling that isuniquely determined by ϕ. This is the Delaunay tiling Dϕ for Z
d relativeto the metrical form ϕ. If a second metrical form ϑ has Delaunay tilingDϑ, and if Dϑ is identicle to, or affinely equivalent to Dϕ, then ϕ and ϑ aremetrical forms of the same L-type.
The description we give below requires that certain degenerate metricalforms be admitted into the discussion, namely, those forms ϕ for which K =Kerϕ is a rational subspace of R
d. The Delaunay polyhedra for such aform are themselves degenerate–they are cylinders with axis K and Delaunaypolytopes as bases. These cylinders fit together to form the degenerateDelaunay tiling Dϕ. For example, if a ∈Z
d is primitive, ϕ(x) = (a · x)2 issuch a form—the kernel K is the solution set for ϕ(x) =0, and given by a⊥,which is rational. The Delaunay tiles are infinite slabs, each bounded by apair of hyperplanes a · x =k, a · x =k + 1, k ∈ Z. These fit together to tileR
d.Let Φ be the cone of metrical forms in d variables, namely, the cone
of positive definite quadratic forms and semidefinite quadratic forms withrational kernels. For each metrical form ϕ ∈ Φ there is a Delaunay tilingDϕ for Z
d.
Definition: If D is a Delaunay tiling for Zd, then the following cone of
positive definite quadratic forms
ΦD ={ϕ ∈ Φd
Dϕ = D}
is called an L-type domain.
For this definition the Delaunay tilings can be the usual ones, where the tilesare Delaunay polytopes – or they could be degenerate Delaunay tilings wherethe tiles are cylinders with a common axis K.
9
The relatively open faces of an L-type domain, are L-type domains. IfD is a trangulation, ΦD has full dimension
(d+12
); this is the generic case. If
D is not a triangulation, dim ΦD is less than(
d+12
), and ΦD is a boundary
cell of a full-dimensional L-type domain. In the case where dim ΦD = 1, theelements ϕ ∈ ΦD are called edge forms as they correspond to extreme raysof full-dimensional L-type domains.
Let D be a polytope in the Delaunay tiling D. Then, if πΦ is theprojection onto the quadratic part, ΦD ⊂ πΦ(PD). Since this containmentholds for all Delaunay tiles D ∈ D, there is the following description of ΦD
in terms of inhomogeneous domains:
ΦD =⋂
D∈D
πΦ(PD),
where the intersection is over all d-dimensional Delaunay polytopes in D.Since the containment ΦD ⊂ πΦ(PD) also holds for all Delaunay tilings D
that contain D, there is the following description of πΦ(PD) in terms ofhomogeneous domains:
πΦ(PD) =⊔
D∋D
ΦD,
where the disjoint union is over all Delaunay tilings for Zd that contain
D. This holds not only for full-dimensional cells of PD, but for cells of alldimensions. The last equality shows that πΦ(PD) is tiled by L-type domains.It also establishes the following
Theorem 3 If p ∈ P is perfect and, therefore, an edge form for an inhomo-geneous domain, then πΦ(p) is an edge form for an L-type domain.
This result can also be established in a more direct way by appealing to thedefinition of L-type domain: if D is a perfect Delaunay polytope, or perfectdegenerate Delaunay polyhedron, then πΦ(PD) is a one-dimensional L-typedomain. By definition, the elements of πΦ(PD) are then edge forms.
The converse of theorem does not hold - there are edge forms for L-typedomains that are not inherited from perfect elements in P. Evidence hasaccumulated recently that the growth of numbers of types of edge forms withdimension is very rapid starting in six dimensions (see Dutour and Vallentin,2003), but the the growth of perfect inhomogeneous forms is much less rapid- there is some hope that a complete classification can be made throughdimension nine, or even through ten.
10
3 Infinite Sequences of
Perfect Delaunay polytopes
Consider the following sets of vectors in Rd:
Dds,k = { [1s, 0d−s] −
s− 1
d− 2kj } ∪ { [1s+1, 0d−s−1] −
s
d− 2kj }
where s, k ∈ N and j = [1d] (1d means the entry 1 is repeated d times, andsimilarly for 1s and 0d−s). All permutations of entries are taken so that|Dd
s,k| =(
ds
)+(
ds+1
)=(
d+1s
). The following is the main theorem of this
paper.
Theorem 4 For d ≥ k(2s+ 1) + 1, where s ≥ 1, k ≥ 2, the polytope
P ds,k =
1
2conv{ Dd
s,k ∪−Dds,k }.
is a symmetric perfect Delaunay polytope for the affine lattice Λds,k = aff Cd
s,k;
the origin is the center of symmetry for P ds,k and does not belong to Λd
s,k. The
circumscribing empty ellipsoid can be defined by the equation ϕds,k(x) = R2,
Each pair of positive integers (s, k), for s ≥ 1, k ≥ 2, determines an infinitesequence of symmetric perfect Delaunay polytopes, one in each dimension,with the initial dimension given by k(2s+1)+1. For s = 1, k = 2 the infinitesequence is the one described in the opening commentary, i.e., Cd, d ≥ 7,where the initial term is the Gosset polytope 321 = C7 with 56 vertices.
The(
d+1s
)diagonal vectors Dd
s,k for P ds,k have the origin as a common mid-
point, forming a segment arrangement that generalizes the cross formed bythe diagonals of a cross-polytope. Moreover, these
(d+1
s
)diagonals are prim-
itive and belong to the same parity class for Λds,k, namely, they are equivalent
modulo 2Λds,k. More generally, primitive lattice vectors u,v in some lattice
Λ, with mid-points equivalent modulo Λ, are necessarily equivalent modulo2Λ and thus belong to the same parity class. And conversely, the mid-pointsof lattice vectors u,v ∈ Λ belonging to the same parity class are equivalentmodulo Λ. By analogy with the case of cross-polytopes, we call any such
11
arrangement of segments or vectors a cross. The convex hulls of such crossesoften appear as cells in Delaunay tilings – cross polytopes are examples, asare the more spectacular symmetric perfect Delaunay polytopes. There isa criterion due to Voronoi (1908) and Baranovskii (1991) that determineswhether these crosses are Delaunay: Let Λ be a lattice, let ϕ be a metricalform, and let C be the convex hull of a cross of primitive vectors belongingto the same parity class. Then C is Delaunay relative to ϕ if and only ifthe set of diagonal vectors forming the cross is the complete set of vectors ofminimal length, relative to ϕ, for their parity class. This is the criterionwe have used to establish the Delaunay property for the symmetric perfectDelaunay polytopes P d
s,k.The following result shows that asymmetric perfect Delaunay polytopes
can appear as sections of symmetric ones.
Theorem 5 For d ≥ 6 let u = [−12, 1d−1] ∈ Zd+1. Then
Gd = conv{v ∈ vertP d+11,2 | v · u =
1
2}
is an asymmetric perfect Delaunay polytope for the affine sublattice Λds,k =
aff vert Gd. The circumscribing empty ellipsoid can be defined as {x ∈aff Gd | ϕd+1
This is the infinite sequence of G-topes described in the introduction, withGossett polytope 221 = G6 as the initial term for d = 6.
The terms in this sequence have similar combinatorial properties. Forexample, the lattice vectors running between vertices all lie on the boundary,in all cases. These lattice vectors are either edges of simplicial facets, ordiagonals of cross polytope facets–there are two types of facets, simplexes andcross polytopes. The 6-dimensional Gossett polytope has 27 five-dimensionalcross-polytopal facets, but for the rest the number is twice the dimension,2d. G6 can be found as a section of G7, but G8 and G9 do not have sectionsarithmetically equivalent to G6.
From this theorem we might expect that all asymmetric perfect Delaunaypolytopes are obtained from symmetric ones by sectioning, and at our currentstate of knowledge this appears to be the case. This would be a fortunateturn of events, since the growth of classes of symmeteric perfect Delaunay
12
P dimP | vertP | Symmetry
P dκ,s d 2
((ds
)+(
ds+1
))= 2(
d+1s+1
)centrally-symmetric
Υd−1 d− 1 d(d+1)2
− 1 asymmetric
Table 1: Properties of constructed perfect Delaunay polytopes
polytopes with dimension is slower than for all other geometric phenomenaassociated with point lattices that we know about.
We summarize properties of the constructed polytopes in the followingtable (in this notation groups of entries separated by semicolumns can onlybe permuted between themselves).
The following table gives coordinates of the vertices of G-topes, discoveredin 2001 by Erdahl and Rybnikov.
Polytope P 74,1 is affinely equivalent to Gosset’s 321 = G7. Polytope Υ6 is
affinely equivalent to Gosset’s 221 = G6.
4 Delaunay Property Part of Main Theorem
We will use the following notation: φ1 =(∑d
i=1 xi
)2
, φ2(x) =∣∣∣x − j
∑di=1 xi
d
∣∣∣2
;
φ2(x) is the squared Euclidean distance from x to the line lin j. The followingtheorem proves the Delaunay property of polytopes P d
s,k asserted in Theorem4.
Theorem 6 Let s ≥ 1, k ≥ 2, and d ≥ k(2s+1)+1. Let l0 = [(−1)k/2, 1d−k/2],Λ = < e1, . . . , ed,
j
d−k>
Z, Λ0 = {λ ∈ Λ : λ · l0 ≡ 1( (mod 2))}. Then there is
a positive definite quadratic form of the type
φ(x) = αφ1(x) + βφ2(x), (1)
were α, β > 0, such that the polytope P ds,k is a Delaunay polytope in the affine
lattice Λ0 with respect to φ.
13
Here n = d− k and e1, . . . , ed stand for the canonical basis of Rd.
Lemma 4.1 Suppose φ(x) = αφ1(x) + βφ2(x) where α, β > 0. Then allpoints λ ∈ Λ0 which are closest to 0 with respect to φ, ie.,
φ(λ) = min{φ(u) : u ∈ Λ0}
are, up to permutations of components, of the type [1l, 0d−|l|] + a j
n, where
−d2≤ l < d
2, a ∈ Z. Here 1l for a negative l means l times −1. This
representation is unique.
Proof. Suppose λ ∈ Λ0 is closest to 0 with respect to φ in Λ0. Let λ =a1e1 + · · · + aded + a j
n, a1, . . . , ad, a ∈ Z, m = a1 + · · ·+ ad. We have
φ2(λ) = φ2
(d∑
i=1
aiei
)=
∣∣∣∣∣
d∑
i=1
aiei − jm
d
∣∣∣∣∣
2
=
d∑
i=1
a2i −
m2
d. (2)
The numbers ai are of two consecutive integer values. Otherwise therewould be ai and aj such that ai − aj ≥ 2. Consider the vector λ′ = a1e1 +· · ·+(ai − 1)ei + · · ·+(aj +1)ej + · · ·+ aded + a j
n. We have φ2(λ
′)−φ2(λ) =(ai − 1)2 + (aj + 1)2 − a2
i − a2j = 2(aj − ai) + 2 ≤ −2 and j · λ′ = j · λ. Since
λ′ ∈ Λ0 and φ(λ′) < φ(λ), it follows that the vector λ is not closest to 0which is a contradiction.
Now let b be the smallest of the values of numbers ai. Subtract b(e1 +· · ·+ ed) from the first part and add an equal value of bk j
nto the second part
of the existing representation of λ. After a permutation of components, thevector λ is equal to [1l, 0d−l] + (a + bk) j
nwhere 0 ≤ l < d. If l ≥ d
2, again
subtract [1d] from the first summand and add j to the second summand toget the required representation.
To prove uniqueness, note that the components λi of the vector [1l, 0d−|l|]+a j
nare of at most two values. In vector [1l, 0d−|l|], either 1s fill the positions
of the bigger λi, or −1s fill the positions of the smaller λi. Since −d2≤ l < d
2,
the choice is unique. 2
Lemma 4.2 All vectors in the affine lattice Λ0 which are closest to 0 withrespect to a form φ = αφ1(x) + βφ2(x), α, β > 0, belong to the set {λ ∈Λ0 : |λ · j| ≤ d
n}. If λ is closest to 0 with respect to φ and |λ · j| = d
n, then
λ ∈ {± j
n}.
14
Proof. By multiplying both α and β by the same positive number, we canassume that the minimal value of φ on Λ0 is 1. Since j
n∈ Λ0, φ( j
n) = α( d
n)2 ≥
1. Let λ ∈ Rd be a point with φ(λ) = 1. Represent λ = γ
nj + u where γ ∈ R,
u · j = 0. We have φ(λ) = αγ2d2
n2 + β|u|2 = 1, therefore αγ2d2
n2 ≤ 1. Sinceα( d
n)2 ≥ 1, we have proven that |γ| ≤ 1, so |λ · j| = |γ| d
n≤ d
n.
If the latter inequality holds strictly, then |γ| = 1 and φ(λ) = α d2
n2 +
β|u|2 = 1. Since α( dn)2 ≥ 1, we necessarily have β = 0 so λ = ± j
n.
Proof of Theorem 6:
We define a collection of points in Λ0 which contains, up to sign andpermutation of components, all vectors of the affine lattice Λ0 which havethe minimal distance to 0 with respect to any quadratic form φ of the type(1). Then we pick the form φ so that the vertices of P d
k,s are minimal vectorsand other points of M are not. Below is an implementation of this program.
(A) Consider the set
M =
{λ = [1l, 0d−|l|] + a
j
n∈ Λ0 : 0 ≤ λ · j <
d
n,−
d
2≤ l <
d
2
}∪ {
j
n}. (3)
By the two previous lemmas, for every minimal vector λ ∈ Λ0 of the quadraticform φ, either λ or −λ, after permutation the components if necessary, be-longs to this set.
For λ = [1l, 0d−l] + a j
n, we have
λ·j = l+ad
n, φ1(λ) =
(l +
ad
n
)2
, φ2(λ) = |l|−l2
d, l0·λ ≡ a+l (mod 2). (4)
From the calculations above, we get
M =
{[1l, 0d−|l|] + a
j
n: l + a ≡ 1(2), 0 ≤ lk + ad < d,−
d
2≤ l <
d
2
}∪ {
j
n}.
(5)We define a mapping from R
d to R2 by φ1,2(x) = (φ1(x), φ2(x)). We will
call the image of M the diagram. Lines parallel to φ1-axis in R2 will be called
horizontal.
(B) For λ1, λ2 ∈M , points φ1,2(λ1), φ1,2(λ2) belong to the same horizontalline if and only if λ1 = ±λ2. If λ and −λ both belong to M , then λ · j = 0.
15
To prove that, take λ = [1l, 0d−|l|] + a j
n∈M . If l 6= 0, then the condition
0 ≤ lk + ad < d uniquely defines a from a given value of l, and if l = 0, thena = 1. Therefore l uniquely defines a.
The function l → |l| − l2
dis even and increasing on [0, d
2] so two different
points of the diagram may belong to the same horizontal line if and onlyif their preimages are λ1 = [1l, 0d−|l|] + a1
j
nand λ2 = [1−l, 0d−|l|] + a2
j
nfor
some l,a1,a2. If l 6= 0, then 0 ≤ lk + a1d < d, 0 ≤ −lk + a2d < d. Addingthese inequalities, we get 0 ≤ (a1 + a2)d < 2d, so a1 + a2 ∈ {0, 1}. Ifa1 + a2 = 0, then λ1 = −λ2 so φ1,2(λ1) = φ1,2(λ2). If a1 + a2 = 1, then thenumbers l+a1 and −l+a2 have different parity which contradicts conditionsl + a1 ≡ −l + a2 ≡ 1(2). If l = 0, then a1 = a2 = 1. This proves our claim.
(C) Our method of constructing perfect Delaunay polytopes can be sum-marised as follows. We note that each line αx1 + βx2 = 1, where α, β > 0,which supports the edge of the convex hull of the diagram, gives rise to aquadratic form φ(x) = αφ1(x) + βφ2(x) such that the ellipsoid φ(x) = 1circumscribes the points of the affine lattice Λ0 which fall into the endpointsof the edge and has no lattice points inside.
(D) First consider case d = 7, k = 4, s = 1. The diagram for these valuesof parameters is shown in figure 4. We see that the line 3
7x1 + 2
3x2 = 1 passes
through points φ1,2(v74,1) = φ1,2([1, 0
6]) and φ1,2(v74,2) = φ1,2([−12, 05] + j
3),
and all other points of the diagram are contained in the open half-plane37x1 + 2
3x2 > 1. This means that polytope P 7
4,1 is a Delaunay polytope withrespect to quadratic form 3
7φ1(x) + 2
3φ2(x) = 2
3x · x + 1
3(j · x)2.
(E) Now suppose that d ≥ 8, 4 ≤ k ≤ d/2, k ≡ 0(2) and 1 ≤ s ≤ dk− 1.
Suppose λ = [1l, 0d−l] + a j
n∈ M and 0 ≤ φ2(λ) ≤ d
k− d
k2 (or, equivalently,|l| ≤ d
k). If |l| < d
k, then l ≥ 0 and
λ = [1l, 0d−l] − (l − 1)j
n. (6)
If |l| = dk
(this implies that dk
is an integer number), then
±λ = [1dk , 0d− d
k ] − (d
k− 1)
j
n. (7)
To prove this, first check that these points belong to set M , and then usestatement in paragraph (B) that there is at most two points λ = [1l, 0d−|l|] +
16
a j
n∈ M with a given value of |l|, and there are two if and only if lk+ad = 0,
in which case the points are ±λ.We’ll use notation vd
k,s = [1l, 0d−l] − (l − 1) j
nfor 0 ≤ s ≤ d
k. We have
φ1(vdk,s) =
(s+ (1 − s)
d
n
)2
, φ2(vdk,s) = s−
s2
d. (8)
All points φ1,2(vdk,s) therefore belong to the curve
t→
((t+ (1 − t)
d
n
)2
, t−t2
d
)(9)
which touches the vertical axis in the point (0, dk− d
k2 ) when t = dk. The curve
is drawn in dashed line in figure 4. The portion of the curve for 0 ≤ t ≤ dk
isthe graph of a convex function.
Therefore, for each 0 ≤ s ≤ dk− 1 we can find a line with equation
αx1 + βx2 = 1 which passes through points φ1,2(vdk,s), φ1,2(v
dk,s+1), supports
the convex hull of the diagram and does not contain points φ1,2(λ) for λ ∈M ,λ 6= ±vd
k,s,±vdk,s+1. Quadratic form φ(x) = αφ1(x)+βφ2(x) defines an empty
ellipsoid with center 0 which contains vertices of P dk,s on its boundary and
does not contain any other lattice points.We have proven that P d
k,s is a Delaunay polytope in affine lattice Λ0 with
respect to a unique quadratic form φ = φdk,s for d ≥ 7. Explicit formula (4)
for φdk,s is established by a trivial calculation.
2
Example of the diagram for d = 19, k = 6 is shown in figure 4 (right-handimage). Note that not all points belong to the curve (9).
5 Perfection Property Part of Main Theorem
Theorem 7 Let d, k and s be as in Theorem 4. Then, there can be atmost one positive definite quadratic form φ whose ellipsoid φ(x − c) = 1circumscribes the polytope P d
k,s for some c ∈ Rd.
Proof. As before, n = d − k. Since for any given positive definite quadraticform the center of the its ellipsoid which circumscribes P d
k,s is defined uniquely,
17
[ -1, 0 ] + j/3
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
1 2 3 4 5 6 7
2 5
[ -1, 0 ] + 2j/33 4
[ 1, 0 ]6
j/30
0.5
1
1.5
2
1 2 3 4 5
j/4
[ 1, 0 ]7
[ 1, 0 ] - j/42 6
[ -1, 0 ] + 2j/43 5
Figure 1: Diagrams for d = 7; 8, { = 4 onvex hull of the diagram and does not ontain points m(�) for � 2 M ,� 6= �vd{;s;�vd{;s+1. Quadrati form �(x) = ��1(x) + ��2(x) de�nes anempty ellipsoid with enter 0 whi h ontains verti es of P d{;s on its boundaryand does not ontain any other latti e points.We have proven that P d{;s is a Delaunay polytope in aÆne latti e �0 withrespe t to quadrati form � for d � 7. Expli it formula (7) for � an beestablished by a trivial al ulation. 2.Example of the diagram for d = 19, � = 6 is shown in �gure 2 (right-handimage). Note that not all points belong to the urve (17).4 The perfe tion propertyTheorem 4 Let d, { and s be as spe i�ed in theorem 1. Then, there an beat most one positive de�nite quadrati form � whose ellipsoid �(x � ) = 1 ir ums ribes the polytope P d{;s for some 2 Rd .Proof. For shortness, k will stand for d� �.110
0.5
1
1.5
2
1 2 3 4
j/5
[ 1, 0 ]8
[ 1, 0 ] - j/52 7
[ -1, 0 ] + 2j/43 6
[ -1, 0 ] + 3j/44 5
0
1
2
3
4
5
0.5 1 1.5 2 2.5
[ 1, 0 ] - j/132 17
[ 1, 0 ]18
Figure 2: Diagrams for d = 9, { = 4 and d = 19, { = 6
1218
and since the polytope P dk,s has 0 as the center of symmetry, 0 is the cen-
ter of the circumscribing ellipsoid. Therefore, if φ and ψ are two positivedefinite quadratic forms which circumscribe P d
k,s by ellipsoids of radius 1,then the ellipsoids are given by equations φ(x) = 1, ψ(x) = 1. Hence(φ − ψ)|V d
k,s∪V d
k,s+1= 0. We consider an arbitrary quadratic form f such
that f |V dk,s
∪V dk,s+1
= 0 and prove that f = 0.
We will use the following symmetrization technique. Suppose that G isa subgroup of the group Sd of permutations on d elements Id = {1, . . . , d}.The symmetrization F of the form f by G is defined as
F (x1, . . . , xd) =∑
σ∈G
f(xσ1, . . . , xσd). (10)
Since polytope P dk,s is invariant under transformations of R
d defined by per-mutations of coordinates, all components in the above sum are 0 on the setof vertices of P d
k,s. Therefore F |V dk,s
∪V dk,s+1
= 0.
Firstly we prove that if a form f satisfies the condition f |V dk,s
∪V dk,s+1
= 0,
then the sum of the diagonal elements of f , and the sum of off-diagonalelements are 0. We symmetrize f by the group Sd and get a form F withdiagonal coefficients proportional to the sum of diagonal coefficients of f , andnon-diagonal coefficients proportional to the sum of non-diagonal coefficientsof f . Therefore F can be written as F (x) = αφ1(x) + βφ2(x). Supposethat α and β are not both equal to 0. Since F |V d
k,s∪V d
k,s+1= 0, the line αx1 +
βx2 = 0 passes through the points φ1,2(Vdk,s) and φ1,2(V
dk,s+1), where φ1,2(x) =
(φ1(x), φ2(x)). This is impossible because the line that passes through thesepoints is uniquely defined and does not contain 0. This contradiction provesour claim.
Next we prove that all diagonal elements of the form f are equal to 0.Suppose that one of them is nonzero. Without a limitation of generality wemay assume that t = f11 6= 0. Let F be the symmetrization of f by thegroup G = St(1) of permutations which leave 1 fixed. The matrix of F is
The determinant of the system of these 4 equations in variables α, β, δ andt is equal to
2
n(d− 1)(s− d+ 1)(s− d)(d− 2 − n) (15)
and it is not equal to 0 for the specified values of d, n and s. Hence t = 0.Next we prove that all off-diagonal elements of f are equal to 0. Without
a limitation of generality we can assume that f12 6= 0. Let F be the sym-metrization of f by the group of permutations which map the set {1, 2} ontoitself. The matrix of F is
where α 6= 0. We consider the following vectors: v1 = [1s+1, 0d−s−1] − s j
n∈
V dk,s and v2 = [0d−s−1, 1s+1]−s j
n∈ V d
k,s+1. The equations F (v1) = 0, F (v2) = 0yield
4(s−1)β+2α+(s−1)(s−2)δ−2s
n(2α+2(s−1+d−2)β+(s−1)(d−3)δ)+
(s− 1)2(2α+ 4(d− 2)β + (d− 2)(d− 3)δ)
n2= 0, (17)
(s+1)sδ−2(s+ 1)s(2β + (d− 3)δ)
n+s2(2α+ 4(d− 2)β + (d− 2)(d− 3)δ)
n2= 0.
(18)We also know that the sum of off-diagonal elements of the matrix of F isequal to 0:
2α + 4(d− 2)β + (d− 2)(d− 3)δ = 0 (19)
so, with some simplifications, the previous two equations can be rewritten as
4(s−1)β+2α+(s−1)(s−2)δ−2s
n(2α+2(s+d−3)β+(s−1)(d−3)δ) = 0,
δ −2(2β + (d− 3)δ)
n= 0. (20)
The systems of equations (19) and (20) in variables α, β and δ has de-terminant 8(d− 2 − n)(−d + s+ 1) which is not equal to 0 for the specifiedparameters d, n and s which proves that the system has only a 0 solution.In particular, α = 0. We have proven that all off-diagonal elements of thematrix of form f are equal to 0.
6 Proof of Theorem 5
Assume thatD ⊂ Rd+1, with 0 /∈ affD. Consider the lattice Λ =< vertD >Z.
Let v ∈ vertD be any vertex. Consider polytope D′ = v − D. We havevertD′ ⊂ Λ. One can see that there is a positive definite quadratic form φwhose ellipsoid circumscribes vertD ∩ vertD′ and does not have any otherlattice points inside or on the boundary. Note that since D satisfies theperfection property, φ is defined up to a parameter and a scale factor.
21
We can now “stretch” the ellipsoid until it touches some other latticepoint(s) X. If the vertices of D cannot be embedded into the set of verticesof a centrally symmetric perfect Delaunay polytope, then the ellipsoid willindeed meet points in lattice Λ. Proving that means proving that the cylinderwhich circumscribes both polytopes D and D′ contains other points of Λ. Ifthat is not true, project Λ onto linD′ along t. The image Λ1 is either alattice, in which case the ellipsoid which circumscribes D′ will circumscribea centrally symmetric perfect Delaunay polytope in Λ1, or the direct sum ofa lattice and a linear subspace, in which case the set of vertices of D′ hasdimension less than d-a contradiction.
The resulting ellipsoid circumscribes the polytope D′′ = conv(vertD ∪vertD′∪X) and has no other lattice points inside or on the boundary. HenceD′′ satisfies the Delaunay property. It is easy to see that it also satisfies theperfectness property.
7 Summary
This paper has presented two equivalent definitions of perfect Delaunay poly-tope, one related to the study of edge forms in L-type domains, the other toa generalization of perfect forms to inhomogeneous case. Edge forms classi-fication is one of the cornerstone problems in geometry of positive quadraticforms; as Voronoi noticed in 1908 , the study of minima of inhomogeneousforms is strongly related to the study of perfect homogeneous quadraticforms.
We observed that each centrally perfect Delaunay polytope can be embed-ded into a centrally symmetric one. Therefore centrally symmetric perfectDelaunay polytopes play a special role. We conjectured that the growth ofthe number of perfect Delaunay polytopes in dimension d up to affine equiv-alence is not prohibitive; M. Dutour (2004) discovered that there is only oneperfect Delaunay polytope in dimension 6. We have given a new constructionof infinite series of perfect Delaunay polytopes in dimensions d ≥ 6, basedon the Gosset polytope 321.
Further study of perfect Delaunay polytopes can have two directions: oneto estimate the growth of number of types of centrally symmetric Delaunaysupertopes, the other to find higher-dimensional analogues of the 15, 16 and22, 23-dimensional examples.
22
References
[1] E. P. Baranovskii, Partition of Euclidean spaces into L-polytopes ofcertain perfect lattices. (Russian) Discrete geometry and topology (Rus-sian). Trudy Mat. Inst. Steklov. 196 (1991), 27–46. Translated in Proc.Steklov Inst. Math. 196, (1992), no. 4, 29–51.
[2] Conway, J. H.; Sloane, N. J. A. Low-dimensional lattices. III. Perfectforms. Proc. Roy. Soc. London Ser. A 418 (1988), no. 1854, 43–80.
[3] H. S. M. Coxeter, Discrete Groups Generated by Reflections. Annals ofMath. 35 (1934), 588-621. Repr. in Kaleidoscopes: Selected Writings ofH. S. M. Coxeter, F. A. Sherk et al., eds., Wiley, New York, 1995.
[4] M. Deza,V. P. Grishukhin, Hypermetric graphs. Quart. J. Math. OxfordSer. (2) 44 (1993), no. 176, 399–433.
[5] M. Deza, V. P. Grishukhin, V. Delaunay polytopes of cut lattices. LinearAlgebra Appl. 226/228 (1995), 667–685.
[6] M. Deza, V. P. Grishukhin, Cut lattices and equiangular lines. Discretemetric spaces (Bielefeld, 1994). European J. Combin. 17 (1996), no. 2-3,143–156.
[7] M. Deza, V. P. Grishukhin, Hypermetric two-distance spaces. Recentadvances in interdisciplinary mathematics (Portland, ME, 1997). J.Combin. Inform. System Sci. 25 (2000), no. 1-4, 89–132.
[8] M. Deza, V. P. Grishukhin, M. Laurent, Extreme hypermetrics and L-polytopes. Sets, graphs and numbers (Budapest, 1991), 157–209, Colloq.Math. Soc. Janos Bolyai, 60, North-Holland, Amsterdam, 1992.
[9] M. Deza, V. P. Grishukhin, M. Laurent, Hypermetrics in geometryof numbers. Combinatorial optimization (New Brunswick, NJ, 1992–1993), 1–109, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 20,Amer. Math. Soc., Providence, RI, 1995.
[10] M. Deza, M. Laurent, Geometry of cuts and metrics. Algorithms andCombinatorics, 15. Springer-Verlag, Berlin, (1997).
23
[11] M. Dutour, F. Vallentin, Some six-dimensional rigid forms. Preprintmath.MG/0401191 on http://ArXiv.org . To appear in the proceedingsof the 2003 Voronoi conference on analytic number theory and spatialtessellations.
[12] M. Dutour, The six-dimensional Delaunay polytopes. European Journalof Combinatorics, Volume 25, Issue 4 , May 2004, Pages 535-548
[13] R. Erdahl, A convex set of second-order inhomogeneous polynomials withapplications to quantum mechanical many body theory, MathematicalPreprint #1975-40, Queen’s University, Kingston Ontario, (1975).
[14] R. Erdahl, A cone of inhomogeneous second-order polynomials, DiscreteComput. Geom. 8 (1992), no. 4, 387–416.
[15] R. M. Erdahl, A structure theorem for Voronoi polytopes of lattices,A talk at a sectional meeting of the AMS, Toronto, September 22-24,(2000).
[16] R. M. Erdahl, On the tame facet of the perfect domain E∗6 , Plenary talk
at the Seventieth Birthday Celebrations for Sergei Ryshkov, SteklovInstitute, Moscow, January 24-27, (2001).
[17] R. M. Erdahl, K. Rybnikov, Supertopes, (2002)http://faculty.uml.edu/krybnikov/PDF/Supertopes.pdf and asmath.NT/0501245 on arxiv.org.
[18] A. Korkine, G. Zolotareff, Sur les formes quadratiques, Math. Ann. 6(1873), 366-389.
[19] H.-F. Loesch. Zur Reduktionstheorie von Delone-Voronoi fur matroidis-che quadratische Formen. Dissertation. Univ. Bochum, 1990.
[20] J. Martinet, Perfect lattices in Euclidean spaces. Fundamental Principlesof Mathematical Sciences, 327, Springer-Verlag, Berlin, (2003).
[21] K. Rybnikov, REU 2001 Report: Geometry of Numbers, (2001)http://www.mathlab.cornell.edu/ upsilon/REU2001.pdf
[22] S. S. Ryshkov, Direct geometric description of n-dimensional Voronoiparallelohedra of the second type, (Russian) Uspekhi Mat. Nauk 54
[23] S. S. Ryshkov, On the structure of a primitive parallelohedron andVoronoi’s last problem, (Russian) Uspekhi Mat. Nauk 53 (1998), no.2 (320), 161-162; translation in Russian Math. Surveys 53 (1998), no.2, 403-405.
[24] G. F. Voronoi, Nouvelles applications des parameters continus a latheorie des formes quadratiques, Deuxieme memoire, J. Reine Angew.Math., 134 (1908), 198-287, 136 (1909), 67-178.
[25] G. F. Voronoi, Sobranie socineniiv treh tomah, [Collected works in threevolumes], vol. 2, (in Russian), Kiev (1952), Introduction and notes byB. N. Delaunay.
