Source-linked AI summary
The Exact Weight Spectrum of $\RM(m-7,m$): A Counterexample to the Carlet-Sol\'{e} Conjecture
Yueying Lou, Qichun Wang
TL;DR
The paper excludes eight conjectured weights in RM(7, 14), determining the exact weight spectrum of RM(m −7, m) for every m ≥14. The paper combines affine geometry and Fourier analysis to exclude the candidate weights in RM(7, 14), then uses a geometric transfer to extend the exclusions to higher dimensions. The exact weight spectrum of RM(m −7, m) is determined for every m ≥14, providing a counterexample to the Carlet–Solé conjecture.
Problem
The paper excludes eight conjectured weights in RM(7, 14), determining the exact weight spectrum of RM(m −7, m) for every m ≥14.
Source: §1 · p. 3Method
The paper combines affine geometry and Fourier analysis to exclude the candidate weights in RM(7, 14), then uses a geometric transfer to extend the exclusions to higher dimensions.
Source: §1 · p. 3Results
The exact weight spectrum of RM(m −7, m) is determined for every m ≥14, providing a counterexample to the Carlet–Solé conjecture.
Source: §1 · p. 3, §5 · p. 15, §6 · p. 16Takeaways & Limitations
The four counterexamples for RM(m−7, m) are below 3·2^7, and the paper proposes a conjecture for the broader RM(n−c, n) spectra.
Source: §6 · p. 16The paper leaves open whether Conjecture 1 holds for RM(n −8, n) when n ≥16.
Source: §6 · p. 16
Abstract
from arXiv · showhide
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\'{e} 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\'{e} 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\'{e} conjecture.
1 Introduction
The paper addresses the open problem of determining Reed–Muller weight spectra near the highest degrees, against a conjecture extending known cases. It determines the spectrum of RM(m−7, m) for m ≥14 by excluding the eight candidate weights in RM(7, 14) and transferring those exclusions to higher dimensions.
1 Introduction
- Before this work, the Carlet–Solé conjecture had been confirmed for c = 3, 4, 5, and 6, while eight potential weights remained unresolved for RM(7, 14) [6] [13] [24].The c = 5 case was determined by Carlet in 2024, and the c = 6 case by Lou and Wang in 2025.Source: §1 · p. 2
- The conjecture specifies a proposed form for the weight spectrum of RM(n −c, n) when n ≥2c, using prescribed low- and high-weight sets and consecutive even integers between them.The sets A and B are tied to earlier classifications, while C consists of consecutive even integers in the stated interval.Source: §1 · p. 2
- Prior work also estimated unknown weight enumerators and determined exact spectra or distributions for several particular Reed–Muller codes [11].The cited work includes RM(4, 10), RM(4, 9), and RM(3, 11).Source: §1 · p. 2
- The paper determines the exact weight spectrum of RM(m −7, m) for every m ≥14, excluding eight conjectured weights in RM(7, 14) and transferring the exclusions to higher dimensions.The proof combines affine geometry and Fourier analysis.Source: §1 · p. 3
- The paper establishes necessary conditions using affine geometry, excludes the eight weights in Section 4, and proves the higher-dimensional result in Section 5.Section 2 provides background; Section 6 concludes.Source: §1 · p. 3
2 Preliminaries
The preliminaries fix the Boolean-function and Reed–Muller-code framework and collect low-weight classifications and a covering result used later. These tools constrain supports and weights in the relevant ranges.
2 Preliminaries
- RM(r, n) consists of truth tables of n-variable Boolean functions of algebraic degree at most r.The functions are maps from the n-dimensional binary vector space to F2, and their truth tables form a binary code.Source: §2 · p. 3
- When an affine section vanishes identically, the ANF factorization gives g(z, t) = t q(z) with deg(q) ≤deg(g) −1.Affine substitutions preserve degree and weight, while restriction to an affine subspace does not increase degree.Source: §2 · pp. 3–4
- For r ≥2, every nonzero word below weight 2^(n−r+1) is affinely equivalent to one of two Kasami–Tokura forms.The minimum positive weight is 2^(n−r), and minimum-weight supports are affine (n−r)-flats.Source: §2 · p. 4
- For n ≥12, weights below 208 in RM(n −6, n) are restricted by the previously established spectrum.The supplied passage gives this as a necessary list derived from that spectrum.Source: §2 · p. 4
- A word q in RM(r, n) with 0 < wt(q) < 2.5·2^(n−r) has support contained in two affine hyperplanes with independent linear parts [12].Its zero set therefore contains an affine (n−2)-flat; the applications here use n−r = 6 and threshold 160.Source: §2 · p. 4
- For m ≥14, the Kasami–Tokura–Azumi low-weight classification specialized to m−r = 7 supplies the weights below 320 used to establish the bottom of the spectrum.The paper uses this classification to establish the bottom portion of the spectrum.Source: §2 · p. 4
3 Affine geometry and some necessary conditions
The section derives geometric constraints on supports of words with the four candidate weights T = {322, 326, 330, 334}. These constraints yield empty affine flats and a weight-64 hyperplane section under a nonempty-hyperplane hypothesis.
3 Affine geometry and some necessary conditions
- For f ∈RM(7, 14) with weight in T, every affine hyperplane meets supp(f).Otherwise f factors as t q with q ∈RM(6, 13), whose weight would be congruent to 2 modulo 4, contrary to the divisibility property.Source: §3 · p. 5
- For the candidate weights T and m ≥14, some affine (m−3)-flat and some affine (m−2)-flat are disjoint from S.The proof of the latter uses bounds on hyperplane-section weights and a quotient-space count based on the empty (m−3)-flat.Source: §3 · pp. 5–6
- The empty (m−3)-flat forces each nonzero coset restriction to have at least 48 support points, implying W ≥336 and contradicting W ≤334.The restrictions have degree at most m−8 in m−3 variables and belong to RM(m−8, m−3).Source: §3 · pp. 4, 6
- For n ≥12 and r = n−6, no three codewords of weights 96, 112, and 126 can have a sum of degree at most r−1.The proof compares affine-factor spaces and degree-r monomials to rule out cancellation of the top-degree terms.Source: §3 · pp. 6, 8
- Proposition 1 assumes every hyperplane meets S; the affine-coordinate representation around an empty (m−2)-flat yields three nonzero sections whose weights sum to W.Those section weights lie in the specified set intersected with [64, 206], enabling the weight-64 conclusion.Source: §3 · p. 8
- If every affine hyperplane meets S, some affine hyperplane has intersection weight 64.The proof uses an empty (m−2)-flat and rules out the remaining possible section weights using the exclusion of a degree-lowered sum of weights 96, 112, and 126.Source: §3 · p. 8
4 Exclusion of the eight weights in RM(7, 14)
The section excludes all eight conjectured weights for RM(7, 14). It combines affine-flat arguments with Fourier analysis to rule out the candidate weights and their complements.
4 Exclusion of the eight weights in RM(7, 14)
- A hyperplane section of weight 64 reduces the argument to a degree-six restriction whose possible low-weight forms contradict the required intersection constraints.The first Kasami–Tokura form yields incompatible weights; the second would make the support an XOR of three affine seven-flats, ruled out by Lemma 6.Source: §4 · pp. 9–10
- The XOR of three affine seven-flats cannot have a weight in T, because the possible pairwise and triple intersections lead to contradictions in both cases.The proof separates the cases of a nonempty and empty triple intersection.Source: §4 · p. 9
- No word of RM(7, 14) has any of the four weights in T, and the four complementary weights are excluded as well.The complement relation wt(f) + wt(f + 1) = 2^14 supplies the latter exclusions.Source: §4 · pp. 10, 13
- Fourier coefficients encode the weights of paired hyperplane sections, and enumerating their allowed pairs yields constraints for each candidate weight.Table 1 lists signed nonzero Fourier coefficients used in that enumeration.Source: §4 · p. 11, Table 1 · p. 11
- For the remaining four cases, projection onto a six-dimensional subspace restricts character sums to {−31, −1, 1, 31}, forcing an impossible zero-frequency value.The resulting contradiction excludes all four cases.Source: §4 · pp. 12–13
5 Extend to higher dimensions
The section extends the exclusion of conjectured weights from RM(7, 14) to all RM(m −7, m), then establishes the exact spectrum by combining that exclusion with a constructive inclusion.
5 Extend to higher dimensions
- No word of RM(8, 15) has weight in T, so T is absent from Wm for every m ≥14.The proof uses a hyperplane section of weight 64 and bounds the weights of two complementary sections to derive a contradiction.Source: §5 · p. 14
- For every m ≥14, Wm equals A ∪ {w ∈2Z : 336 ≤w ≤2^m −336} ∪ (2^m −A), with the four weights in T and their complements excluded.The reverse inclusion follows by considering even weights through the midpoint and using complementation for the rest.Source: §5 · p. 15
- The base inclusion P14 ⊆W14 transfers to every m ≥14 by concatenating codewords and complementing the resulting words.The construction yields all even weights from 336 through 2^m −336, along with A and 2^m −A.Source: §5 · pp. 14–15
- For the reverse inclusion, all codeword weights are even; below 320 the classified weights lie in A, and between 320 and 334 the four weights in T are excluded.Every other even weight through the midpoint lies in the central interval, and complementation handles weights above it.Source: §5 · p. 15
- The three sets in the spectrum are disjoint, giving |Wm| = 2^m −291.The count uses |A| = 22 and 2^m−1 −335 even weights in the central interval.Source: §5 · p. 15
6 Conclusions
The conclusion identifies the remaining RM(7, 14) nonexistence cases and states that their exclusion, together with constructive inclusion, yields the exact spectrum for RM(m −7, m). It leaves the conjecture for RM(n −8, n) unresolved and proposes a broader pattern for weight spectra.
6 Conclusions
- The four low weights in T and their complements were the only outstanding nonexistence cases for RM(7, 14), and the paper excludes them in fourteen and every larger dimension.Combining these exclusions with constructive inclusion yields the exact spectrum of RM(m −7, m).Source: §6 · p. 16
- Whether Conjecture 1 holds for RM(n −8, n) with n ≥16 remains unknown.The authors say it is difficult to predict the conjecture's validity for further values of c.Source: §6 · p. 16
- The proposed Conjecture 2 describes spectra using low-weight and complementary sets plus a consecutive-even-integer interval.It proposes that A follows from a low-weight structure theorem, while C consists of consecutive even integers in the stated range.Source: §6 · p. 16
- The KTA structure theorem covers weights below 2.5 · 2^(n−r); a structure theorem below 3 · 2^(n−r) is left for future work.The broader theorem is proposed as a possible route to describing the low-weight structure.Source: §6 · p. 16