C++20 code accompanying the classification of Boolean cubic forms in ten variables and the resulting Reed--Muller weight-distribution computation.
Reusable code is in src/; experiments and inspection programs are in
exp/.
tests/test_invariant.cpp tests the invariant from Section Complete
Invariant. It checks GL(10,2)-invariance on random forms in dimensions 8, 9,
and 10, verifies distinct hashes for the 348 hardcoded m=9 representatives,
counts distinct hashes in a random m=10 sample, and reports evaluation times.
Compile and run:
g++ -std=c++20 -O3 -pthread -I src -I third_party tests/test_invariant.cpp -o bin/test_invariant
bin/test_invariantExample output:
m=9 representatives: distinct hashes 348/348
GL(10,2) invariance on hardcoded m=9 reps: 64/64
GL(10,2) invariance on random m=8 forms: 64/64
GL(10,2) invariance on random m=9 forms: 64/64
GL(10,2) invariance on random m=10 forms: 64/64
speed m=8: 1000 random forms, 43.832 ms total, 0.043832 ms/form, guard=f940afb07afdf670
speed m=9: 1000 random forms, 109.236 ms total, 0.109236 ms/form, guard=532371b1257ac20a
speed m=10: 1000 random forms, 205.022 ms total, 0.205022 ms/form, guard=cabe0440d2956814
random m=10 orbit hashes: distinct 1000/1000 samples
PASS
exp/bfs9.cpp implements the rank-stratified enumeration from Section
Enumeration by Alternating Rank and Appendix Catalog Construction and
Residual Searches. It starts from the unique rank-1 orbit x0*x1*x2,
expands by adding rank-1 cubics, identifies orbits with src/invariant.h, and
stops after finding all 348 nonzero m=9 orbits.
exp/bfs10.cpp applies the same construction in m=10. A full run is long and
should be partitioned across frontiers or machines.
Compile from the repository root:
g++ -std=c++20 -O3 -pthread -I src -I third_party exp/bfs9.cpp -o bin/bfs9
bin/bfs9 -r 4Example output:
rank rows known time
---- ------ --------- --------
1 1 1/348 0.002s
2 2 3/348 11.56s
3 8 11/348 1.1m
4 38 49/348 5.7m
Completed layers are written to data/bfs9/layer_RR.npy or
data/bfs10/layer_RR.npy. These files store the representative and the
rank-1 terms giving its alternating-rank decomposition. The rank layers can be
compared with Table 2 of the paper.
exp/gi.cpp runs the comparisons from Appendix Graph Isomorphism on
selected catalog pairs using the orthogonality graph G_f and the colored
incidence graph B_f. When canonical hashes agree, it constructs and verifies
a graph isomorphism. The selected pairs show that neither graph alone
distinguishes every orbit.
Compile and run:
g++ -std=c++20 -O3 -pthread -I src -I third_party exp/gi.cpp -o bin/gi
bin/giExample output:
| pair | isomorphic G_f | isomorphic B_f |
| ---------------- | --------------- | --------------- |
| f_341 vs f_342 | NO | NO |
| f_381 vs f_382 | YES | NO |
| f_441 vs f_442 | NO | NO |
| f_496 vs f_497 | NO | YES |
| f_1097 vs f_1144 | YES | NO |
| f_1386 vs f_1387 | YES | NO |
exp/stabilizer.cpp computes the natural dimension and stabilizer order
defined in Section Boolean Cubic Forms for selected catalog representatives.
It also prints the invariant hash used to identify each orbit.
Compile and run:
g++ -std=c++20 -O3 -pthread -I src -I third_party exp/stabilizer.cpp -o bin/stabilizer
bin/stabilizerExample output:
| form | representative | dim | |St| | invariant hash |
| ------ | ---------------------------------------- | --- | -------------- | ---------------- |
| f_12 | 012+034+067+135 | 8 | 2359296 | 751a7b0c180666ff |
| f_31 | 012+034+057+147+156+236 | 8 | 192 | 06d55037e205023f |
| f_32 | 012+034+056+078 | 9 | 12128668876800 | 8edd24685be67c7a |
| f_204 | 012+034+057+058+134+167+238+246+256+268 | 9 | 48 | 3f53b8383a2d958b |
| f_349 | 029+035+078+125+248+568 | 10 | 21139292160 | fe0c80e78564a8ac |
exp/thickness.cpp follows Appendix Monomial-Count Minimization. It starts
from a dense form, applies greedy GL(10,2) transvections with short plateau
walks, and prints the reduced form and the change of variables y = A x. The
resulting monomial count is an upper bound on the orbit thickness.
Compile and run:
g++ -std=c++20 -O3 -pthread -I src -I third_party exp/thickness.cpp -o bin/thickness
bin/thicknessReproducibility Examples for "The Weight Distribution of the Third-Order Reed--Muller Code of Length 2048"
src/enumerator.h implements the quotient computation from Section Coset
Weight Enumerators. The driver exp/enumerator.cpp applies it to
f_32941 = 015+025+026+034+078+128+147+236
+ 245+279+357+369+456+468+579+589,
one of the 179 catalog orbits attaining d2=408.
Compile and run:
g++ -std=c++20 -O3 -DNDEBUG -I src -I third_party exp/enumerator.cpp -o bin/enumerator
bin/enumeratorThe table contains the symmetric half of the enumerator;
A_{1024-w}=A_w. A single-thread run printed:
Started enumerating f_32941(x)+RM(2,10).
Computed in 150 seconds.
w A_w
---- -----------------
408 422912
416 70232064
424 2604958720
432 47030280192
440 554012571648
448 4768913117184
456 31322283489280
464 159371486863360
472 631035756813312
480 1945497353705472
488 4668779260701696
496 8720584817655808
504 12682704590524416
512 14368257675255808
src/heuristic_ub_r2m10.h implements the search from Section Heuristic
Upper Bounds, which found RM(2,10) corrections of weight at most 408 for the
BCF10 catalog. src/heuristic_ub_r6m10.h uses the cocubic moves from
Appendix Cocubic Upper-Bound Search to find RM(6,10) corrections of weight at
most 32. The driver exp/heuristic_ub.cpp runs both searches on two catalog
forms and writes the corrections to data/heuristic_ub/ as packed
uint64_t words. RM2 files contain one word; RM6 files contain fourteen
words.
Compile and run:
g++ -std=c++20 -O3 -DNDEBUG -pthread -I src -I third_party exp/heuristic_ub.cpp -o bin/heuristic_ub
bin/heuristic_ubExample output:
corrections written to data/heuristic_ub/
form RM2 ub RM6 ub
------ ------ ------
f_1007 360 28
f_3108 368 26
exp/trace_polynomials.cpp reproduces the scan from Appendix Trace
Representations of the Extremal Forms. It compares all 12*1023 cubic trace
monomials and all 66*1023^2 trace binomials over
GF(2)[alpha]/(alpha^10+alpha^3+1) with the 179 representatives in
data/representatives_408.txt. No trace monomial is extremal; the binomial
scan reaches one extremal orbit, represented by Tr(omega*x^21+x^49) with
omega=alpha^2+alpha^3+alpha^5+alpha^6+alpha^7.
Compile and run:
g++ -std=c++20 -O3 -DNDEBUG -pthread -I src -I third_party exp/trace_polynomials.cpp -o bin/trace_polynomials
bin/trace_polynomials --threads 48A 48-thread run printed:
field GF(2)[alpha]/(alpha^10+alpha^3+1)
family candidates extremal orbits representations time
------------------ ---------- ---------------- --------------- ----------
trace monomials 12276 0 0 11s
trace binomials 69070914 1 4092 1474s
extremal orbit
hash 6aa820dde330ed55
|St| 5
trace representation Tr(omega*x^21+x^49)
omega alpha^2+alpha^3+alpha^5+alpha^6+alpha^7
Section Discussion reports the coset enumerator of Tr_11(x^7) as an m=11
example of the quotient method from Section Coset Weight Enumerators.
exp/enumerator_tr11x7.cpp performs that computation over
GF(2)[z]/(z^11+z^2+1).
Compile and run:
g++ -std=c++20 -O3 -DNDEBUG -pthread -I src -I third_party exp/enumerator_tr11x7.cpp -o bin/enumerator_tr11x7
bin/enumerator_tr11x7 --threads 48A 48-thread run printed:
Started enumerating f(x)+RM(2,11) for f(x)=Tr_11(x^7).
Computed in 2596 seconds.
w A_w
---- --------------------
856 1284096
864 51589120
872 1224103936
880 19001606144
888 218044321792
896 1982554382336
904 14915333672960
912 95413956870144
920 527444203173888
928 2543802909159424
936 10763686864009216
944 40082413949681664
952 131568511236816896
960 380951601526177792
968 973242244411277312
976 2193951433168912384
984 4363972487604449280
992 7659225647446056960
1000 11861788922022014976
1008 16210844216987025408
1016 19551609716473978880
1024 20811583231735283712
tests/test_macwilliams.py repeats the MacWilliams consistency check from
Section Coset Weight Enumerators for data/enumerator_rm3_10.txt and
data/enumerator_rm3_11.txt. It verifies nonnegative integral dual
coefficients, B_1=...=B_15=0, and the predicted value of B_16.
Run from the repository root:
python tests/test_macwilliams.pyExpected output:
code dual first nonzero B_w expected status
-------- -------- ------------------- ------------------- ------
RM(3,10) RM(6,10) B_16 = 3439615168 B_16 = 3439615168 OK
RM(3,11) RM(7,11) B_16 = 110880192896 B_16 = 110880192896 OK
This section contains ongoing research developments that are not part of either paper above. The results and software are preliminary, may evolve, and may contain errors.
Dougherty, Mauldin, and Tiefenbruck in The Covering Radius of the Reed-Muller Code RM(m-4,m) in RM(m−3,m) derive cocubic lower bounds by constructing self-orthogonal spaces. Let 𝔽=𝔽₂, let f with deg f = m−3, and write g = f+p+ℓ, where deg p = m−4 and deg ℓ ≤ m-5. Put S={x∈𝔽ᵐ : g(x)=1}, n = wt(g) = |S|. We want to prove n ≥ LB. For every Boolean polynomial h, Σ_{x∈𝔽ᵐ} h(x) mod 2 = [x₁..xₘ]h, and let ⟨a|b⟩ = Σ_{x∈S} a(x)b(x) mod 2 = [x₁..xₘ]abg. Let V = ⟨g,x₁g,…,xₘg⟩ for x∈S and V ⊆ 𝔽ⁿ. Since g=1 on S, this is also the space generated by the restrictions of 1,x₁,…,xₘ to S. For affine a and b, deg(abg) ≤ m−1, so V ⊆ V^⊥. Since a self-orthogonal subspace of 𝔽ⁿ has dimension at most n/2, this already gives n ≥ 2 dim V.
To strengthen this bound, let Q = {q : q = Σᵢⱼqᵢⱼxᵢxⱼ and deg(qf) ≤ m−2}. For q ∈ Q, we have deg(qg) ≤ m−2, so ⟨q|a⟩ = [x₁..xₘ]qag = 0 for every affine a, and hence qg ∈ V^⊥. For q,q′ ∈ Q, put ⟨q|q′⟩ = bₚ(q,q′) = [x₁..xₘ]qq′(f+p). Since deg(qq′ℓ) ≤ m−1, we can ignore ℓ. Let r = rank bₚ and choose q₁,…,qᵣ ∈ Q corresponding to r linearly independent rows of bₚ. Then q₁g,…,qᵣg are linearly independent mod V. Indeed, if Σᵢcᵢqᵢg ∈ V, taking its scalar product with qg for every q ∈ Q shows that the same linear combination of the selected rows of bₚ is zero, and hence every cᵢ = 0. Therefore V together with q₁g,…,qᵣg is a (dim V + r)-dimensional subspace of V^⊥. Since dim V^⊥=n - dim V, we obtain dim V + rank bₚ ≤ n - dim V, or n ≥ 2 dim V + rank bₚ. Since bₚ depends affinely on p, proving the lower bound reduces to showing that the corresponding MinRank problem has no solution.
Since bₚ is alternating, its symplectic normal form shows that the largest local certificate level for a fixed p is rank bₚ / 2. Thus, without restricting certificate size, the largest possible certificate level is minₚ rank bₚ / 2.
To reduce the full problem to smaller ones, choose a subspace N ⊆ Q and let Aₚ be the restriction of bₚ to N. Only a linear projection of p affects Aₚ. We choose N so that this projection is small, allowing us to enumerate all possible restrictions Aₚ while leaving the remaining coefficients of p as free variables. For each fixed Aₚ, put Aₚ into symplectic normal form. Its nonzero blocks contribute rank Aₚ, while its zero rows and columns span rad Aₚ. Let Cₚ be the cross-block of bₚ between rad Aₚ (rows) and Q/N (columns). Since every vector in rad Aₚ is already orthogonal to N, ker Cₚᵀ = rad Aₚ ∩ rad bₚ. Hence rank Cₚ = dim rad Aₚ - dim(rad Aₚ ∩ rad bₚ). The cross-block contributes at least 2 rank Cₚ in addition to rank Aₚ, and therefore rank bₚ ≥ rank Aₚ + 2 rank Cₚ. Thus the lower-bound proof reduces to showing that, for every p, either rank Aₚ or rank Cₚ is already sufficiently large.
To prove rank Cₚ ≥ t, suppose instead that rank Cₚ < t. Then dim ker Cₚᵀ ≥ dim rad Aₚ - t + 1. Choose a t-dimensional subspace H ⊆ rad Aₚ, so any counterexample must satisfy hᵀCₚ = 0 for some nonzero h ∈ H. There are 2ᵗ-1 possible vectors h, and each condition hᵀCₚ = 0 is a linear system in the remaining coefficients of p. Gaussian elimination either shows that the system is inconsistent or records h as a known direction in ker Cₚᵀ. In the latter case, we repeat the argument mod the kernel directions already found. If enough independent directions are accumulated, we have found a counterexample; if every branch becomes inconsistent before that, then rank Cₚ ≥ t for every p.
lb_lvl5.cpp applies this reduction to three forms in dimensions m=9,10,11, represented by their cubic complements.
F = x₁x₄x₇ + x₁x₅x₈ + x₁x₆x₉ + x₂x₄x₈ + x₂x₅x₇ + x₂x₅x₉ + x₂x₆x₇ + x₃x₄x₉ + x₃x₅x₇ + x₃x₆x₈ + x₃x₆x₉
m=9 : F + x₇x₈x₉
m=10: F + x₈x₉x₁₀
m=11: F + x₉x₁₀x₁₁
It proves rank bₚ ≥ 10 for every homogeneous p of degree m-4 within few seconds. Since dim V = m+1 for these forms, this gives the lower bounds 30, 32, and 34. The three-variable extension of Dougherty, Mauldin, and Tiefenbruck preserves the certificate level, so these three consecutive examples imply ρ(RM(m-4,m),RM(m-3,m)) ≥ 2m+12 for every m≥9, improving their general lower bound 2m+10. In particular, together with the upper bound 32 established above, this proves ρ(RM(6,10),RM(7,10))=32.
lb_lvl6.cpp applies the same framework to the m=9 form represented by the cubic complement F+x₇x₈x₉ (corresponding to catalog #53). Proving the stronger bound rank bₚ ≥ 12 requires a more careful treatment of the remaining Aₚ low-rank branches, using symmetry reduction and polynomial identities for the cases not closed by linear Gaussian elimination. The complete single-threaded computation verifies rank bₚ ≥ 12 for every homogeneous p of degree 5 in under two minutes. Since dim V=10, this gives n ≥ 2 dim V+rank bₚ ≥ 32. Together with the known upper bound 32, this proves ρ(RM(5,9),RM(6,9))=32.
If you use this work in research, please cite one of the following BibTeX entries.
@misc{khoruzhii2026rmwd,
author = {Kirill Khoruzhii and Patrick Gel{\ss} and Sebastian Pokutta},
title = {The Weight Distribution of the Third-Order Reed-Muller Code of Length 2048},
year = {2026},
eprint = {2607.02365},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.02365}
}@misc{khoruzhii2026cbcf,
author = {Kirill Khoruzhii and Patrick Gel{\ss} and Sebastian Pokutta},
title = {Classification of Boolean Cubic Forms in Ten Variables},
year = {2026},
eprint = {2606.28473},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.28473}
}