🔢 mathematics

On the Distance Distribution of Reed-Muller Codes

This paper establishes error bounds for the distance distribution of Reed-Muller codes over large finite fields by employing a character sum method to solve the problem of counting multivariate polynomials with prescribed properties, thereby addressing a long-standing open problem regarding coset weight distributions proposed in MacWilliams and Sloane's 1977 textbook.

Original authors: Neil Kolekar

Published 2026-01-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Neil Kolekar

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

The Big Picture: The "Lost Message" Problem

Imagine you are sending a secret message using a special code (a Reed-Muller code). This code is like a giant grid of numbers. To send a message, you pick a specific pattern from this grid.

However, sometimes the message gets garbled during transmission. It arrives with some errors. You, the receiver, get a messy version of the message. Your job is to figure out: "How many valid, clean patterns are exactly this far away from my messy message?"

This is called the Distance Distribution Problem.

If the messy message is actually a valid pattern (just with a few typos), you are counting how many other valid patterns are close to it. This is the Weight Distribution.
If the messy message is not a valid pattern at all (it's a "coset"), you are counting how many valid patterns are close to this "imposter." This is the Coset Weight Distribution.

The Problem: For most codes, figuring out exactly how many patterns are at a specific distance is incredibly hard. It's like trying to count how many specific types of snowflakes exist in a blizzard without a microscope. This paper focuses on a specific type of code (Reed-Muller) and tries to give a very accurate estimate of these counts, especially when the "messy message" isn't a valid pattern.

The Core Idea: Counting Polynomials

The paper translates this coding problem into a math problem about polynomials (equations with variables like $x, y, z$ ).

Think of a polynomial as a recipe for a cake.

The ingredients are the coefficients (numbers).
The shape is determined by the variables ( $x, y, z$ ).
The zeroes are the specific points where the cake "collapses" or equals zero.

The question becomes: "How many different cake recipes can I make that have a specific shape, use specific ingredients, and collapse (equal zero) at exactly $S$ specific points?"

The Solution: The "Character Sum" Method

The author, Neil Kolekar, uses a technique called the Character Sum Method. Here is an analogy for how this works:

Imagine you are trying to count how many people in a huge crowd are wearing red hats, but you can't see them directly. Instead, you have a special "hat detector" (a character).

If a person is wearing a red hat, the detector beeps loudly.
If they aren't, it stays silent.

In math, these "detectors" are called characters. They are special functions that help us filter through millions of possibilities.

Additive Characters: These detect patterns based on addition (like checking if numbers sum up to a certain value).
Multiplicative Characters: These detect patterns based on multiplication.

The paper's breakthrough is combining these two types of detectors. The author realized that the "recipes" (polynomials) we are looking for have a structure that is easy to see with multiplication but hard to see with addition. By using both detectors together, he can filter out the noise and get a much clearer picture of the count.

The Main Achievement: Error Bounds

The paper doesn't just give a single number; it gives a range with a guarantee.

Think of it like a weather forecast. Instead of saying "It will rain exactly 1.2 inches," the paper says: "It will rain between 1.1 and 1.3 inches, and we are 99% sure the error is no more than 0.05 inches."

The Goal: Calculate the number of polynomials with specific zeroes.
The Result: The author provides a formula that predicts this number.
The "Error Bound": He proves that the difference between his prediction and the actual number is very small. He calculates exactly how small this error can be.

This is a big deal because, for decades, mathematicians have struggled to get these "error bounds" for Reed-Muller codes when the message is a "coset" (an invalid pattern). This paper is the first systematic attempt to solve this for a wide range of these codes over large fields.

How They Did It (The Toolkit)

To get these precise bounds, the author had to build a new mathematical toolkit:

Lagrange Interpolation (The "Fingerprint"): He used a method to describe exactly which polynomials vanish (become zero) at specific points. It's like creating a unique fingerprint for every possible set of zeroes.
Truncated Rings (The "Box"): He put these polynomials into a mathematical "box" (a quotient ring) that limits how complex the recipes can get. This makes the counting manageable.
Gauss Sums (The "Scale"): He used a specific type of sum (Gauss sums) to weigh the importance of different patterns. He had to figure out exactly how heavy these weights are in his specific "box."
The Li-Wan Sieve (The "Filter"): Finally, he used a powerful filtering tool (the Li-Wan sieve) to remove duplicates and over-counting. Imagine sifting sand to find gold; this sieve ensures he only counts the unique, valid patterns and ignores the noise.

Why This Matters (According to the Paper)

The paper claims to solve a problem that has been open since 1977 (mentioned in a famous textbook by MacWilliams and Sloane).

Previous attempts worked well for simple codes (Reed-Solomon) but failed for the more complex Reed-Muller codes.
This paper extends the success of the simple codes to the complex ones.
The Method: It creates a "unified framework." This means the same mathematical tools used here could potentially be used to solve other similar counting problems involving polynomials and finite fields, not just this specific coding problem.

Summary in One Sentence

Neil Kolekar developed a new mathematical "sieve" that uses special detectors (characters) to accurately count how many complex mathematical recipes (polynomials) exist with specific properties, providing a highly accurate estimate with a guaranteed margin of error for a major class of error-correcting codes.

Technical Summary: On the Distance Distribution of Reed-Muller Codes

Problem Statement
The paper addresses the distance distribution problem for Reed-Muller codes, specifically focusing on the coset weight distribution problem. Given a received word $u$ (which may not be a codeword) and an integer $k$ , the objective is to compute the number of codewords $w$ in the Reed-Muller code $RM_q(d, v)$ such that the Hamming distance between $u$ and $w$ is exactly $k$ .

While the weight distribution problem (where $u$ is a codeword) has seen recent progress via combinatorial methods, the coset weight distribution problem has remained largely open since its proposal in MacWilliams and Sloane's 1977 textbook. The paper reformulates this coding theory problem into a polynomial enumeration problem over finite fields: counting the number of multivariate polynomials $f$ with prescribed degree constraints and coefficients such that the difference $f - g$ (where $g$ is a fixed polynomial) has a specific number of zeroes in $\mathbb{F}_q^v$ .

Methodology
The author employs a character sum method, extending the approach previously used by Li and Wan for Reed-Solomon codes to the multivariate setting. The methodology proceeds through several technical stages:

Lagrange Interpolation and Character Sums:
The set of polynomials vanishing on a specific set of points $Z$ is characterized using Lagrange interpolation polynomials $P_v(x) = \prod_{i=1}^v (1 - (x_i - v_i)^{q-1})$ . This allows the count of polynomials with a specific reduction in a quotient ring $E$ to be expressed as a character sum involving both additive and multiplicative characters over a truncated polynomial quotient ring.
Quotient Ring Structure:
The analysis is conducted over the ring $E = \mathbb{F}_q[x_1, \dots, x_v] / \langle x_1^{i_1} \dots x_v^{i_v} \mid \sum i_j = \ell \rangle$ . The paper investigates the algebraic properties of this ring, specifically the structure of ideals $K_\psi$ associated with additive characters $\psi$ . It is shown that $K_\psi$ is the unique ideal maximally contained in the kernel of $\psi$ .
Gauss Sum Evaluation:
The magnitude of the error term depends on the size of Gauss sums $G(\chi, \psi)$ over this ring. The paper derives an exact formula for $|G(\chi, \psi)|^2$ , linking it to the size of the ideal $K_\psi$ and the condition that the multiplicative character $\chi$ is trivial on $1 + K_\psi$ .
Enumerative Combinatorics:
To bound the error, the paper performs two key enumerations:
- Ideals: It characterizes ideals $I$ with $\dim(\text{Soc}(R/I)) = 1$ and provides an upper bound on the distribution of their codimensions, relating them to generalized Hankel matrices.
- Characters: It analyzes the distribution of multiplicative characters, proving that products of random characters satisfying certain constraints exhibit a "uniform distribution" property, which simplifies the estimation of character sums.
Li-Wan Sieve:
The final error bound is derived using the Li-Wan coordinate-sieve formula, a refinement of the inclusion-exclusion principle. This allows the summation over permutations to be bounded efficiently by grouping terms based on cycle structures.

Key Results
The main result is Theorem 1.3, which provides an explicit error bound for $N_k(d, g)$ , the number of polynomials $f$ satisfying the degree and zero-count constraints. The theorem states that the deviation of $N_k(d, g)$ from its expected value (the center of approximation) is bounded by:

$\left| N_k(d, g) - \binom{(q-1)q^{v-1}}{k} q^{k-E-qv-1+1} \right| \le \binom{v q^2 q^{\binom{\ell+v-3}{v-1}} + k - 1}{k - 1} q^k \left( \binom{\lceil \ell/2 \rceil + v}{v} + 1 \right) - E$

where $E$ is the number of exponent tuples summing to at most $\ell-1$ . The bound relies on parameters $q_1$ and $q_2$ derived from the Weil bound and properties of the characteristic $p$ .

Significance and Claims
The paper claims to make the first systematic attempt to study the coset weight distribution problem for Reed-Muller codes of fixed degree over large finite fields. Its significance lies in:

Unification: It provides a unified framework applicable to a broad class of polynomial enumeration problems over finite fields involving prescribed evaluation vectors.
Extension: It successfully extends the character sum techniques from Reed-Solomon codes (univariate) to the multivariate Reed-Muller setting.
Algebraic Insight: The technical work regarding the algebraic properties of the truncated polynomial quotient rings and the enumeration of their ideals is presented as potentially useful beyond the immediate scope of distance distribution.

The author notes that while the weight distribution problem for Reed-Muller codes was recently resolved using higher-order Fourier analysis, this work addresses the more difficult coset problem using algebraic and analytic number theory tools. The paper concludes by suggesting future directions, including generalizing the results to different quotient rings and handling evaluation sets $D$ that deviate significantly from $\mathbb{F}_q^v$ .