pith. sign in

arxiv: 2607.02365 · v1 · pith:O53JULYTnew · submitted 2026-07-02 · 💻 cs.IT · math.IT

The Weight Distribution of the Third-Order Reed-Muller Code of Length 2048

Kirill Khoruzhii , Patrick Gel\ss , Sebastian Pokutta This is my paper

Pith reviewed 2026-07-03 04:44 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords reed-muller codesweight distributioncubic boolean formscovering radiusGL(10,2) orbitsnonlinearity
0
0 comments X

The pith

The weight distribution of the Reed-Muller code RM(3,11) of length 2048 is now known exactly.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper computes the full weight distribution of the third-order Reed-Muller code RM(3,11) with length 2048. The computation enumerates the coset weight enumerators for representatives of all 3,691,560 nonzero orbits of cubic Boolean forms under the action of GL(10,2). A key structural result enables this by showing that nondegenerate cubic forms have nondegenerate restrictions to hyperplanes except in one exceptional orbit per odd dimension. The same work determines that the relative covering radius of RM(2,10) inside RM(3,10) is exactly 408, attained by 179 orbits, improving the previous lower bound of 400. A heuristic also shows the relative covering radius of RM(6,10) in RM(7,10) is at most 32.

Core claim

We compute the weight distribution of RM(3,11) by assembling the coset weight enumerators of f + RM(2,10) evaluated for representatives of all 3691560 nonzero GL(10,2)-orbits of Boolean cubic forms in ten variables. This rests on the structural theorem that a nondegenerate Boolean cubic form admits a nondegenerate hyperplane restriction, except for a single orbit in each odd dimension. The computation also yields the second-order nonlinearity of every cubic form and raises the best known lower bound on the covering radius of RM(2,10) from 400 to 408.

What carries the argument

The GL(10,2)-orbits of Boolean cubic forms in ten variables and the associated coset weight enumerators of f + RM(2,10).

If this is right

  • The exact weight distribution of RM(3,11) is determined.
  • The second-order nonlinearity of all cubic forms in 10 variables is known.
  • The lower bound on the covering radius of RM(2,10) is raised to 408.
  • An upper bound of 32 is established for the relative covering radius of RM(6,10) in RM(7,10).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The enumeration technique could extend to weight distributions of higher-order Reed-Muller codes.
  • Improved covering radius bounds may inform the design of decoding algorithms for Reed-Muller codes.
  • The weight distribution enables exact computation of other code parameters such as the minimum distance of the dual code.

Load-bearing premise

A nondegenerate Boolean cubic form admits a nondegenerate hyperplane restriction, except for a single orbit in each odd dimension.

What would settle it

A counterexample to the structural theorem, such as a nondegenerate cubic form in odd dimension without nondegenerate hyperplane restriction, or an independent computation showing a different weight count for RM(3,11).

Figures

Figures reproduced from arXiv: 2607.02365 by Kirill Khoruzhii, Patrick Gel\ss, Sebastian Pokutta.

Figure 1
Figure 1. Figure 1: Reed–Muller structure and heuristic search. a) Generator matrix of RM(3, m), with the subcodes highlighted. b) Calibration of the upper-bound heuristic on a hard sample of 104 catalog representatives. An instance is unresolved if the best correction found has weight greater than 400. to the value giving the smaller wt(f + q). The effec￾tive search space is thus F 55 2 , indexed by the linear and quadratic … view at source ↗
read the original abstract

We compute the weight distribution of the third-order Reed--Muller code RM(3,11) of length 2048. The weight enumerator is assembled from the coset weight enumerators of f+RM(2,10), evaluated for representatives of all 3691560 nonzero GL(10,2)-orbits of Boolean cubic forms in ten variables. The computation rests on a structural theorem: a nondegenerate Boolean cubic form admits a nondegenerate hyperplane restriction, except for a single orbit in each odd dimension. The same pass determines the second-order nonlinearity of every cubic form: the relative covering radius of RM(2,10) in RM(3,10) is 408, attained on 179 orbits. This raises the best known lower bound on the covering radius of RM(2,10) from 400 to 408. A complementary heuristic search shows that the relative covering radius of RM(6,10) in RM(7,10) is at most 32, improving the previous bound of 50.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper computes the weight distribution of the third-order Reed-Muller code RM(3,11) of length 2048. The weight enumerator is assembled from the coset weight enumerators of f+RM(2,10), evaluated for representatives of all 3691560 nonzero GL(10,2)-orbits of Boolean cubic forms in ten variables. The computation rests on a structural theorem: a nondegenerate Boolean cubic form admits a nondegenerate hyperplane restriction, except for a single orbit in each odd dimension. The same pass determines the second-order nonlinearity of every cubic form: the relative covering radius of RM(2,10) in RM(3,10) is 408, attained on 179 orbits. This raises the best known lower bound on the covering radius of RM(2,10) from 400 to 408. A complementary heuristic search shows that the relative covering radius of RM(6,10) in RM(7,10) is at most 32, improving the previous bound of 50.

Significance. If the structural theorem holds and the orbit enumeration is correctly implemented, this is a substantial computational result in coding theory: the exact weight distribution of RM(3,11) and improved covering-radius bounds for RM(2,10) and RM(6,10). The scale of the enumeration (over 3.6 million orbits) combined with the use of a structural reduction is noteworthy.

major comments (1)
  1. [Abstract] Abstract (structural theorem): the claim that every nondegenerate cubic form in 10 variables admits a nondegenerate hyperplane restriction is load-bearing for the entire weight-distribution assembly. The manuscript states the theorem but supplies no proof, no computational verification protocol, and no error-checking details for the even-dimensional case; a single counterexample orbit would invalidate the chosen representatives and the recursive coset-enumerator evaluation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful review and for recognizing the scale and significance of the computation. We respond to the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (structural theorem): the claim that every nondegenerate cubic form in 10 variables admits a nondegenerate hyperplane restriction is load-bearing for the entire weight-distribution assembly. The manuscript states the theorem but supplies no proof, no computational verification protocol, and no error-checking details for the even-dimensional case; a single counterexample orbit would invalidate the chosen representatives and the recursive coset-enumerator evaluation.

    Authors: We agree that the structural theorem is load-bearing and that its presentation in the manuscript is insufficient. The theorem states that every nondegenerate cubic form in even dimension (including 10) admits a nondegenerate hyperplane restriction, with the single exceptional orbit occurring only in each odd dimension. The manuscript states the result but does not contain a proof or the requested verification details. In the revised version we will add: (1) a self-contained proof of the theorem, (2) a description of the computational verification protocol that was used to confirm the property on all 3,691,560 orbits, and (3) explicit error-checking procedures applied to the even-dimensional case. These additions will directly address the concern that a counterexample would invalidate the representatives and the recursive assembly. revision: yes

Circularity Check

0 steps flagged

No circularity: weight distribution computed from independent structural theorem on cubic forms

full rationale

The paper assembles the RM(3,11) weight enumerator from coset enumerators over GL(10,2)-orbits of cubic forms, explicitly resting on the stated structural theorem about nondegenerate hyperplane restrictions. No quoted step shows self-definition (theorem not defined via the enumerator), fitted inputs renamed as predictions, or load-bearing self-citations that reduce the result to prior author work by construction. The theorem functions as an external premise enabling enumeration rather than being derived from the output distribution. This matches the default non-circular case for a direct computational result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the validity of the stated structural theorem and the assumption that the orbit representatives are correctly classified and enumerated.

axioms (1)
  • domain assumption A nondegenerate Boolean cubic form admits a nondegenerate hyperplane restriction, except for a single orbit in each odd dimension.
    This theorem is invoked to assemble the weight enumerator from coset enumerators.

pith-pipeline@v0.9.1-grok · 5720 in / 1421 out tokens · 53434 ms · 2026-07-03T04:44:45.311706+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references

  1. [1]

    E. Abbe, A. Shpilka, and M. Ye. Reed–Muller codes: Theory and algorithms.IEEE Transactions on Informa- tion Theory, 67(6):3251–3277, June 2021

    2021

  2. [2]

    Amy and M

    M. Amy and M. Mosca. T-count optimization and reed–muller codes.IEEE Transactions on Information Theory, 65(8):4771–4784, 2019

    2019

  3. [3]

    Brier and P

    E. Brier and P. Langevin. Classification of boolean cubic forms of nine variables. InProceedings 2003 IEEE In- formation Theory Workshop (Cat. No.03EX674), pages 179–182, 2003

    2003

  4. [4]

    Dougherty, R

    R. Dougherty, R. D. Mauldin, and M. Tiefenbruck. The covering radius of the Reed–Muller code RM(m - 4, m) in RM(m - 3, m).IEEE Transactions on Information Theory, 68(1):560–571, Jan. 2022

    2022

  5. [5]

    Fourquet and C

    R. Fourquet and C. Tavernier. An improved list decod- ing algorithm for the second order Reed–Muller codes and its applications.Designs, Codes and Cryptography, 49(1):323–340, Dec. 2008

    2008

  6. [6]

    J. Gao. Numerical results and asymptotic lower bound on the covering radius of reed-muller codes rm(2,11) and rm(3,n).IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E109.A(1):35–46, 2026

    2026

  7. [7]

    Gillot and P

    V. Gillot and P. Langevin. Classification of some cosets of the Reed–Muller code.Cryptography and Communica- tions, 15(6):1129–1137, Nov. 2023

    2023

  8. [8]

    Hora and P

    J. Hora and P. Pudlák. Classification of 9-dimensional trilinear alternating forms over GF(2).Finite Fields and Their Applications, 70:101788, Feb. 2021

    2021

  9. [9]

    X.-D. Hou. Some results on the covering radii of Reed– Mullercodes.IEEE Transactions on Information Theory, 39(2):366–378, Mar. 1993

    1993

  10. [10]

    X.-d. Hou. GL(m, 2) acting onR(r, m)/R(r−1, m).Dis- crete Mathematics, 149(1):99–122, Feb. 1996

    1996

  11. [11]

    Kasami and N

    T. Kasami and N. Tokura. On the weight structure of Reed–Muller codes.IEEE Transactions on Information Theory, 16(6):752–759, Nov. 1970

    1970

  12. [12]

    Khoruzhii, P

    K. Khoruzhii, P. Gelß, and S. Pokutta. BCF10: Boolean cubic forms in ten variables, 2026

    2026

  13. [13]

    Khoruzhii, P

    K. Khoruzhii, P. Gelß, and S. Pokutta. Classification of boolean cubic forms in ten variables, 2026

    2026

  14. [14]

    Khoruzhii, P

    K. Khoruzhii, P. Gelß, and S. Pokutta. Tensor decompo- sition for non-Clifford gate minimization, Feb. 2026

    2026

  15. [15]

    Markov and Y

    M. Markov and Y. Borissov. The weight distribution of the fourth-order Reed–Muller code of length 512.De- signs, Codes and Cryptography, 93(7):2487–2502, July 2025

    2025

  16. [16]

    D. E. Muller. Application of boolean algebra to switching circuit design and to error detection.Transactions of the I.R.E. Professional Group on Electronic Computers, EC- 3(3):6–12, 1954

    1954

  17. [17]

    I. Reed. A class of multiple-error-correcting codes and the decoding scheme.Transactions of the IRE Professional Group on Information Theory, 4(4):38–49, 1954

    1954

  18. [18]

    D. V. Sarwate.Weight Enumeration of Reed–Muller Codes and Cosets. Ph.D. thesis, Princeton University, Princeton, NJ, Sept. 1973

    1973

  19. [19]

    J. Schatz. The second order reed-muller code of length 64 has covering radius 18 (corresp.).IEEE Transactions on Information Theory, 27(4):529–530, 1981

    1981

  20. [20]

    Sloane and E

    N. Sloane and E. Berlekamp. Weight enumerator for second-order Reed–Muller codes.IEEE Transactions on Information Theory, 16(6):745–751, Nov. 1970

    1970

  21. [21]

    Sugino, Y

    M. Sugino, Y. Ienaga, N. Tokura, and T. Kasami. Weight distribution of (128, 64) reed-muller code (corresp.). IEEE Transactions on Information Theory, 17(5):627– 628, 1971

    1971

  22. [22]

    Sugita, T

    T. Sugita, T. Kasami, and T. Fujiwara. The weight distri- bution of the third-order Reed–Muller code of length 512. IEEE Transactions on Information Theory, 42(5):1622– 1625, Sept. 1996

    1996

  23. [23]

    H. C. A. van Tilborg. Weights in the third-order reed- muller codes. JPL Technical Report 32-1526, Vol. IV, Jet Propulsion Laboratory, 1971

    1971

  24. [24]

    Q. Wang. The covering radius of the Reed–Muller code RM(2, 7) is 40.Discrete Mathematics, 342(12):111625, Dec. 2019. 9

    2019