Later this month, Hans Parshall will participate in a summer school on “Sphere Packings and Optimal Configurations.” In preparation for this event, Hans was assigned the task of writing lecture notes that summarize the main results of the following paper:
P. Delsarte, J. M. Goethals, J. J. Seidel,
Geometriae Dedicata 6 (1977) 363–388.
I found Hans’ notes to be particularly helpful, so I’m posting them here with his permission. I’ve lightly edited his notes for formatting and hyperlinks.
Without further ado:
— Spherical codes —
A spherical code is a finite set of unit vectors in Euclidean space . Fundamental problems in discrete geometry and communication theory are concerned with the interplay between the size and the set of inner products For instance, the kissing number is the largest number of unit spheres in that touch without overlapping. Equivalently, is the size of the largest spherical code with .
More generally, we call a spherical code an -code when . Delsarte, Goethals and Seidel obtain upper bounds for the size of an arbitrary -code in terms of polynomials that interact nicely with the set . To see the utility of such a strategy, consider their absolute bound:
Theorem 1 (Theorem 4.8 in [DGS77]). If is an -code with ,
Proof: Observe that the polynomial vanishes on and has degree . For each , define the polynomial function by . For each , notice , and so each is linearly independent. Moreover, each resides in the vector space of real-valued functions on that can be represented by a polynomial of degree at most . It follows that is at most the dimension of this vector space, which is given by ; see Section 2.2 here.
Theorem 1 is clearly sharp for by considering the vertices of a regular simplex. However, already for , equality in (1) is only known to occur for , where the corresponding spherical code is constructed from a set of equiangular lines in . In what follows, we derive improved upper bounds on for arbitrary -codes that depend on more detailed information about .
— Gegenbauer polynomials —
The linear programming bound for spherical codes in is stated in terms of Gegenbauer polynomials . These can be described recursively by , , and, for ,
Note the dependence on the ambient dimension . This recursion has the benefit of being concrete and the drawback of being completely unmotivated. Before we see how these polynomials are useful, we give some motivation as to why they naturally appear in the context of spherical codes. The rest of this section is based loosely on the excellent lecture notes by Vallentin.
We want an upper bound on , where is an arbitrary -code. Equivalently, we want an upper bound on the clique number of the infinite graph with vertices and an edge between exactly when . One such influential bound for finite graphs is given by the Lovasz theta number, which is defined as a semidefinite program. This was strengthened by Schrijver and subsequently extended to infinite graphs by Bachoc, Nebe, Oliveira and Vallentin. To state a specialized version of their bound, let denote the set of continuous functions , which we call kernels. A kernel is called positive, and we write , if for every set of points , the matrix is positive semidefinite. We have the following bound.
Proposition 2. If is an -code, then
Proof: Let be feasible for (3). Since , we have
Rearranging yields as desired.
In Proposition 2, we may without loss of generality restrict our attention to -invariant kernels , where for all . In particular, if is -invariant, then for some continuous function . The Peter–Weyl theorem provides the decomposition , where is the vector space of restrictions of homogenous degree- harmonic polynomials to . Hence, we may express -invariant kernels in terms of the orthogonal projections . Set and let be a real orthonormal basis for . A kernel representation for is given by
The upshot is that every positive -invariant kernel can be expressed as with , with each kernel defined by the addition formula . Moreover, each kernel can be expressed as for a polynomial of degree , and the orthogonality of the spaces leads to the orthogonality relation
This determines the polynomials recursively, and rescaling each appropriately yields the Gegenbauer polynomials described by (2). The choice of scaling is irrelevant for our applications.
— The linear programming bound for spherical codes —
While we could derive the linear programming bound from Proposition 2, we instead give a concrete proof in the spirit of Delsarte, Goethals, and Seidel.
Theorem 3 (Theorem 4.3 in [DGS77]). If is an -code, then
Equality in (4) occurs if and only if for all and
Proof: Let be feasible for (4). The key idea is to consider bounding from above and below. To begin, expand
For , is a positive kernel, and so . For an upper bound, the constraint for all provides
All together, we have with equality exactly when claimed.
Observe that the only property of the Gegenbauer polynomials that we used for Theorem 3 was that, for each , for all finite . This is weaker than each being a positive kernel, and Pfender obtained slight improvements based on this observation.
The case of equality in (4) motivates the following definition. A -design is a spherical code with for all . Equivalently, for every polynomial of degree at most ,
see Section 9.6 here. These highly uniform sets are good candidates for -codes of maximal cardinality. Indeed, if is a -design with and is a polynomial that is feasible for (4) that vanishes on , then every -code has size at most .
This strategy gives the exact values for the kissing numbers and . For , the 240 shortest vectors of the lattice have inner products . Hence, is a -code and . Delsarte, Goethals and Seidel showed that is a -design, and later Levenshtein and Odlyzko and Sloane independently showed that
satisfies with and . Applying Theorem 3 proves . A similar strategy with the Leech lattice yields .
Delsarte, Goethals and Seidel again use Gegenbauer polynomials to give a linear programming lower bound (Theorem 5.10 in [DGS77]) on the size of an arbitrary -design . In some sense, this lower bound is dual to Theorem 3 and the proof is similar. They give an upper bound on for spherical -designs with fixed and show that, in all cases, (Theorem 6.6 in [DGS77]).
The linear programming method has been generalized beyond Theorem 3. Musin developed a nonconvex extension to prove . Cohn and Elkies extended the linear programming method to noncompact settings, leading to the resolution of the sphere packing problems in by Viazovska and by Cohn, Kumar, Miller, Radchenko, and Viazovska. De Laat and Vallentin identified a general semidefinite programming hierarchy for problems in discrete geometry, the lowest level of which is the linear programming method. For more on the development of these methods, the reader is encouraged to consult the notes of Vallentin and Cohn.