Asymptotic rate bounds for binary codes
Follow the latest progress by email.
What is the largest asymptotic rate of binary codes with relative distance 0<δ<1/2? The classical McEliece–Rodemich–Rumsey–Welch bound is the upper-bound baseline; related spherical-code questions use inner-product parameter 0<s<1.
Why it matters and what counts as progress
Why it matters: Improving rate bounds narrows the possible density of error-correcting codes beyond longstanding linear-programming baselines.
What counts as progress: Improve the rate upper bound at fixed δ, obtain larger code constructions, or strengthen the corresponding spherical linear-programming bounds.
How the problem developed
- 1977 · Upper bound [1]
McEliece, Rodemich, Rumsey and Welch Introduced the linear-programming MRRW upper bound for the asymptotic rate of binary codes at fixed relative distance.
OpenAI Astra Reported an exponentially improved upper bound on maximum binary-code size at every prescribed relative distance 0<δ<1/2, strictly below the optimized MRRW bound.
AI contribution
Ten Advances in Mathematics and Theoretical Computer Science
For every relative binary distance 0<δ<1/2, Chapter 2 gives an asymptotic rate bound strictly below the classical MRRW bound. Companion spherical-code bounds improve the localized linear-programming hierarchy for 0<s<1.
Sources
- McEliece et al., New Upper Bounds on the Rate of a Code via the Delsarte-MacWilliams Inequalities
- OpenAI, Ten Advances in Mathematics, Chapter 2
- OpenAI, Ten Advances in Mathematics release and attribution
- OpenAI, code-bound formalization manifest
- OpenAI, binary-code comparator statement
- OpenAI, spherical-code comparator statement
- Sienicki and coauthors, Chapter 2 human review
Website timeline
Publication dates and editorial changes.