Three point bound for sphere packing

The proof is very similar to the proof of linear programming bound for sphere packing.

First note that \(f_3(x,y)\) can be replaced by \([f_3(x,y)+f_3(y,x)]/2\). So we may assume that \(f_3\) is symmetric.

Consider the kernel \(K:\mathbb{R}^{n} \times \mathbb{R}^{n} \rightarrow \mathbb{R}\) given by \[\begin{align} K(x,y) = f_{3}(x,y) + \mathbb{I}_{x=y} f_2(x) \end{align}\]

Note that \(K(x,y)\) is positive definition. For any \(w_{\bullet} : \mathbb{R}^{n} \rightarrow \mathbb{R}\) with finite support, we have \[\begin{align} & \sum_{x,y \in \mathbb{R}^{n}} K(x,y)w_{x}w_{y} \\ = & \sum_{x \in \mathbb{R}^{n}}^{} f_2(0) w_x^{2}+\sum_{x,y \in \mathbb{R}^{n}} f_3(x,y)w_{x}w_{y} \ge 0. \end{align}\] Here, we know that \(f_{2}(0) \ge 0\) since \(\hat{f_2} \ge 0\).

Let \(\Lambda \subseteq \mathbb{R}^{n}\) be a lattice and let \(F \subseteq \mathbb{R}^{n}\) be a finite set such that \(F \rightarrow \mathbb{R}^{n}/ \Lambda\) is injective. Therefore, we get that the set \(F + \Lambda\) is a periodic packing. We also assume that \(\Lambda + F\) is a unit-distance packing, that is no two pair of points are at a distance strictly less than \(1\).

We now try to sum up the set \(K(v_2-v_0,v_1-v_0)\) as \(v_0,v_1,v_2\) are vertices of all possible triangles that we can form with points in \(\Lambda + F\) up to translational symmetry. We consider the sum \[\begin{align} S_{\Delta} = \sum_{\lambda_1, \lambda_2 \in \Lambda} \sum_{s_0,s_1,s_2 \in F} K(\lambda_1 + s_1- s_0, \lambda_2+s_2 - s_0). \end{align}\] Now let us think of \(v_0,v_1,v_2 \in \Lambda + F\) as vertices of a triangle. We can get three types of triangular shapes.

1. Triangles where \(v_0,v_1,v_2\) are distinct,
2. Where exactly one of \(v_0=v_1\), \(v_1=v_2\) or \(v_2=v_0\) holds,
3. Where \(v_0=v_1=v_2\).

For the first type of triangle, we will give get six terms in \(S_{\Delta}\). By symmetry, we can reduce them to three. \[\begin{align} & K(v_2-v_0,v_1-v_0) + K(v_1-v_2,v_0-v_2) + K(v_0-v_1,v_2-v_1 ) \\ + & K(v_1-v_0,v_2-v_0) + K(v_0-v_2,v_1-v_2) + K(v_2-v_1,v_0-v_1 ) \\ & = 2[ K(v_2-v_0,v_1-v_0) + K(v_1-v_2,v_0-v_2) + K(v_0-v_1,v_2-v_1 ) ] \\ \end{align}\]

In the first type of triangle, we get \[\begin{align} 2[ K(v_2-v_0,v_1-v_0) + K(v_1-v_2,v_0-v_2) + K(v_0-v_1,v_2-v_1 ) ] \\ = 2 [f_3(v_2-v_0,v_1-v_0) + f_3(v_1-v_2,v_0-v_2) + f_3(v_0-v_1,v_2-v_1 )] \le 0. \end{align}\] The inequality is because if we set \(x=v_2-v_0,y=v_1-v_0\) then the term is of the form \[\begin{align} f_{3}(x,y) + f_{3}(-x,y-x) + f_{3}(-y,x-y), \|x\|,\|y\|, \|x-y\| \ge 1. \end{align}\]

Similarly, in the second case, suppose that \(v_1=v_2\). Then, \[\begin{align} K(v_2-v_0,v_1-v_0) + K(v_1-v_2,v_0-v_2) + K(v_0-v_1,v_2-v_1 ) \\ = f_2(v_1-v_0)+f_3(v_1-v_0,v_1-v_0) + f_3(0,v_0-v_1) + f_3(v_0-v_1,0) \le 0. \end{align}\] The same happens in the cases when \(v_1=v_0\) or \(v_0=v_2\) holds.

For the third case, we get \(v_1=v_2=v_3\). By translational symmetry, we can have that all the points lie exactly in \(F\). So there are exactly \(\#F\) times such a triangle will form in the sum and each will contribute to the sum \[\begin{align} \left( f_3(0,0) + f_2(0) \right). \end{align}\]

Hence, we get that \(S_{\Delta} \le \#F \cdot K(0,0)\).

On the other hand, it is clear that \[\begin{align} S_{\Delta} = \sum_{\lambda_1, \lambda_2 \in \Lambda} \sum_{s_0,s_1,s_2 \in F} f_3(\lambda_1 + s_1- s_0, \lambda_2+s_2 - s_0) + \sum_{\lambda \in \Lambda} \sum_{s_0,s_1 \in F}^{} f_{2}(\lambda + s_1 - s_0) \\ \end{align}\] The first term is \(\ge 0\) by positive definiteness of \(f_3\) and the other term is \(\ge (\# F)^{2}/\mathop{\mathrm{vol}}(\mathbb{R}^{n} / \Lambda)\) just like in the proof of the linear programming bound for sphere packing.

Putting the lower bound and upper bound on \(S_{\Delta}\) gives the desired proof.