数理解析研究所講究録
第 1889 巻 2014 年 1-6

1

Price of SDP relaxations for spherical codes*
Alexey Glazyrin \dagger and Oleg R. Musin\ddagger
October 7, 2013

1 IntroductionLet
be a subset of points on the sphere in . We will call a spherical-code if the angular distance between any two points of is not greater than . By
we denote the maximum cardinality of a -code in. For $\varphi=\pi/3$ the problem of finding $A(d, \pi/3)$
is the kissing number problem. For $d=3$ , the problem of finding , the maximal such that
$A(3, \varphi)\geq n$ for given, is the Tammes problem [29] (see [9, Section 1.6: Problem 6]).
The linear programming and semi-definite programming approach is one of the most important
methods of analyzing codes. The method was discovered by Delsarte [12, 13] for the Hamming
space and then extended to the spherical case [14] and generalized by Kabatyansky and Levenshtein[16]. The key ingredient for Delsarte’s method in the spherical case is Schoenberg’s theorem [27](later generalized by Bochner [8]). Let
be the classical Gegenbauer polynomial of degree
Gegenbauer (ultraspherical) polynomials
are a special case of Jacobi polynomials$G_{k}^{(d)}(1)=1$
with
and normalization. They may be defined through a recurrence
relation:$C=\{x_{1}, \ldots, x_{M}\}\subset \mathbb{S}^{d-1}$$\mathbb{R}^{d}$

$C$

$C$

$\varphi$$\varphi$$A(d, \varphi)$$\mathbb{S}^{d-1}$$\varphi$$d_{n}$$\varphi$$n$$G_{k}^{(d)}(t)$$k.$$G_{k}^{(d)}(t)$$P_{k}^{(\alpha,\beta)}(t)$$\alpha=\beta=\frac{d-3}{2}$$G_{0}^{(d)}(t)=1, G_{1}^{(d)}(t)=t$;$G_{k}^{(d)}(t)= \frac{2k+d-4}{k+n-3}G_{k-1}^{(d)}(t)-\frac{k-1}{k+d-3}G_{k-2}^{(d)}(t)$.

Consider thematrixwhere the matrix elements are the values of
evaluated at $t_{ij}=(x_{i}, x_{j}),$ $1\leq i,j\leq M$ . Then the Schoenberg theorem states that
$M\cross$$(G_{k}^{(d)}(t_{ij}))_{1\leq i,j\leq M}$$G_{k}^{(d)}$$(G_{k}^{(n)}(t_{ij}))\succeq 0 (k=1,2, \ldots)$,(1)

i.e. this matrix is positive semidefinite (p.d.) for all $k=1,2,$. Moreover, for any polynomialof degree the matrix $F(t_{ij})$ is positive definite for any spherical code only if $F$ is a linear
combination of the first $k+1$ Gegenbauer polynomials with non-negative coefficients. In particular,$G_{1}^{(n)}(t)=t$, so Schoenberg’s theorem provides a far-reaching extension of the condition on theGram matrix of$\ldots$

$F$

$k$

$C$

$C.$

*This research is partially supported by the Russian Government under the Mega Project 11. $G34.31.0053$ , RFBR
grant 11-01-00735, DMS 1101688.
\dagger University of Texas at Brownsville.
University of Texas at Brownsville; Institute for Problems of Information Transmission, Moscow.
$\ddagger$

2
The Desarte method uses the relaxed Schoenberg conditions:$\sum_{i,j}G_{k}^{(n)}(t_{ij})\geq 0 (k=1,2, \ldots)$.

(2)

By means of this inequality it is not difficult to prove the following theorem:
Theorem 1.1 (Delsarte-Goethals-Seidel[14], Kabatyansky-Levenshtein[16]) For a spherical code
, let $f(t)$ be a real polynomial such that $f((x_{i}, x_{j}))\leq 0$ for all $i\neq j$
and $f(t)$ has non-negative coefficients in the Gegenbauer basis with a constant coefficient $f_{0}>0.$$C=\{x_{1,\ldots,M}x\}\subset \mathbb{S}^{d-1}$

Then $|C|\leq f(1)/f_{0}.$This theorem allows one to find kissing numbers in dimensions 8 and 24 [18, 26], the best
asymptotic bounds for kissing numbers [16] (slightly improved in [11]) and the general bound on$A(d, \varphi)[18,19]$ . Certain strengthening of these linear conditions gives new proofs for the kissing
and the best current bounds for some sphere, solution of the problem inbumber inpacking densities [10]. The Delsarte method also accounts for the best known asymptotic bounds
in some other spaces [21, 3, 7], thereby representing one of the key tools in extremal problems of
distance geometry. The Delsarte method has been recently extended to semidefinite programming
bounds that rely on a more detailed version of the positivity constraints and on the corresponding
p.d. functions on the space [28, 23, 24, 5, 6, 4].
$\mathbb{R}^{4}[25]$$\mathbb{R}^{3}[2,22]$

Multivariate positive definite functions: We consider the multivariate generalization of Schoenif for any finite
function $F(x, y)$ is p.d. on
berg conditions. Let be a point on
configuration of points $C=\{x_{1}, x_{2}, \ldots, x_{M}\}\subset S^{d-1}$ the following matrix$\mathbb{S}^{d-1}.$$q$$S^{d-1}$$A$$(F(t_{ij}, u_{i}, u_{j}))_{1\leq i,j\leq M}, t_{ij}=(x_{i}, x_{j}), u_{i}=(x_{i}, q)$,

is positive definite. An explicit characterization of such functions was found in [5], relying on
the Bochner theorem; these functions may be written as nonnegative linear combinations of thefollowing trivariate polynomials:$G_{k}^{(d,1)}(t, u, v)=((1-u^{2})(1-v^{2}))^{k/2}G_{k}^{(d)}( \frac{t-uv}{\sqrt{(1-u^{2})(1-v^{2})}})$.

The polynomials $G_{k}^{(d,1)}(t, u, v)$ are proportional to the elements of the zonal matrices that arise
under the action of the group $H=O(\mathbb{R}^{d-1})$ that stabilizes a point on
Extending this construction to the action of the stabilizer of $m\geq 1$ points, paper [23] constructed a Fourier basis for the space of p.d. functions of $2m+1$ variables. The corresponding
multivariate Gegenbauer polynomials have the form$\mathbb{S}^{d-1}.$$G_{k}^{(d,m)}(t, u, v)=((1-|u|^{2})(1-|v|^{2}))^{k/2}G_{k}^{(d-rn)}( \frac{t-(u,v)}{\sqrt{(1-|u|^{2})(1-|v|^{2})}})$,(3)

are real variables. These functions provide a suitable generalization
whereof the Schoenberg theorem to the case of restricted group actions on
is related to Gegenbauer’s proof of the ”addition formula”
The meaning of the functions[ , pp. 459-462]. Namely, given one reference point , we project thefor the polynomials
points $x,$ on the hyperplane orthogonal to the direction , scale the picture to put them on thesphere of dimension $d-1$ , and write out Delsarte’s conditions for the points on that sphere.
. This construction
similar procedure is performed for an arbitrary $m$ to yield the functions
method of the polynomials, put forward in [23], offers a visual perspective of positivity constraints
involved in the semidefinite progralmning (SDP) bounds on spherical codes.
$t,$ $u_{1}\ldots,$ $u_{m},$ $v_{1},$$v_{m}$$\ldots,$$\mathbb{S}^{d-1}.$$G_{k}^{(d,1)}$$G_{k}^{(d)}$

$y$

$1$

$q$

$q$

$A$

$G_{k}^{(d,m)}$3
2 SDP relaxations for spherical codes
Any spherical code
following conditions:$x_{1},$ $x_{2},$$T\succeq 0$;$\ldots,$$x_{M}$

rank $(T)\leq d$ ;in$\mathbb{S}^{d-1}$

can be represented by a Gram matrix$t_{ii}=1(1\leq i\leq M)$ ,$T$

that satisfies the$-1\leq t_{ij}\leq 1(1\leq i\neq j\leq M)$.

(4)

The rank condition in (4) is difficult to use for computational purposes since it is not linear or
semi-definite. Hence often it is replaced by the semi-defimite Schoenberg conditions (1) or linear
Delsarte conditions (2).
These relaxations enable one to perform explicit calculations of the bounds on codes (after anappropriate symmetrization [4] . In the simplest form (2) the positivity conditions even enable one
to compute universal bounds on codes and designs [19, 20]. At the same time, the question of
the gap between the exact description of codes (4) and the relaxed conditions (1) $-(2)$ is altogether
unexplored.
The convex set of symmetric p.d. matrices with unit main diagonal (the elliptope) has been
extensively studied in combinatorics and distance geometry [17, 15]. Spherical configurations form
a subset of the elliptope isolated by the rank condition. We study properties of the subsets of theelliptope obtained through a sequence of relaxations from the rank condition in (4) to the positivity
constraints and Delsarte conditions, and the impact of the relaxations on the bounds on codes.
It appears that for $d=2$ , the Schoenberg conditions (1) are fulfilled if and only if the underlying
configuration of points lies on the circle
while the Delsarte conditions (2) miss some non-planar
configurations. For $d\geq 3$ even (1) sometimes fails to track the dimension.
For each dimension it is sufficient to consider only configurations of $d+1$ points. If any subset
of $d+1$ points of a spherical $co$ de is -dimensional, then the whole code is -dimensional.
For $d=2$ the Gram matrix has the form$)$$\mathbb{S}^{1}$

$d$

$d$

$d$

(5)

$T=(\begin{array}{lllll}1 cos\alpha cos \betacos \alpha l cos \gammacos \beta cos\gamma 1 \end{array})$

The Gegenbauer polynomials for $d=2$ are the Chebyshev polynomials of the first kind, $G_{k}^{(2)}(t)=$$\cos$ k(arccos), and therefore (2) is equivalent to
$t$

(6)

$\cos k\alpha+\cos k\beta+\cos k\gamma\geq-\frac{3}{2}$

It is easy to see that (6) does not guarantee that rank $(T)=2$ . For instance the values $\alpha=\beta=$
satisfy this inequality for all positive integer , while rank $(T)=3$ . At the same time,: for instance, $\det(G_{3}^{(2)}(T))=$
using (1) points out that this is not a valid configuration on$-4<0$ , so these conditions do not hold for $k=3$ . The fact that such exists is not accidental: weproved that if rank $(T)=3$ then there always is a value of such that$\frac{2}{3}\pi,$$k$$\gamma=\frac{1}{3}\pi$$S^{(1)}$

$k$

$k$

Theorem 2.1 For$\alpha,$$\beta,$$\gamma\in[0, \pi]$$G_{k}^{(2)}(T)\not\geq 0.$, the matrix$(\begin{array}{llll}1 cosk\alpha cos k\betacosk\alpha 1 cos k\gammacosk\beta k\gamma cos 1 \end{array})$, if and only if there are three points
is positive semidefinitefor all $k=0,1,$$x_{3}\cdot x_{1}=\cos\beta.$$x_{2}\cdotx_{3}=\cos\alpha,$circle such that $x_{1}\cdot x_{2}=\cos\gamma,$$\ldots$$x_{1},$ $x_{2},$$x_{3}$

on a unit

4
Things become more involved for larger dimensions. As an example, let $d=3$ and consider
configurations of 4 points on the 3-sphere such that all the inner products except two of them are, and $t_{12}=u,$ $t_{34}=v$ . This gives a Gram matrix of the form
$t_{ij}$$0$$T=(\begin{array}{llll}1 u 0 0u 1 0 00 0 1 v0 0 v l\end{array})$

To see how much we lose by replacing the rank condition with the positivity constraints, we evaluate$k=1,2,$, (thethe matnices
are the Legendre polynomials) and check whether the$\det
T=(1-u^{2})(1-v^{2})$, the corresponding section of the elliptope
resulting matrices are p.d. Since
is a square $(0\leq u\leq 1,0\leq v\leq 1)$ . It is not hard to show that for $u=v=0.9$ all Gegenbauer
matrices are still positive definite but the dimension of this configuration (rank of the matrix) is
not 3.
$G_{k}^{(3)}(T),$$G_{k}^{(3)}$$\ldots$

3 Discussion
1. Letto be the set of reference points on the sphere. Paper [23] provesthat any spherical set of points $C=\{x_{1}, \ldots, x_{M}\}$ satisfies$Q=\{q_{1}, \ldots, q_{m}\}\subset \mathbb{S}^{d-1}$$(G_{k}^{(d,m)}(t_{ij}, u_{i}, u_{j}))_{1\leq i,j\leq M}\succeq 0 (k=1,2, \ldots)$

where the functions$G_{k}^{(d,m)}$are defined above (3), and,(7)$t_{ij}=(x_{i}, x_{j}),$ $u_{i}=(u_{i,1}, \ldots, u_{i,m}),$ $u_{j}=$$m$ . In particular, with $m=1$ we recover the$u_{p.l}=(x_{p}, q_{l}),p=1,2;l=1,$
corresponds to the classical Schoenberg’s theorem.
positivity conditions of [5], while
As a direct corollary of the statement for two-dimensional codes that we proved, for $m=d-2,$
inequalities (7) are able to substitute the rank condition. It would be interesting to find the minimal$m$ satisfying this condition.
For $m=1$ , the main problem is to find out when inequalities (7) fail to confinn the rank, andtherefore to determine how strong is the method employed in [5].
$(u_{j,1}, \ldots, u_{j,m}),$$\ldots,$$Q=\emptyset$

2. It would be interesting to investigate the impact of SDP relaxations (1) $-(2)$ for spherical codes
and to estimate the maximum distance between matrices that satisfy (1) and the rank condition in(4). Based on the outcome of this research, it is possible to estimate the accuracy of the bounds on$T$codes derived from SDP problems.
that are
3. Finally, it would be interesting to provide a complete description of point sets on
isolated by the Delsarte conditions (2). This will provide a characterization of $M\cross M$ matrices $T=$
for which the conditions $\{(G_{k}^{(d,d-2)}(t_{ij}, u_{i}, u_{j}))_{1\leq i,j\leq M}\succeq 0, k=1,2, \ldots\}$ are equivalent
to the rank condition in (4). Such matrices correspond to valid point configurations on the sphere$\mathbb{S}^{1}$$(t_{ij})$$\mathbb{S}^{d-1}.$

5References[1] G. E. Andrews, R. Askey, and R. Roy.

Special functions, volume 71 of Encyclopedia of
Mathematics and its Applications. Cambridge University Press, Cambridge, 1999.

[2] K. M. Anstreicher. The thirteen spheres: a new proof. Discrete Comput. Geom., 31(4):613-

625, 2004.
[3]

C. Bachoc. Linear programming bounds for codes in Grassmannian spaces. IEEE Trans.
Inform. Theory, $52(5):2111-2125$ , 2006.

[4] C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin. Invariant semidefinite programs. In

Handbook on semidefinite, conic and polynomial optimization, volume 166 of Internat. Ser.
Oper. Res. Management Sci., pages 219-269. Springer, New York, 2012.

[5]

C. Bachoc and F. Vallentin. New upper bounds for kissing numbers from semidefinite programming. J. Amer. Math. Soc., $21(3):909-924$ , 2008.

[6]

C. Bachoc and F. Vallentin. Semidefinite programming, multivariate orthogonal polynomials,
and codes in spherical caps. European J. Combin., $30(3):625-637$ , 2009.

[7]

A. Barg and P. Purkayastha. Bounds on ordered codes and orthogonal arrays. Mosc. Math. J.,$9(2):211-243$ , back matter, 2009.

[8] S. Bochner. Hilbert distances and positive definite functions. Ann. of Math. (2), 42:647-656,

1941.

[9] P. Brass, W. Moser, and J. Pach. Research problems in discrete geometry. Springer, New York,

2005.

[10]

H. Cohn and N. Elkies.
$157(2):689-714$ , 2003.

[11]

New upper bounds on sphere packings. I. Ann. of Math. (2),

H. Cohn and Y. Zhao. Sphere packing bounds via spherical codes. arXiv:1212.5966, 2012.

[12] P Delsarte. Bounds for unrestricted codes, by linear programming. Philips Res. Rep., 27:272-

289, 1972.

[13] P. Delsarte. An algebraic approach to the association schemes of coding theory. Philips Res.

Rep. Suppl., (10): $vi+97$ , 1973.

[14] P. Delsarte, J. M. Goethals, and J. J. Seidel. Spherical codes and designs.
cata, $6(3):363-388$ , 1977.

Geometriae Dedi-[15] M. M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms andCombinatorics. Springer-Verlag, Berlin, 1997.

[16]

G. A. Kabatyansky and V. I. Levenshtein. Bounds for packings on the sphere and in space.
Problems ofInformation Transmission, $14(1);3-25$ , 1978.

[17]

M. Laurent and S. Poljak. On a positive semidefinite relaxation of the cut polytope. Linear
Algebra Appl., 223/224:439-461, 1995. Special issue hononing Miroslav Fiedler and Vlastimil
Pt\’ak.

6[18] V. I. Levenshtein. Boundaries for packings in $n$ -dimensional Euclidean space. Dokl. Akad.
Nauk SSSR, 245(6): 1299-1303, 1979.
[19]

V. I. Levenshtein. Designs as maximum codes in polynomial metric spaces. Acta Appl. Math.,$29(1-2):1-82$ , 1992. Interactions between algebra and combinatorics.

[20] V. I. Levenshtein. Universal bounds for codes and designs.
Vol. I, , pages 499-648. North-Holland, Amsterdam, 1998.

In Handbook of coding theory,$\Pi$[21] R. J. McEliece, E. R. Rodemich, H. Rumsey, Jr., and L. R. Welch. New upper bounds on therate of a code via the Delsarte-MacWilliams inequalities. IEEE Trans. Information Theory,-23(2): 157-166, 1977.

$IT$[22] O. R. Musin. The kissing problem in three dimensions. Discrete Comput. Geom., $35(3):375-$

384, 2006.
[23]

O. R. Musin. Multivariate positive definite functions on spheres. $arXiv;math/0701083$ , 2007.

[24] O. R. Musin. Bounds for codes by semidefinite programming. Tr. Mat. Inst. Steklova, 263(Geometriya, Topologiya i Matematicheskaya Fizika. I):143-158, 2008.
[25] O. R. Musin. The kissing number in four dimensions. Ann. ofMath. (2), $168(1);1-32$ , 2008.
[26] A. M. Odlyzko and N. J. A. Sloane. New bounds on the number of unit spheres that can toucha unit sphere in n dimensions. J. Combin. Theory Ser. A, $26(2):210-214$ , 1979.

[27] I. J. Schoenberg.

Metric spaces and completely monotone functions. Ann. of Math. (2),$39(4):811-841$ , 1938.

[28] A. Schrijver. New code upper bounds from the Terwilliger algebra and semidefinite programming. IEEE Trans. Inform. Theory, $51(8):2859-2866$ , 2005.
[29] P. M. L. Tammes. On the origin of number and arrangement of the places of exit on the sufface

ofpollen-grains. Amsterdam, de Bussy, 1930.