The half-rate linear programming bound for binary codes is $\frac12-\frac1π$

Source abstract

In their work on sphere packing and the conformal bootstrap, Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini conjectured the exact high-dimensional exponent of the Cohn--Elkies sphere-packing linear program. OpenAI's Chapter 1 subsequently proved their conjecture by establishing that both Fourier sign-uncertainty radii are $(1/π+o(1))\sqrt d$. We prove the binary coding analogue: the half-rate point of the asymptotic binary Delsarte linear program is $1/2-1/π$; equivalently, $$R_D\!\left(\frac12-\frac1π\right)=\frac12.$$ We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If $A^{\mathrm K}_{\pm}(n)$ denotes the first radial layer after which an origin-vanishing Krawtchouk $(\pm1)$-eigenfunction can be nonnegative, then $$\frac{A^{\mathrm K}_{\pm}(n)}n\longrightarrow \frac12-\frac1π.$$ The common lower bound is the Hamming space counterpart of the mass-concentration principle in the Chapter 1 proof. The upper bound has a different source. It is the binary-code counterpart of the final spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu improved the resulting binary bound and suggested the functional $Φ$ used here, but explicitly evaluated only a few low levels of the corresponding hierarchy. We construct and evaluate compatible binary certificates at every level, attaining the upper bound in the limit. The construction uses an $N$-qubit generalization of the pure-state channel of Alrabiah and Guruswami.