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 review the use of binary hypothesis testing for the derivation of the sphere packing bound in channel coding, pointing out a key difference between the classical and the classical-quantum setting. In the first case, two ways of using the binary hypothesis testing are known, which lead to the same bound written in different analytical expressions. The first method historically compares output distributions induced by the codewords with an auxiliary fixed output distribution, and naturally leads to an expression using the Renyi divergence. The second method compares the given channel with an auxiliary one and leads to an expression using the Kullback–Leibler divergence. In the classical-quantum case, due to a fundamental difference in the quantum binary hypothesis testing, these two approaches lead to two different bounds, the first being the “right” one. We discuss the details of this phenomenon, which suggests the question of whether auxiliary channels are used in the optimal way in the second approach and whether recent results on the exact strong-converse exponent in classical-quantum channel coding might play a role in the considered problem.
A multiple-access channel transmits messages from several senders to one receiver. For quantum outputs, the receiver must distinguish states depending on all messages, while tests for different decoding errors may not commute. In this paper, we give a self-contained account of simultaneous decoding, in which one joint measurement recovers the messages at the established achievable rates using independent codebooks. The proof combines Sen's tilted-subspace method with Cheng's analysis of the pretty-good measurement, a standard measurement for distinguishing quantum states. Auxiliary labels close to a common reference state separate the geometric directions associated with different errors. A Gram-matrix bound then allows separately chosen binary tests to certify the performance of one measurement. The labels are removed from the completed decoder, leading to a deterministic packing theorem that applies to finite state ensembles, including unequal priors. We develop the two-sender case first, with worked examples and figures, before treating any fixed number of senders. Sharper finite-error guarantees for the same decoder are developed separately, with sharp bounds for two specified steps of the analysis rather than a claim of globally optimal decoding. Applications recover known achievable rates for unassisted and entanglement-assisted classical communication, distributed classical compression with quantum side information, and coherent-state communication through a beamsplitter or passive multiport device. The common proof makes the geometric mechanism and its quantitative consequences available without repeating the construction for each application.