Comments on the recent improvements of the MRRW bounds

arXiv:2609.01860v1 Announce Type: cross 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.

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.

17 pages. This note contains a set of comments on the results in Chapter 2 of the OpenAI manuscript "Ten Advances in Mathematics and Theoretical Computer Science'' (August 1, 2026) and in the arXiv preprint 2608.09347 by O. Alrabiah and V. Guruswami

Information Theory (cs.IT); Combinatorics (math.CO); Quantum Physics (quant-ph)

arXiv:2609.01860 [cs.IT]

(or arXiv:2609.01860v1 [cs.IT] for this version)

https://doi.org/10.48550/arXiv.2609.01860 arXiv-issued DOI via DataCite (pending registration)

În afara temei aiqbench

Comments on the recent improvements of the MRRW bounds

Subiecte conexe