The half-rate linear programming bound for binary codes is 1/2−1/π
Abstract
In their work on sphere packing and the modular 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))√d. We prove the binary coding analogue: RD (1/2−1/π)=1/2. We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If AK±(n) denotes the smallest radius r for which a nonzero Krawtchouk (±1)-eigenfunction f exists with f(0) = 0 and f(x) ≥ 0 for all |x| ≥ r, then AK±(n)/n⟶ 1/2−1/π. The lower bound proves a mass-concentration principle similar to OpenAI's Chapter 1 for Hamming space. The upper bound, on the other hand, follows the approach of the spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu formulated a hierarchy for binary codes analogous to the spherical-code construction and improved the best known binary coding rate bounds by evaluating the first level of the corresponding hierarchy. We prove this hierarchy bounds the Delsarte program and give a construction at arbitrarily deep levels of the hierarchy, attaining the upper bound in the limit. The construction uses an N-qubit generalization of the pure-state channel of Alrabiah and Guruswami.
Related
- Linear programming bounds for binary and ternary LCD Codes
- Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size
- A proof of the Braun-Etzion-Vardy bound for binary subspace codes
- Random Algebraic Geometry Codes Approach the Half-Singleton Bound for Insertions and Deletions
- Linear Programming Bounds for Locally Recovery Codes II
BibTeX
@misc{salmon2026halfrate,
title = {{The half-rate linear programming bound for binary codes is $\frac12-\frac1π$}},
author = {Andrew Salmon},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03736},
eprint = {2609.03736},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03736},
}
RIS
TY - UNPB
TI - The half-rate linear programming bound for binary codes is 1/2−1/π
AU - Andrew Salmon
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.03736
UR - https://arxiv.org/abs/2609.03736
AB - In their work on sphere packing and the modular 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))√d. We prove the binary coding analogue: R_D (1/2−1/π)=1/2. We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If A^K_±(n) denotes the smallest radius r for which a nonzero Krawtchouk (±1)-eigenfunction f exists with f(0) = 0 and f(x) ≥ 0 for all |x| ≥ r, then A^K_±(n)/n⟶ 1/2−1/π. The lower bound proves a mass-concentration principle similar to OpenAI's Chapter 1 for Hamming space. The upper bound, on the other hand, follows the approach of the spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu formulated a hierarchy for binary codes analogous to the spherical-code construction and improved the best known binary coding rate bounds by evaluating the first level of the corresponding hierarchy. We prove this hierarchy bounds the Delsarte program and give a construction at arbitrarily deep levels of the hierarchy, attaining the upper bound in the limit. The construction uses an N-qubit generalization of the pure-state channel of Alrabiah and Guruswami.
ER -