# Delsarte's Method ###### tags: `optimization` `kissing-number-problem` Reference ~ Musin, O. (2008). [*The Kissing Number in Four Dimensions*](https://www.jstor.org/stable/40345407). Annals of Mathematics, 168(1), second series, 1-32. [PDF](https://arxiv.org/pdf/math/0309430.pdf) Remark ~ This method works for cases $n=8$ and $n=24$. From here on we will speak of $x \in S^{n-1}$, alternatively, * of points in $S^{n-1}$, or * of unit vectors in $\mathbb{R}^n$. Let $X=\{x_1, \dots, x_M\}$ be any finite subset of the unit sphere $S^{n-1}\subset \mathbb{R}^n$. Denote that * $\phi_{i, j} = \mathrm{dist}(x_i, x_j)$ the spherical (angular) distance between $x_i$ and $x_j$. * Clearly, $\cos\phi_{i, j} = x_i \cdot x_j$. ## Schoenberg's Theorem with Its Extension Let $u_1, \dots, u_M$ be any real numbers. Then we have $$ 0 \leq \Vert \sum u_i x_i \Vert = \sum_{i,j} \cos\phi_{i, j} u_i u_j, $$ or equivalently the *Gram matrix* $[\cos\phi_{i, j}]$ is positive semidefinite. Schoenberg extend this property to *Gegenbauer polynomials* $G_k^{(n)}$. He proved that * The matrix $\left[ G_k^{(n)} (\cos\phi_{i, j}) \right]$ is positive semidefinite for any finite $X$. * If $f(t)$ is a real polynomial and for any finite $X$ the matrix $\left[ f (\cos\phi_{i, j}) \right]$ is positive semidefinite, then $f(t)$ is a linear combination of $G_k^{(n)} (t)$ with nonnegative coefficients. ## Gegenbauer Polynomials $G_k^{(n)}$ > For easy understanding and implementation of this polynomial, we employ the recurrence form. *Gegenbauer* or *ultraspherical* polynomials $G_k^{(n)}$ can be defined by the recurrence formula: $$ \begin{aligned} G_0^{(n)} &= 1, \\ G_1^{(n)} &= t, \\ G_k^{(n)} &= \frac{(2k + n -4)tG_{k-1}^{(n)} - (k-1)G_{k-2}^{(n)}}{k+n-3}. \end{aligned} $$ ### Delsarte's Inequality If a symmetric matrix is positive semidefinite, then the sum of all its entries is nonnegative. With Schoenberg prove that the matrix $\left[ G_k^{(n)} (t_{i, j}) \right]$ is positive semidefinite, where $t_{i, j} = \cos\phi_{i, j}$, one implies that $$ \tag{1} \sum_i \sum_j G_k^{(n)} (t_{i, j}) \geq 0. $$ ## Lower bound of $S(X)$ Now we denote by $G_n^+$ the set of continuous function $f:[-1, 1]\to\mathbb{R}$ representable as series $$ f(t) = \sum_{k=0}^\infty c_k G_k^{(n)}(t) $$ whose coefficients satisfy the following conditions: * $c_0 > 0$, * $c_k > 0$ for $k=1,2,\dots$, and * $f(1) = \sum_k c_k < \infty$. With equation $(1)$, we get $$ \tag{2} S(X) = \sum_{k=0}^\infty c_k \left( \sum_i \sum_j G_k^{(n)} (t_{i, j}) \right) \geq c_0 \sum_i \sum_j G_0^{(n)} (t_{i, j}) = c_0 M^2. $$ This is the lower bound of $S(X)$. ## Upper bound of $S(X)$ Let $X=\{x_1,\dots,x_M \}$ be a spherical $\psi$-code, i.e. for all $i \neq j$ * $t_{i, j} = x_i \dot x_j \leq z := \cos\psi$, or equivalently * $t_{i, j} \in [-1, z]$ but $t_{i, i} = 1$. Suppose $f\in G_n^+$ and $f(t)\leq 0$ for all $t\in [-1, z]$. Then $f(t_{i, j})\leq 0$ for all $i\neq j$. That implies $$ S_f(X) = M f(1) + 2 f(t_{1, 2}) + \dots + 2f(t_{M-1, M}) \leq M f(1). $$ ## Objective Find suitable polynomial $f\in G_n^+$ such that $f(t)\leq 0$ for all $t\in[-1, z]$. Then $$ c_0 M^2 \leq S_f(X) \leq Mf(1), $$ which yields that $$ M \leq \frac{f(1)}{c_0}. $$ Let $A(n, \psi)$ be the maximal size of a $\psi$-code in $S^{n-1}$, then $$ A(n, \psi) \leq \frac{f(1)}{c_0}. $$ For the kissing number problem, given $z=0.5$ and $c_0 = 1$, one obtains that $$ k(n) = A(n, \frac{\pi}{3}) \leq f(1). $$