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.
Comments
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
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.
We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below δ, then every length-n binary code, linear or nonlinear, of relative distance δ has rate at most the channel's capacity, up to an O(n−1/2) correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly.
This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every 0<δ<21, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.
We prove two deterministic inapproximability results. First, for every fixed 0<ϵ<1/2, Euclidean GapCVP(2) is NP-hard with gap factor n1/2−ϵ under deterministic polynomial-time many-one reductions, where n denotes the lattice rank. Consequently, the Euclidean closest vector problem is NP-hard to approximate within the same factor. This improves the previous n1/400 hardness factor in Chapter 7 of the OpenAI report [Ope25]. Aharonov and Regev gave short certificates for both the YES and the NO case of GapCVP(2) at gap factor Cn, placing that problem in NP∩coNP for an absolute constant C>0 [AR05]. An NP-hard problem lying in coNP would give NP=coNP, so the factor n1/2−ϵ above cannot be improved to Cn unless the two classes coincide. Second, for every fixed 0<ϵ<1, the gap versions of binary nearest codeword and binary syndrome decoding are NP-hard with factor n1−ϵ under deterministic polynomial-time many-one reductions, where n denotes the binary block length. Consequently, both optimization problems are NP-hard to approximate within the same factor. This improves the previous n1/200 hardness factor in Chapter 7 of the OpenAI report [Ope26].
There are some bounds that are placed on the size of error correcting codes. Some of the well-known bounds are discussed in the following sections. 6.1 Definitions Let n be fixed, and let M denote the size of a code C (i.e., the number of codewords in C), and d the minimum distance between the codewords. For example, (i) for the code C = {00, 01, 10, 11} : n = 2,M = 4; d = 1; (ii) for the code C = {000, 011, 101, 110} : n = 3,M = 4, d = 2; and (iii) for the code C = {00000, 00111, 11111} : n = 5,M = 3, d = 2. Then for a q-ary (n,M, d) code, the transmission rate (also known as the information rate) is defined by R(C) = log q M n , and the relative minimum distance by δ(C) = (d − 1)/n. Note that this distance is also defined by d/n, but neater formulas are obtained by defining it as (d − 1)/n. For the binary repetition code C = {00 . . .0︸ ︷︷ ︸ 11 . . .1︸ ︷︷ ︸ n }, which is an (n, 2, n) code, we find that R(C) = log 2 2 n = n → 0 and δ(C) = n− 1 n → 0 as n→∞.
We extend the quantum-channel optimization of Alrabiah and Guruswami to q-ary constant-composition codes. We study explicit channel and flag constructions that recover selected classical asymptotic upper bounds, including the Ben-Haim--Litsyn, moving-subspace and Horn-channel bounds. We give two equivalent formulations, Gram and flag, and prove stability of the obtained upper bounds under permutation transport and generalized shortening. A hierarchy defined by bounding the output-state ranks within each flag improves strictly between consecutive levels at every composition and every positive distance below the Plotkin threshold. We provide finite matrix parametrizations of these bounds (i.e., the number of variables does not depend on the length of codes under consideration). Numerical optimization rapidly produces improvements over the known asymptotic upper bounds throughout all tested nonbinary parameter ranges. For rational input data, each finite level admits near-optimal feasible rational descriptions of polynomial length. Their feasibility can be checked exactly and their objective values computed to any prescribed accuracy in polynomial time; the associated threshold problem with a prescribed gap belongs to PromiseNP.
In this paper, we study binary constrained codes that are resilient to bit-flip errors and erasures. In our first approach, we compute the sizes of constrained subcodes of linear codes. Since there exist well-known linear codes that achieve vanishing probabilities of error over the binary symmetric channel (which causes bit-flip errors) and the binary erasure channel, constrained subcodes of such linear codes are also resilient to random bit-flip errors and erasures. We employ a simple identity from the Fourier analysis of Boolean functions, which transforms the problem of counting constrained codewords of linear codes to a question about the structure of the dual code. We illustrate the utility of our method in providing explicit values or efficient algorithms for our counting problem, by showing that the Fourier transform of the indicator function of the constraint is computable, for different constraints. Our second approach is to obtain good upper bounds, using an extension of Delsarte's linear program (LP), on the largest sizes of constrained codes that can correct a fixed number of combinatorial errors or erasures. We observe that the numerical values of our LP-based upper bounds beat the generalized sphere packing bounds of Fazeli, Vardy, and Yaakobi (2015).