XSci

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

Qichun Wang, Yueying Lou, Zifan Wang

Submitted by Qichun Wang

Published October 16, 2026 · Version v1, October 16, 2026 · DOI 10.66977/xsci.2610.001i

Cryptography and Coding Theory

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 ℓ1\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 ∥Wg∥1+2∣Wg(0)∣≤10368{\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.

View PDF

Review reports

Expert review

November 5, 2026 · Recommendation: reject

Fit

Against the target journals

  • Does not meet the Certification Standard, as measured against JOURNAL OF COMBINATORIAL THEORY SERIES A (ISSN 0097-3165).

    In my view, the manuscript’s specialized focus makes its suitability for the Journal of Combinatorial Theory, Series A dependent on a clearer demonstration of its broader combinatorial significance. An independent paper by Hou, Sabo and Slaughter has already appeared online and establishes the same result. Although the works were developed independently, their proofs share substantial ideas, particularly the cubic reduction and the exclusion of nonlinearity 243. The authors should therefore explain more precisely the distinctive contribution of their reciprocity conditions and two-class reduction.

Journals the reviewer recommends

  1. DESIGNS CODES AND CRYPTOGRAPHY (ISSN 0925-1022)

    Designs, Codes and Cryptography would be a natural venue because the manuscript directly addresses coding theory and the nonlinearity of Boolean functions, both closely connected to its readership. The journal’s emphasis on algebraic methods also fits the paper’s use of cubic forms, Walsh transforms and determinant models.

Referee Report

I recommend revising the manuscript and submitting it to Designs, Codes and Cryptography. Your result settles the maximum nonlinearity of a Boolean function in 9 variables. The connection between coding theory and Boolean function theory makes the journal a natural choice. Hou’s earlier result on the same code with ambient space $\mathrm{RM}(4,9)$ appeared there [9].

The strongest part of your method is the passage from equality in a Walsh norm bound to a restriction on the cubic part of a function. Theorem 2 has two equality cases. Lemma 4 and Proposition 2 eliminate one by restricting to a hyperplane. In the other, applying the Walsh residue operation twice yields the two conditions in (25). These leave just two nonzero cubic classes. Independent checks support this reduction and the value 242. The main revision I ask for is a proof that every admissible function in those two classes reaches one of the forms treated in Appendix A.

Contribution and related work

Please compare the argument with Hou, Sabo and Slaughter, The Covering Radius of RM(1,9) is Precisely 242 (IACR ePrint 2026/2529). Both proofs give a cubic from a hypothetical function of nonlinearity 244, use the same two extremal spectral patterns, and reduce the 243 case to a contradiction using equivalent weighted bounds. The proofs diverge in the last step. Hou, Sabo and Slaughter retain 193 cubic classes and test quadratic representatives by reconstructing the sign function. Your reciprocity condition reduces that calculation to two determinant models. This is the distinction and it would emphasize in the introduction.

A brief comparison with the smaller covering-radius problems in [6], [8] and [17] would explain what changes in 9 variables. Identify which residue arguments make sense in other dimensions and where the proof first needs the classification of 9-variable cube functions. Moving the two-class elimination into the main text, or outlining its two models immediately after Theorem 3, would give the reader a better view of that dependence.

In the historical discussion, consider citing Langevin’s work on the covering radius inside $\mathrm{RM}(3,9)$. This also gives an opportunity to explain a distinction a reader might otherwise miss. In your proof the extremal function being ruled out can have arbitrary degree. It is the function extracted from its Walsh residues that has degree at most three.

The classification and the two remaining classes

1   Make Proposition 3 reproducible

On p. 9 the procedure is clear enough to implement. Testing $J(J(P))=P$ on all 349 representatives gives 282, 290, 320, 326, 329 and 349. Adding $C(P)=0$ leaves 282, 290 and 349, as reported. Class 349 is the zero form and is excluded by the quadratic Walsh bound. Please archive the indexed input from [3], give its checksum and indexing convention, and supply a runnable script and expected output. Distinguish the use of the classification theorem [1] from the computation on the particular list [3].

The paragraph following (27) already justifies testing the listed representatives. It changes variables in both functions and reapplies Lemma 5 to the transformed pair. Retain that order of argument. In Lemma 5, spell out why only two disjoint cubics contribute modulo 8 on 6 free variables, and only three contribute modulo 16 on nine. The valuation bound in Lemma 3 supplies both statements.

2   Account for translations in Appendix A

After (42), nine independent linear conditions on 36 quadratic coefficients leave a kernel of dimension 27. The 18 parameters arise only after quotienting by nine translation directions. In the determinant model those directions are the quadratic parts of translates of the determinant, spanned by its cofactors. Show that they complement the row and column quadratics. Give the corresponding rank and complement argument for the Hermitian model after (54), and state the Walsh congruence hypothesis in each normalization.

At the start of Appendix A, recall the hypotheses on $g$ and $T(g)$ under which $T^2(g)$ is defined. Derive (45) and the Hermitian parameter map before (57) from (37)–(39), with one coefficient worked out in each model. Specify the translation and affine adjustment after applying $T$ once, then show why iteration on normalized parameters preserves the fixed-point test. For example, under $g^{\prime}(x)=g(x+u)+v\cdot x+c$, the relevant identity is

\[T^2(g^{\prime})(x)=T^2(g)(x+u)+v\cdot x+c.\]

3   Establish coverage of the final lists

For (51), give the stabilizer action when the first matrix has rank one or two, and use it to obtain the listed choices for the second matrix. For (58), specify the scalar and similarity transformations that preserve the hypotheses of Theorem 3. All ten entries of Table 1 and the four character sums after (61) agree with direct evaluation. They finish the argument once coverage of the lists has been proved.

An alternative after proving normalization is to test all $2^{18}$ parameter choices in each class. Retain those satisfying the congruence and the bound $\|W_g\|_\infty\le48$, check that the second application of $T$ is defined, and test $T^2(g)=g$ on the truth table. An independent enumeration found no such fixed point in either class. Publishing the script and counts at each stage would give a short computational proof of Theorem 3.

Formula corrections and shorter proof details

4   Correct the Hermitian identity on page 18

With $t=\operatorname{tr}(A)$, $s=\operatorname{tr}(\operatorname{cof}(A))$ and $d=\det(A)$, squaring the stated parameter map places the conjugate of $t$ on the quadratic term. Please derive the following corrected version of (57) before separating the trace cases.

\[\bar{t}A^2+(d+1+t\bar{t})A+\bar{s}I=0.\]

The choice $A=\operatorname{diag}(1,1,\omega)$ detects the error. It gives $t=d=\omega$ and $s=1$, satisfies (56), and is fixed by $\Phi^2$. The printed left side of (57) is $\operatorname{diag}(1,1,\omega^2)$, whereas the corrected expression vanishes. The next paragraph on p. 18 already uses the conjugated coefficient.

5   Correct equation 34 on page 12

For $f(0)=1$, Walsh inversion gives $\sum_a W_f(a)=-512$. The middle expression in (34) therefore requires $2^{11}$ in place of $2^{10}$. A direct expansion gives

\[\sum_a(W_f(a)-2)^2=2^{18}-4(-512)+4\cdot512=266240.\]

This yields 56 entries of magnitude 8 and 456 of magnitude 24. The resulting value 10496 still exceeds the upper bound 10368 in Theorem 5 by 128.

6   Clarify the spectral arguments and the lower bound

In Section 2, use the evenness of Walsh coefficients together with Parseval to obtain $\|W_f\|_\infty\ge24$. In Section 5, note that every linear function on 9 variables has even weight, so adding it preserves the parity of the weight of $f$. Hence all Walsh coefficients have the same residue modulo 4, which must be 2 when a coefficient has magnitude 26.

For (17), equality in the sum of the absolute values forces $(-1)^{f(x)}W_g(x)=-|W_g(x)|$ term by term. In Proposition 2 cite item 3 of Lemma 3 explicitly. The integer multilinear coefficients of $k-q$ are even by finite differences. Dividing them by two and reducing modulo 2 gives the degree bound for $r$ in (19). In (60)–(61), identify $\epsilon_i=Y_{ii}$ so that the reader can reconstruct the summation domain from the specified frequency.

In the abstract, say that a hypothetical function of nonlinearity 244 would force equality in the cubic norm bound. After Theorem 1, identify a specific witness in [11] that attains 242. Its maximum absolute Walsh coefficient is 28, giving $256-28/2=242$. This separates the established construction from your new upper bound. In Section 6, distinguish the unbalanced witnesses in the cited constructions from the question of existence of a balanced extremizer.

In my opinion, the authors should strengthen the discussion of existing work on the nonlinearity of Boolean functions and the covering radii of Reed–Muller codes. Relevant results established by other researchers should be carefully reviewed, explicitly cited, and used as the foundation for the present argument. In particular, the manuscript should explain how known weight-divisibility results, Walsh-spectrum constraints, and earlier covering-radius methods contribute to the proof. This would help streamline the exposition and identify the new ideas introduced in this paper.

For example, the proof of Lemma 3 can be shortened by invoking the classical Reed–Muller weight-divisibility theorem, as recalled in Carlet and Solé, Theorem 1. Applying this theorem to the restrictions appearing in equation (2) gives the coefficient divisibility in equation (5), from which all the stated congruence properties follow. This would clarify the dependence on established results and allow the exposition to focus on the reciprocal residue conditions and the elimination of the two remaining cubic classes.

Judgements on the six assessment questions

1   Evidence for the finite computation

My assessment is that the current presentation needs a reproducibility supplement before I would recommend acceptance at JCTA. The enumeration itself is small and well specified. Proposition 3 describes an algorithm that can be implemented from (23) and (24), and independent implementations reproduce both survivor lists. I therefore regard this as a limited, repairable documentation issue. The dependence on the established classification theorem [1] is mathematically more substantial than evaluating the two maps on 349 inputs.

For publication, I would request an archived copy of the indexed list [3], a short script, the full output and one execution command. A human-checkable certificate could serve the same purpose. This is my judgement of what the proof needs for reliable verification. It also applies to a submission to Designs, Codes and Cryptography. Independent computations undertaken during review increase confidence but should be accompanied by material that subsequent readers can inspect.

2   Status of the proof in Appendix A

As written, I regard Appendix A as a substantive proof sketch with essential steps still to be supplied. Equations (37)–(39) give enough information to reconstruct the coefficient calculations, and exact computations support (45) and the Hermitian parameter map after the necessary normalization. A referee can recover these claims with additional algebra and computation. The manuscript should itself explain that recovery, because these maps connect the Walsh argument to every later matrix restriction.

The required additions are the translation and affine corrections after one application of $T$, the justification for iterating the induced parameter map, and the exhaustive reduction to (51) and (58). Equation (57) also needs the correction given above. These are localized gaps in the supplied proof of Theorem 3. The numerical checks support the theorem and indicate how to complete the argument.

3   Exhaustiveness of the normalization and final lists

The normalization to 18 parameters in each model is supported by an exact rank calculation. Exhaustiveness of the stabilizer lists remains insufficiently demonstrated in the manuscript. In both models, the nine congruence conditions have rank 9 on the 36 quadratic coefficients. Their kernel has dimension 27. The translation space has dimension 9, the displayed parameter space has dimension 18, and their sum has dimension 27. This establishes coverage at the normalization stage once the invariance of the relevant hypotheses is stated.

The computations already performed check all ten sums in Table 1, all four Hermitian sums, and all $2^{18}$ normalized parameters in each class. They support the exclusion asserted in Theorem 3. They do not by themselves establish the proposed stabilizer orbit decompositions. To claim that (52) and (62) follow from the short lists, the authors should give the actions and show that every admissible parameter reaches one of the listed forms. The exhaustive test described above supplies an alternative endpoint that avoids relying on those unproved orbit reductions.

Orbit reduction novelty and scope

4   Validity of testing orbit representatives

Yes. The condition is an invariant of the full linear orbit, and testing the listed representatives is justified. Let $\rho_A P=[P(Ax)]_3$ denote the cubic part after Boolean reduction. The two covariance identities are

\[J(\rho_A P)=\rho_{A^{-T}}J(P),\]

\[J^2(\rho_A P)=\rho_A J^2(P).\]

They hold for every cubic form, including forms with $C(P)\ne0$. One proof writes $J$ as the complement map applied to the sum of wedge products of unordered pairs of cubic monomials. This quadratic construction commutes with each elementary linear substitution. The complement map changes the action to the dual action, and a second application returns to the original action. Thus the fixed-point condition is orbit invariant. The paragraph after (27) already gives a sufficient proof-specific justification by transforming both functions and reapplying Lemma 5. I would treat this question as resolved, with an optional short covariance lemma for clarity.

5   Identification of the methodological contribution

The introduction identifies the outline of the method, but does not explain its novelty relative to [6], [8] and [17] adequately. Those references concern different covering-radius problems. Merely citing their numerical conclusions leaves the reader to determine which parts of their methods are being reused and which obstruction is overcome here.

The clearest contribution to emphasize is the chain from sharp cubic Walsh bounds, through the reciprocal residue operation and the constraints in (25), to two determinant models. The authors should compare the mechanisms of [6], [8] and [17] with those steps, and identify the precise new lemma or combination of ideas. The comparison with Hou, Sabo and Slaughter is especially important because that paper shares the initial reduction and the treatment of nonlinearity 243. It makes the two-class structural reduction and its algebraic endpoint the most distinctive part of the present proof.

6   Scope beyond 9 variables and publication judgement

Some ingredients are general, while the complete proof is presently specific to 9 variables. Lemma 3 begins with a divisibility statement for arbitrary $m$, and Walsh residue and equality arguments can be studied more broadly. The decisive classification step uses exactly 349 9-variable cubic orbits. The closure in (23) is also dimension sensitive. Removing two disjoint cubic supports from nine coordinates leaves a cubic support. The same complement construction in $m$ coordinates would have size $m-6$.

The paper therefore establishes no automatic extension to larger odd dimensions. I would value it as a substantial solution of a concrete covering-radius problem with a structural refinement of the proof. A demonstrated extension would strengthen a claim to a broadly applicable new method, but is not required to make the theorem worthwhile. After the proof details and reproducibility material are supplied, I recommend submission to Designs, Codes and Cryptography, whose subject area and readership fit the work. The present recommendation is to revise before submission.

Competing Interests

There is no conflict of interest disclosed by the reviewer.