🔢 mathematics

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

This paper computes the complete weight distribution of the third-order Reed-Muller code RM(3,11) by analyzing coset weight enumerators across all GL(10,2)-orbits of Boolean cubic forms, a process that simultaneously establishes a new lower bound of 408 for the covering radius of RM(2,10) and improves the upper bound for the relative covering radius of RM(6,10) in RM(7,10) to 32.

Original authors: Kirill Khoruzhii, Patrick Gelß, Sebastian Pokutta

Published 2026-07-03

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Kirill Khoruzhii, Patrick Gelß, Sebastian Pokutta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to organize a massive library of secret codes. In the world of mathematics and computer science, these codes are called Reed–Muller codes. They are like special sets of instructions used to send messages clearly, even if some parts get scrambled during transmission.

This paper is about solving a specific, incredibly difficult puzzle: figuring out the exact "weight distribution" of a third-order code with a length of 2,048.

Here is the breakdown of what the authors did, using simple analogies:

1. The Goal: Counting the "Heavy" and "Light" Codes

Think of every code as a string of 2,048 light switches (on or off).

The weight of a code is simply how many switches are "on."
The weight distribution is a giant list that tells you exactly how many codes have 1 switch on, how many have 256 on, how many have 512 on, and so on.

For small libraries, mathematicians already had the answer. But for this specific, huge library (length 2,048), the list was missing. The authors wanted to write down the complete catalog.

2. The Problem: Too Many Combinations

To solve this, they had to look at billions of variations of these codes. It's like trying to taste every single possible flavor combination in a giant ice cream shop to see which one is the "sweetest" or "heaviest."

The shop had 3.69 million distinct "flavor families" (mathematicians call these orbits). If they tried to taste every single variation within every family, the task would take longer than the age of the universe. It was computationally impossible.

3. The Breakthrough: The "Shortcut" Rule

The authors found a clever shortcut, which they call a structural theorem.

Imagine you are trying to find the heaviest suitcase in a warehouse. Usually, you'd have to open every single suitcase. But the authors discovered a rule:

"For almost every type of suitcase, you can look at just one specific side of it (a 'hyperplane restriction') to know what the whole thing is like. You only have to do the full, slow inspection for one very weird, rare type of suitcase."

This rule allowed them to skip 99.9% of the heavy lifting. Instead of checking billions of variations, they only had to check a manageable number. This turned an impossible task into one that took about 65 years of computer time (which is still huge, but doable with modern supercomputers).

4. The Results: The New Record

After running their shortcut on all 3.69 million families, they finally assembled the complete list (the weight distribution).

But they found something even more interesting while doing it:

The "Hardest" Code: They were looking for the code that is furthest away from being a simple, easy code. In math terms, they wanted the "second-order nonlinearity."
The Old Record: The best known "distance" was 400.
The New Record: They found 179 specific code families that are actually 408 units away.

This is a big deal because it pushes the known limit of how "complex" these codes can get. It's like finding a new record for the highest jump in the Olympics.

5. The Side Quest: A Faster Way to Guess

The main calculation took a long time. So, the authors also built a "smart guesser" (a heuristic search).

Instead of tasting every ice cream flavor, this guesser takes a quick bite, sees if it's close to the target, and adjusts.
It found the same answer (408) but did it 1,000 times faster.
They used this fast guesser to solve a similar, even harder puzzle (involving 7th-degree codes) and improved that record too, lowering the "distance" from 50 to 32.

Summary

In short, the authors:

Mapped a massive, uncharted territory of mathematical codes (length 2,048).
Found a shortcut that made the mapping possible.
Discovered a new record for how complex these codes can be (raising the limit from 400 to 408).
Created a faster tool that can find these records quickly for future puzzles.

They didn't invent a new medicine or a new engine; they solved a pure math puzzle that helps us understand the fundamental limits of error-correcting codes.

Technical Summary: The Weight Distribution of the Third-Order Reed–Muller Code of Length 2048

Problem Statement
The weight distributions of Reed–Muller codes $RM(r, m)$ are a classical problem in coding theory, yet closed-form solutions are known only for orders $r \leqslant 2$ and their duals $r \geqslant m-3$ . For third-order codes ( $r=3$ ), complete distributions have been established only through individual computations for lengths up to 1024 ($RM(3, 10)$). This paper addresses the computation of the weight distribution for the next step in this chain: the third-order Reed–Muller code $RM(3, 11)$ of length 2048. A secondary objective is to determine the second-order nonlinearity $d_2(f)$ for all cubic forms in ten variables, thereby establishing the relative covering radius $\rho_{2,3}(10)$ of $RM(2, 10)$ within $RM(3, 10)$.

Methodology
The computation relies on the Sarwate-type recursion, which expresses the weight enumerator of $RM(3, m+1)$ as a sum of squared coset weight enumerators of $f + RM(2, m)$ over all cubic forms $f$ . Since the coset enumerator depends only on the $GL(m, 2)$-orbit of $f$ , the sum reduces to orbit representatives weighted by orbit sizes.

The primary bottleneck for $m=10$ is the sheer number of orbits (3,691,560 nonzero orbits) and the cost of evaluating a single coset enumerator. The standard split formula by Brier and Langevin requires an outer enumeration over $2^{36}$ homogeneous quadratic forms for $m=10$ , which is computationally infeasible for a full catalog pass.

To overcome this, the authors employ a structural theorem (Theorem 1): every nondegenerate Boolean cubic form admits a nondegenerate hyperplane restriction, with the exception of a single orbit in each odd dimension. For $m=10$ (an even dimension), this theorem guarantees that every nondegenerate orbit has a restriction to a hyperplane that is also nondegenerate. This allows the coset enumerator to be computed via a quotient space of size $2^{26}$ rather than $2^{36}$ , saving a factor of $2^{10}$ per orbit.

The evaluation of the coset weight enumerators is performed using fast Walsh–Hadamard transforms on the resulting affine cosets. The entire catalog pass required approximately 65 CPU-years. To verify the tightness of the results and improve efficiency for upper bounds, a local-search heuristic (combining greedy descent, $\tau$ -moves, iterated local search, and beam search) was developed. This heuristic finds explicit quadratic corrections $q$ minimizing $wt(f+q)$, providing certificates for the covering radius at a fraction of the cost of the full enumeration.

Key Contributions and Results

Weight Distribution of $RM(3, 11)$:
The paper presents the complete weight distribution of $RM(3, 11)$ (Table 1). This result is assembled by summing the squared coset weight enumerators of all 3,691,560 nonzero $GL(10, 2)$-orbits of Boolean cubic forms in ten variables, plus the contribution from the zero orbit.
Second-Order Nonlinearity and Relative Covering Radius:
The lowest nonzero exponent of each coset enumerator corresponds to the second-order nonlinearity $d_2(f)$ . The computation determines that the maximum value of $d_2(f)$ over all cubic forms in ten variables is 408.
- Theorem 3: The relative covering radius $\rho_{2,3}(10)$ of $RM(2, 10)$ in $RM(3, 10)$ is exactly 408.
- This maximum is attained on 179 distinct orbits. The representatives of these orbits and their "kissing numbers" (the count of quadratic forms achieving the minimum weight) are listed in Table 2.
- All 179 extremal forms are nondegenerate.
Improved Lower Bound on Covering Radius:
The result raises the best known lower bound on the covering radius of $RM(2, 10)$ from 400 to 408. The 179 orbits serve as explicit witnesses for this bound.
Connection to Alternating Rank:
The paper establishes a relationship between $d_2(f)$ and the alternating rank ($arank$) of a cubic form. Using a derived bound (Theorem 4), the authors show that for any form with $d_2(f) = 408$ , the alternating rank must be at least 6. In $m=10$ , the maximum alternating rank is 7. The analysis reveals that 177 of the 179 extremal orbits have $arank = 7$, while 2 have $arank = 6$. This contrasts with lower dimensions ( $m \leqslant 9$ ), where the extremal forms were forced to have the maximum possible alternating rank for that dimension.
Heuristic Search and Cocubic Bounds:
The local-search heuristic successfully reproduced the bound $\rho_{2,3}(10) \leqslant 408$ at roughly one-thousandth of the cost of the full enumeration. Applied to degree-seven forms, this heuristic improved the upper bound on the relative covering radius of $RM(6, 10)$ in $RM(7, 10)$ from 50 to 32 (Lemma 2).

Significance
The paper claims significance primarily in resolving the weight distribution for $RM(3, 11)$, extending the known chain of third-order codes. The structural theorem regarding nondegenerate hyperplane restrictions is presented as a critical enabler, making the full catalog pass feasible where previous methods were "out of reach."

The determination of $\rho_{2,3}(10) = 408$ is significant for the covering radius literature, updating the best known lower bound for $RM(2, 10)$. Furthermore, the analysis of the extremal orbits provides structural insights: the shift from monomial trace forms (which previously held the record at 400) to binomial trace polynomials and the concentration of extremal forms at maximal alternating rank suggest new directions for searching high-nonlinearity forms in higher dimensions ( $m > 10$ ). The authors note that the enumeration data and reference code are made available to facilitate further research in coding theory and Boolean function analysis.