🔢 mathematics

Classification of Boolean Cubic Forms in Ten Variables

This paper presents a complete classification of Boolean cubic forms in ten variables up to GL(10,2)-equivalence, yielding a catalog of 3,691,560 nonzero orbits with detailed structural data and establishing the first full classification of alternating trilinear forms in dimension 10 over GF(2).

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

Published 2026-06-30

📖 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 have a giant box of Lego bricks. You want to build every possible unique 3D shape you can make using exactly ten specific types of bricks. However, there's a catch: if you can rotate or flip one shape to make it look exactly like another, they count as the same shape.

This paper is essentially a massive, exhaustive catalog of all those unique shapes, but instead of Lego bricks, the "bricks" are mathematical building blocks called Boolean cubic forms.

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

1. The Big Task: Sorting the Chaos

The authors wanted to sort every possible mathematical expression involving ten variables (let's call them $x_1$ through $x_{10}$ ) that follows specific rules (they are "cubic," meaning they involve multiplying three variables together, like $x_1 \times x_2 \times x_3$ ).

There are billions of ways to write these expressions. But many of them are just "disguises" of the same underlying structure. If you change the labels of your variables (a mathematical "basis change"), two different-looking formulas might actually be the same shape.

The goal was to find every unique shape (called an "orbit") and list them all.

The Result: They found exactly 3,691,560 unique shapes. That is a huge number, but it's the complete list. Nothing is missing.

2. How They Did It: The "Rank" Strategy

Instead of trying to list every single possibility at once (which would take forever), they built the shapes layer by layer, like climbing a ladder.

The Ladder (Alternating Rank): They started with the simplest shapes (rank 1). Then, they asked: "What happens if I add one simple building block to a rank 1 shape?" That creates a rank 2 shape. They kept adding blocks, moving up the ladder from rank 1 to rank 7.
The Filter: At every step, they had to check: "Is this new shape actually new, or is it just a disguised version of one we already found?"

3. The Detective Work: The "Fingerprint"

To tell if two shapes are the same, they needed a perfect fingerprint.

The First Clue (The Orthogonality Graph): They turned each shape into a map (a graph) showing how the variables relate to each other. For smaller problems (fewer than 10 variables), this map was enough to prove two shapes were identical.
The Problem: At 10 variables, two completely different shapes sometimes produced the exact same map. The first clue wasn't enough.
The Second Clue (The Incidence Graph): They added a second, more detailed map that looked at the "inside" of the shape.
The Final Fingerprint: By combining data from both maps into a single 64-bit number (like a digital hash code), they created a perfect fingerprint. If two shapes have the same fingerprint, they are definitely the same. If they have different fingerprints, they are definitely different.

4. What's in the Catalog?

For every single one of the 3.6 million unique shapes, the authors recorded:

The Representative: The simplest, cleanest version of that shape (using the fewest possible terms).
The Symmetry Score: How many ways you can rotate or flip the shape without changing it. Some shapes are very symmetrical (easy to spin), while most are unique and rigid.
The Blueprint: A specific way to build that shape using the minimum number of "decomposable" blocks.

5. Why Does This Matter? (According to the Paper)

The paper mentions a few specific reasons why this list is useful, sticking strictly to what they claim:

Coding Theory: It helps improve error-correcting codes (like those used in data transmission) by understanding the structure of "Reed-Muller codes."
Quantum Computing: In building fault-tolerant quantum computers, certain calculations require "Toffoli gates." The authors show that the complexity of these calculations is directly linked to the "rank" of these shapes. Having this catalog allows engineers to look up the most efficient way to build these circuits.
Mathematical Geometry: It solves a long-standing puzzle about the geometry of "trivectors" in 10-dimensional space over the field with two numbers (0 and 1).

Summary

Think of this paper as the periodic table for a specific type of 10-variable mathematical shape. Before this, scientists knew these shapes existed but didn't have a complete list. Now, they have a verified, exhaustive catalog of over 3.6 million unique entries, complete with "fingerprints" to identify them and "blueprints" to build them efficiently. This helps engineers and mathematicians solve problems in coding and quantum computing by turning a complex search problem into a simple lookup table.

Technical Summary: Classification of Boolean Cubic Forms in Ten Variables

Problem Statement
The paper addresses the classification of Boolean cubic forms in ten variables over the field $\mathbb{F}_2$ up to $GL(10, 2)$-equivalence. A Boolean cubic form is a polynomial $f(x) = \sum T_{ijk} x_i x_j x_k$ where coefficients are in $\mathbb{F}_2$ and variables satisfy $x_j^2 = x_j$ . Two forms are equivalent if one can be transformed into the other via an invertible linear change of variables, ignoring constant, linear, and quadratic terms. This classification corresponds to enumerating the nonzero orbits of the space $RM^*(3, 10)$ (the third layer of Reed–Muller codes) under the action of $GL(10, 2)$. While complete classifications exist for dimensions $m \leq 9$ over various fields, the case $m=10$ had not been addressed over any field prior to this work.

Methodology
The authors employ a rank-stratified enumeration strategy combined with a novel complete invariant for orbit identification.

Rank-Stratified Enumeration (BFS):
The enumeration proceeds by "alternating rank," defined as the minimum number $r$ such that a form $f$ can be decomposed into a sum of $r$ decomposable cubics $u(x)v(x)w(x)$ . The process starts with the zero form and iteratively adds rank-1 forms (decomposable cubics) to representatives of the current layer. This generates candidates for the next rank layer. The search space is significantly reduced by identifying $GL(10, 2)$-orbits at each step rather than enumerating all $2^{\binom{10}{3}}$ forms.
Complete Invariant Construction:
To distinguish between orbits efficiently, the authors construct a $GL(10, 2)$-invariant.
- Orthogonality Graph ( $G_f$ ): Based on the relation $u \perp_f v \iff \Delta_u \Delta_v f(x) = 0$ . While the isomorphism class of $G_f$ is a complete invariant for $m < 10$ , it fails for $m=10$ , leaving 51 unresolved collisions.
- Incidence Graph ( $B_f$ ): A bipartite graph derived from the polar bilinear forms, where edges represent image relationships ( $u \to_f v$ ).
- Local Statistics: Instead of full graph isomorphism testing (which is computationally expensive), the authors extract local statistics:
  - $\mu_5(f)$ : The multiset of closed walks of length 5 in $G_f$ .
  - $\theta(f)$ : A specific set of right degree-codegree counts from $B_f$ .
  - $\rho(f)$ : A resolver based on marked triples for the single remaining collision pair ( $f_{381}, f_{382}$ ).
- The triple $(\mu_5, \theta, \rho)$ is compressed into a single 64-bit word. This invariant is verified to be collision-free across all representatives.
Verification:
Completeness is verified independently by two methods:
- Burnside's Lemma: The total count of orbits matches the theoretical sum derived from the group action.
- Orbit-Stabilizer Identity: The sum of $|GL(10, 2)| / |St(f)|$ over all catalog representatives equals the total number of nonzero forms ( $2^{\binom{10}{3}} - 1$ ).

Key Contributions and Results

The Catalog: The paper presents an explicit catalog of all 3,691,560 nonzero $GL(10, 2)$-orbits of Boolean cubic forms in ten variables.
Representatives: For every orbit, the catalog provides a representative with a minimized monomial count (maximum observed is 17), the order of its stabilizer in $GL(10, 2)$, and an explicit alternating rank decomposition.
Structural Data:
- Alternating Rank: The maximum alternating rank in dimension 10 is 7. The distribution shows that rank 6 forms constitute the dominant layer among nondegenerate forms.
- Stabilizers: There are 143 distinct stabilizer orders. Most forms in $m=10$ have a trivial stabilizer.
- Dimensionality: Of the total orbits, 348 have nontrivial radicals (inherited from lower effective dimensions), while 3,691,212 are nondegenerate in dimension 10.
Invariant Performance: The 64-bit invariant evaluates in an average of 0.20 ms per form, significantly faster than direct canonical labeling (which took up to 8.9 s for collision classes).

Significance and Applications
The authors position this work as a foundational resource for several areas:

Coding Theory: The catalog provides the necessary input for computing coset weight enumerators and covering radii for third-order Reed–Muller codes $RM(3, 10)$ and related structures like $RM^*(7, 10)$ . It also supplies the orbit-indexing layer required for Sarwate-type recursions for $RM(3, 11)$.
Quantum Computing: The classification offers a lookup table for optimizing quantum circuits. Since the alternating rank of the cubic part of a phase polynomial controls the Toffoli gate count, the catalog allows for the replacement of cubic fragments (up to 10 variables) with optimal decompositions, analogous to subcircuit replacement for AND-count minimization.
Mathematical Classification: This constitutes the first complete classification of alternating trilinear forms in dimension 10 over any field. By polarization, the results directly apply to the geometry of trivectors and the classification of code loops via associator forms.

The paper concludes that while the classification is complete for $m=10$ , extending this to $m=11$ would require substantially more efficient invariants due to the exponential growth in the number of orbits (estimated at $\approx 6 \times 10^{13}$ ). The data and code are made available via Zenodo and GitHub.