Solution of the Propeller Conjecture in \mathbb R ^3

It is shown that every measurable partition $\{A_1,\ldots , A_k\}$ { A 1 , … , A k } of $\mathbb R ^3$ R 3 satisfies 1 $$\begin{aligned} \sum _{i=1}^k\big \Vert \int _{A_i} x\mathrm{{e}}^{-\frac{1}{2}\Vert x\Vert _2^2}\mathrm{{d}}x\big \Vert _2^2\leqslant 9\pi ^2. \end{aligned}$$ ∑ i = 1 k ‖ ∫ A i x e - 1 2 ‖ x ‖ 2 2 d x ‖ 2 2 ? 9 π 2 . Let $\{P_1,P_2,P_3\}$ { P 1 , P 2 , P 3 } be the partition of $\mathbb R ^2$ R 2 into $120^{\circ }$ 120 ° sectors centered at the origin. The bound (1) is sharp, with equality holding if $A_i=P_i\times \mathbb R $ A i = P i × R for $i\in \{1,2,3\}$ i ∈ { 1 , 2 , 3 } and $A_i=\emptyset $ A i = ? for $i\in \{4,\ldots ,k\}$ i ∈ { 4 , … , k } . This settles positively the $3$ 3 -dimensional Propeller Conjecture of Khot and Naor (Mathematika 55(1-2):129–165, 2009 (FOCS 2008)]. The proof of (1) reduces the problem to a finite set of numerical inequalities which are then verified with full rigor in a computer-assisted fashion. The main consequence (and motivation) of (1) is complexity-theoretic: the unique games hardness threshold of the kernel clustering problem with $4\times 4$ 4 × 4 centered and spherical hypothesis matrix equals $\frac{2\pi }{3}$ 2 π 3 .