The Covering Radius of the Reed--Muller Code RM(1,9) is 242

Qichun Wang, Yueying Lou, Zifan Wang

Oct 13, 2026arXiv:2610.17871v1

cs.IT

Scorecard· 16/16

8.0/10 impact

Resolves a four-decade-old open problem (covering radius of RM(1,9)=242) with a compact, plausible argument; impact limited to a niche community and tempered by verification risk.

Abstract

What is the covering radius of the Reed--Muller code RM(1,9) ? This is a long-standing open problem in cryptography and coding theory. In this paper, we resolve this problem, and prove that the covering radius of RM(1,9) is 242. We exclude nonlinearity 244 by obtaining a cubic Boolean function achieving a sharp Walsh $\ell^1$ bound. Its equality cases reduce either to an impossible cubic hyperplane restriction or to two homogeneous cubic forms in the Brier--Langevin classification. To exclude nonlinearity 243, we deduce the inequality ${\Vert W_g\Vert }_{1}+2|W_g(0)|\le 10368$ , and then reduce either to a spectrum bounded by 24 or to the same expression to be at least 10496.

AI Impact Assessments

(1 model)

Assessment: "The Covering Radius of the Reed–Muller Code RM(1,9) is 242"

Core Contribution

The paper claims to settle a problem open for more than four decades: the maximum nonlinearity of 9-variable Boolean functions, equivalently the covering radius of RM(1,9). The previous bounds were 242 ≤ ρ ≤ 244. The lower bound comes from the Kavut–Yücel rotation-symmetric functions, and the upper bound is the Parseval bound. The authors exclude 244 and 243 as follows.

Excluding 244. A function with ‖W_f‖∞ = 24 must have Walsh values in {±8, ±24}, with exact multiplicities. A derived cubic function g = (W_f − 8)/16 mod 2 then satisfies ⟨(−1)^f, W_g⟩ = −10240.

- Theorem 2 proves a sharp bound ‖W_g‖₁ ≤ 10240 for every 9-variable cubic, with only two equality cases.

- Case (B) is eliminated by showing that f would have a cubic restriction to a hyperplane, which a spectrum-counting argument rules out.

- Case (A) is handled by an involutive "residue duality" g → h → g on the homogeneous cubic part. This yields the algebraic conditions J(J(P)) = P and C(P) = 0, which are checked against the 349 Brier–Langevin orbits of RM(3,9)/RM(2,9). Only classes 282, 290 and the zero form survive. The zero form fails on a quadratic ℓ₁ norm. Classes 282 and 290 are killed by hand through determinant and Hermitian-determinant models, each showing max|W_g| ≥ 80.

Excluding 243. The authors prove a perturbed ℓ₁ bound, ‖W_g‖₁ + 2|W_g(0)| ≤ 10368. Reducing the 243 case to the excluded 244 spectrum gives the identity ⟨(−1)^f, W_g⟩ = −10496 + 2W_g(0). The resulting contradiction (10496 ≤ 10368) has a margin of 128.

The overall strategy is elementary and elegant: divisibility of cubic Walsh spectra, sharp ℓ₁ extremal inequalities via quadratic majorants (Φ(z) ≥ |z|), and a self-duality constraint that makes the classification tractable.

Methodological Rigor

The core chain is checkable by hand. I spot-checked the Parseval multiplicities (64·64 + 448·576 = 2¹⁸), the 253952 < 262144 contradictions, and the 10368 versus 10496 gap. All are consistent.

The proof is short for a famous open problem, which warrants caution. Several steps are terse, such as the "finite differences permit coefficientwise division" step and the claims about which monomial selections contribute modulo 8 or 16 in Lemma 5. Some inequalities contain typographical sloppiness; for example, the even-parity bound in Theorem 5 is written as 1033 − (s−3)²/2 but is really 516.5 − (s−3)²/2 up to scaling.

The decisive step relies on a computer check of 349 classes. The text says "both supplied implementations" exist, but no code is included, and the classification of Brier–Langevin is itself a computational result from a 2003 workshop paper.

Appendix A is dense, and the identification of classes 282 and 290 with the determinant and Hermitian models depends on explicit linear substitutions that must be verified.

The paper has not been refereed, and a result of this magnitude needs independent verification. The ingredients are plausible, and the margin in the 243 case is comfortable.

Potential Impact

If correct, this closes the smallest unresolved even/odd-boundary case for RM(1,m), a classical benchmark in coding theory and Boolean-function cryptography. The value 242 matches the best known construction, so the result confirms the long-held expectation that the rotation-symmetric search had reached optimality.

It will be cited as a definitive reference, and textbooks and tables of covering radii will need updating.

Methodologically, the sharp ℓ₁ bounds for cubic Walsh spectra and the residue-duality trick may extend to other settings: RM(1,m) for odd m ≥ 11, balanced nonlinearity questions, and covering radii of higher-order RM codes. The conclusion highlights the open problem of balanced 9-variable functions with nonlinearity 242. Extension to m = 11 looks hard, since cubic classification is no longer available.

Practical or commercial impact is negligible. The result is a bound on optimal S-box and stream-cipher component nonlinearity and gives no construction.

Timeliness & Relevance

Interest in covering radii of RM codes has been revived by recent results (RM(2,7), RM(3,7), RM(4,8), RM(m−4,m)). The RM(1,9) problem is the best-known remaining gap, so the result lands at the focus of this community.

Strengths

It resolves a named, well-known open problem with a compact, conceptually clean argument.

The sharp equality-case analysis and the 128 margin in the 243 case suggest a robust argument rather than a delicate one.

It reuses existing classification infrastructure cleverly.

Limitations

The result is expected, because 242 was widely conjectured, so surprise is low.

The proof is partly computational, with no code in the paper, and Appendix A is hard to verify by reading.

The techniques are specific to m = 9 and rely on divisibility properties special to cubics in 9 variables, 2^⌈m/3⌉ with m = 9 being tidy. Generalization is unclear.

The brevity, with some under-justified steps, raises the risk of subtle gaps until independent checking occurs.

The audience is narrow: Boolean-function and coding theorists.

Overall, this is a high-impact result within a niche, with some verification risk.

Rating:8/ 10

Significance 8Rigor 7Novelty 7.5Clarity 6

Generated Oct 14, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

8.0/10 impact

Resolves a four-decade-old open problem (covering radius of RM(1,9)=242) with a compact, plausible argument; impact limited to a niche community and tempered by verification risk.