Upper Bounds for Binary and Spherical Codes
What is the maximum size of a binary code of given minimum distance? The linear-programming bounds of McEliece, Rodemich, Rumsey and Welch (1977) resisted improvement for half a century. The new upper bounds are exponentially stronger at every prescribed distance, with analogous results for high-dimensional spherical codes.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Coding theory
- Posed by
- —
- Year posed
- 1977
- Years open
- 49y
- Solved
- 2026-08-01
- Model
- Astra (internal preview)
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-verified
- Publication
- Announced
- Significance
- 39 / 100
- Disclosed cost
- $182
- Wikipedia
- No dedicated article
What was actually shown
exponential improvement over the 1977 MRRW bounds; the exact rate-distance trade-off remains open
What the AI did
Generated by an internal version of OpenAI's Astra: per the announcement, the mathematical arguments were produced by the system (roughly 2,000 dollars of compute at Sol API rates across all ten results), humans prepared the manuscripts with the same model, and the model then formalized the argument in Lean. A narrated reasoning walkthrough is published for each result.
Verification
Kernel-checked Lean 4 certificate in OpenAI's public ten-proofs repository (Lean 4.32, mathlib, `lake build All`), with an independent Comparator checking route. Statement fidelity and community review of the day-old company announcement remain pending.