Comments on the recent improvements of the MRRW bounds
Abstract
The asymptotic McEliece--Rodemich--Rumsey--Welch bound (1977) limits the largest attainable rate of binary codes as a function of the relative distance. After a nearly half-century hiatus, this result was recently improved in two concurrent works, by OpenAI and by O. Alrabiah and V. Guruswami. The two arguments look entirely different, a Delsarte certificate on the one hand, a classical-quantum channel and the pretty good measurement on the other, and they yield the same bound. The purpose of this note is to explain why: in both proofs, a subspace is attached to every codeword and moved with it, and the bound counts how many such subspaces fit in the ambient space, exactly in the first case and in the probabilistic sense of typicality in the second. We also present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.
Related
- Comments on "Multidimensional Costas Arrays and Their Periodicity"
- Counterexamples and Sufficient Conditions: Comments on "Optimally-Transported Generalized Method of Moments"
- Spectral Improvements of Geometric Inequalities on Closed Kähler Manifolds
- Almost-orthogonal Strichartz estimates and radial improvements
- Distribution-Dependent Improvements of McDiarmid's Inequality via Rényi Divergence
BibTeX
@misc{barg2026comments,
title = {{Comments on the recent improvements of the MRRW bounds}},
author = {Alexander Barg},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01860},
eprint = {2609.01860},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01860},
}
RIS
TY - UNPB
TI - Comments on the recent improvements of the MRRW bounds
AU - Alexander Barg
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01860
UR - https://arxiv.org/abs/2609.01860
AB - The asymptotic McEliece--Rodemich--Rumsey--Welch bound (1977) limits the largest attainable rate of binary codes as a function of the relative distance. After a nearly half-century hiatus, this result was recently improved in two concurrent works, by OpenAI and by O. Alrabiah and V. Guruswami. The two arguments look entirely different, a Delsarte certificate on the one hand, a classical-quantum channel and the pretty good measurement on the other, and they yield the same bound. The purpose of this note is to explain why: in both proofs, a subspace is attached to every codeword and moved with it, and the bound counts how many such subspaces fit in the ambient space, exactly in the first case and in the probabilistic sense of typicality in the second. We also present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.
ER -