Exact weight spectrum found for Reed–Muller codes breaking conjecture
The Exact Weight Spectrum of $\RM(m-7,m$): A Counterexample to the Carlet-Solé Conjecture
Information Theory
Summary
Finding the exact weight spectrum of certain Boolean functions is important in coding and cryptography. The authors determined the exact spectrum for a specific family of Reed–Muller codes where the degree is seven less than the number of variables. Their results disprove a previously believed conjecture about these weight spectra. They used methods from geometry and Fourier analysis to rule out several potential weights that were thought to exist.
What this means in practice
- •For error correcting code designers: Use the precise weight spectrum of Reed–Muller codes with r = n-7 to optimize decoding strategies and code constructions.
- •For cryptographic protocol developers: Refine security analyses and constructions of cryptographic primitives based on Boolean function properties using the exact weight spectrum found.
Authors
Yueying Lou, Qichun Wang
Abstract
Boolean functions are widely used in cryptography and coding theory. A key challenge lies in finding the weight spectrum for all $n$-variable Boolean functions of degree at most $r$, also known as the Reed--Muller code $\RM(r,n)$. In 2023, Carlet and Solé determined the weight spectra of $\RM(n-c,n)$ for $c=3,4$, and conjectured the weight spectrum of $\RM(n-c, n$) for $n\ge2c$. The weight spectra of $\RM(n-5, n)$ and $\RM(n-6,n)$ were determined by Carlet in 2024 and by Lou and Wang in 2025, respectively, confirming the Carlet-Solé conjecture for the cases $c=5,6$. Very recently, Leuenberger et al. and Wei et al. investigated the weight spectrum of $\RM(7,14)$ independently, and there are eight potential weights which have not been determined. Up until now, the weight spectra of the Reed--Muller codes $RM(r,n)$ are still unknown for $r=3,...,n-7$. In this paper, we determine the exact weight spectrum of $\RM(m-7, m)$ for every $m\ge 14$. By combining affine geometry and Fourier analysis, we exclude the conjectured eight weights for $\RM(7,14)$. We then extend the exclusions to all higher dimensions using a geometric transfer. Consequently, we provide a counterexample to the Carlet-Solé conjecture.