Source-linked AI summary
Comments on the recent improvements of the MRRW bounds
Alexander Barg
TL;DR
The note examines how recent improvements relate to the longstanding MRRW bounds for binary codes. It presents an LP-free coding-theoretic proof and connects the Delsarte and classical-quantum arguments through moving subspaces attached to codewords.
Problem
The note addresses why two apparently different proofs of recent MRRW-bound improvements share the same underlying idea.
Method
The note presents an LP-free proof from a one-dimensional argument and relates its Delsarte-type perspective to a decoding-based classical-quantum proof.
Results
The common mechanism is packing subspaces rather than vectors, with the subspaces moved alongside codewords.
Takeaways & Limitations
The two proof approaches yield closely related arguments because both count how many codeword-associated subspaces fit in the ambient space.
Takeaways & Limitations
The note focuses on MRRW-1 and does not attempt to determine whether new certificates imply new classical-quantum results.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
The note places recent improvements to the long-standing MRRW bounds in context and explains their shared geometric idea: replacing moving lines or vectors with moving subspaces.
- Historical context: The MRRW bounds have constrained asymptotic rates of binary codes for nearly half a century, until two concurrent works achieved a small improvement.The note focuses on the MRRW-1 case because it highlights the new ideas, while related improvements also apply to MRRW-2 and spherical codes.
- Purpose and scope: The note presents the Delsarte-type proof as an extension of the spectral method, building from the one-dimensional case and adding contextual comparisons.It explicitly claims no novelty beyond presentation and contextual remarks.
- Core idea: The central slogan is to move from packing vectors to packing subspaces and move each subspace with its codeword.This viewpoint is shared by both recent proofs and connects their apparently different arguments.
- Core idea: The new construction replaces stabilizer-fixed lines with exponentially large spaces of degree-k Boolean harmonics embedded equivariantly across retained Fourier levels.The larger subspaces account for the asymptotic improvement described in the note.
2. THE RESULT
The section states the asymptotic coding-theory setting and presents two new bounds that are identical, with their common value characterized by an optimization whose infimum lies on a boundary curve.
- Coding-theory setting: The asymptotic problem concerns the largest rate of binary codes with prescribed relative Hamming distance.For codes C⊂{0,1}^n, the rate, minimum distance, and maximal code size A2(n,d) are defined in the section.
- New bounds: The two recently cited results are stated as new bounds for the asymptotic rate-distance problem.The section cites concurrent results as Theorems [18, Eq. (2)] and [2, Theorem 2].
- Equality of bounds: RMQC(δ) = κH(δ) for 0 < δ < 1/2, so the two results are identical.The section explicitly introduces this equality after observing that the results coincide.
- Endpoint bounds: At the endpoints, the boundary recovers MRRW-1 and the Bassalygo–Elias bound.The endpoint correspondences include r=δ, b=0 for MRRW-1 and r=0 for the other endpoint.
- Optimization structure: For fixed δ∈(0,1/2), the infimum in the optimization is attained on ΓH(a,b)=1−2δ, yielding the stated equality.The MQC bound therefore traverses the boundary curve of the OAI optimization problem with the same objective function.
- Small-distance regime: For δ≤0.0744, the minimum is attained at r=0 and RMQC(δ)=RBE(δ).This identifies the small-distance regime in which the MQC expression equals the Bassalygo–Elias bound.
3. PRELIMINARIES
The preliminaries recast Hamming-space functions through Fourier levels and coordinate maps, establishing the raising/lowering structure used to build positive-definite kernels. The construction records coordinate actions in separate slots so attached vectors have inner products encoding distance-dependent multipliers.
- Fourier levels: The Hamming space is represented multiplicatively as Xn = {±1}n, whose character basis decomposes functions into Fourier levels Vi.The isometry group is Bn = {±1}n ⋊Sn, with stabilizer Stab(x) ∼= Sn.
- Point-attached vectors: Each point x determines a line in every Fourier level fixed by Stab(x), represented by the corresponding zonal vector.The line is spanned by vi,x and is fixed by the point stabilizer.
- Kernel construction: Separating coordinate summands realizes products t(x, y)⟨u, u′⟩ as inner products, producing positive-definite kernels for the certificate.The auxiliary factor W records each coordinate action in its own slot.
- Coordinate maps: Coordinate maps Ci,i+1 and Ci,i−1 are isometries with orthogonal ranges, splitting the coordinate operator into raising and lowering components.The raising and lowering actions change Fourier level only by one.
- Coordinate maps: For f ∈ Vi, the two components have squared norms governed by i and n −i, so the normalized operator is an isometry.These quantities count coordinates that lower or raise the level, respectively.
4. THE CLASSICAL BOUND: ONE LINE PER CODEWORD
The classical bound attaches one equivariantly moving line to each codeword and uses a spectral, positive-definite certificate whose scalar kernel depends only on Hamming distance. Its proof is presented in full-space form and prepares the direct generalization from lines to subspaces.
- Full-space formulation: The proof rewrites the classical MRRW-1 argument on the full Hamming space rather than using only radial functions.This unwrapping is technically useful because the improved construction cannot apparently be written using radial functions.
- Spectral certificate: The transition coefficients form the level transitions of the Ehrenfest urn chain, with binomial detailed balance.The associated symmetric tridiagonal matrix J(0) represents the resulting three-term recurrence.
- The field of lines: The field of lines x 7→Rux is Bn-equivariant, making the kernel K(x, y) depend only on Hamming distance.The same invariance mechanism is later reused for the subspace construction.
- The bound: Theorem 4.6 bounds the size of a code with minimum distance at least δn under the spectral condition Λ > s, where s = 1 −2δ.The certificate is positive definite through the transition coefficients and Perron relation.
- The bound: The line proof generalizes directly to subspaces, while Cauchy-Schwarz in the classical derivation causes a loss that evaluating tr(Π2) can avoid.The resulting refinement is only non-exponentially sharper.
5. THE IMPROVED BOUND : ONE SUBSPACE PER CODEWORD
The improved construction replaces each codeword’s line with an exponentially larger moving subspace built from degree-k Boolean harmonics. Equivariance preserves a scalar, distance-only kernel, while the projection bound counts how many nearly orthogonal subspaces fit in the ambient space.
- One subspace per codeword: The new construction embeds an isometric copy of the degree-k Boolean harmonics into every retained Fourier level.For k = 0, the harmonic space is the constants and the construction reduces to the zonal-vector case.
- The field of subspaces: Each codeword x carries the dE-dimensional subspace Ex = im Ψx, which moves equivariantly under the group action.Equivalently, its projector satisfies Pgx = ρ(g)Pxρ(g)∗.
- The field of subspaces: The nontrivial stabilizer representation Hk is the source of the local index b and gives the attached subspace exponentially large dimension.This is the mechanism identified for the asymptotic improvement.
- The field of subspaces: Equivariance makes K(x, y) = tr(PxPy) Bn-invariant and therefore a scalar function only of dH(x, y).Thus the certificate remains two-point and scalar despite using higher-dimensional objects.
- The projection bound: The projection bound interprets the argument as packing dE-dimensional subspaces into an ambient space of dimension D, with factor 1−sΛ−s accounting for overlap.Inequalities bound nearly orthogonal subspaces associated with code points at distance at least d.
6. ASYMPTOTICS
The asymptotic analysis scales k and L linearly with n, evaluates the spectral quantities by standard asymptotics, and converts the finite-dimensional projection bound into the optimized expression for the improved rate bound.
- Asymptotics: When n →∞ with k/n →b and L/n →a, where 0 ≤b < a ≤1/2, Lemma 6.1 gives the relevant asymptotics for the spectral parameter.The proof uses Perron-Frobenius for an upper bound and Rayleigh-Ritz for a matching lower bound.
- Asymptotic bound: The finite-dimensional hypothesis Λ > s holds asymptotically when ΓH(a, b) > 1 −2δ, and binomial asymptotics yield the expression optimized in the improved bound.The substitutions match those used to establish the identity between the coding-theoretic and quantum parameterizations.
7. THE PROBABILISTIC PICTURE: CLASSICAL-QUANTUM CHANNELS
The probabilistic proof attaches codeword-dependent typical subspaces to mixed quantum outputs while keeping a fixed ambient typical subspace. Its packing bound matches the Delsarte construction because both use subspaces of the same asymptotic dimensions, differing only between probabilistic and exact packing.
- Probabilistic picture: The concurrent quantum proof is reinterpreted as packing subspaces that move with codewords, paralleling the Delsarte proof.The proofs differ in how the subspaces are produced and packed: typicality and a strong converse versus exact positivity and trace counting.
- Pure-state channel: The pure-state channel attaches an equivariant line to each codeword, with overlaps depending only on Hamming distance.Translations and coordinate permutations move these lines equivariantly under the Hamming-space isometry group.
- Ambient typical subspace: The average output becomes diagonal in the Hadamard basis, with a Bernoulli(q) spectrum whose typical subspace has dimension 2^(h2(a)+o(1))n.Here a=q, and this typical subspace is the ambient space used in the classical construction.
- Mixed-qubit channel: The mixed-qubit channel preserves the average output while making conditional outputs codeword-dependent through a sign-flipping Z-component.The common X-component defines the fixed ambient space, whereas opposite Z-components encode the moving distinction between codewords.
- Moving typical subspaces: Each conditional typical subspace moves with its codeword and has dimension 2^(h2(b)+o(1))n, matching the equivariant subspace field algebraically.The quotient of ambient and conditional dimensions corresponds to the Holevo-information expression.
- Matching the bounds: Choosing the channel parameter so the pretty-good-measurement error equals δ reproduces the Delsarte parameter substitutions and shows the optimal channel is strictly mixed.The note identifies η>0 with b>0 and states that both approaches pack subspaces of asymptotically the same dimensions.
8. COMPLEMENTS AND FURTHER REMARKS
The further remarks explain why moving subspaces preserve a scalar two-point certificate, identify extensions and possible improvement routes, and distinguish exact finite-length algebra from asymptotic channel typicality. They also mark several directions as unresolved or speculative.
- Moving subspaces: Moving subspaces retain a scalar two-point Delsarte certificate because their trace kernel is invariant and depends only on Hamming distance.This contrasts with fixed-base higher-degree constructions, which generally lead to matrix-valued and three-point programs.
- Spectral mechanism: The new proof replaces the failed higher-degree positivity route with a Gram factorization that yields a strictly smaller eigenvalue.For k>0, individual summands are not Delsarte-feasible, so the improvement requires a different mechanism.
- Extensions: The spectral approach extends to Johnson space and the real sphere, where the discussed construction strictly improves the Kabatiansky–Levenshtein bound.The same ideas also improve MRRW-2 for constant-weight and general binary codes.
- Extensions: The remarks suggest broader homogeneous-space applications, but such extensions may be technically more involved and of more limited interest.The note specifically mentions q-ary Hamming, projective, Grassmann, and ordered Hamming spaces.
- Possible improvements: A further improvement could come from reducing the spectral-radius gap between the distance-multiplication matrix and the certificate matrix.The boundary condition depends on ΓH, so the relevant opportunity is specifically the remaining spectral-radius gap.
- Open directions: For the channel hierarchy, the limit as ℓ→∞ remains unknown, and at fixed ℓ improvements could target either decoding or output-state design.The PGM error criterion is sufficient, and bitwise optimality is stated only for linear codes.
- Classical–quantum versus Delsarte: A better output-symmetric channel would not immediately yield a Delsarte certificate because channel positivity does not supply the required sign change and spectral ingredients.The channel kernel is nonnegative everywhere, whereas a Delsarte certificate must be nonpositive at distances at least δn.
- Methodological distinction: The quantum argument is asymptotic through typical subspaces, while the Delsarte argument is exact at finite blocklength.This is a methodological distinction between the two proofs, not merely a difference in presentation.