Research · Papers · Symmetry, state encodings and search gauges · MF-175
Degree distribution of the two-column C7 transducer nonlinear quotient
For the two-column C7 transducer with dim V = 4, exactly 12 nonzero cosets in V have degree ≥ 3 and 3 cosets are quadratic.
Published 2026-09-04
For everyone
Plain summary
Boolean functions map binary inputs to binary outputs. Their algebraic degree measures how many inputs interact in their highest-order terms. When analyzing zero-knowledge proof gadgets and cryptographic circuits, researchers evaluate components called transducers to determine their multiplicative complexity—the minimum number of AND gates needed to compute them.
This paper analyzes the two-column C7 transducer, which takes 11 inputs and produces 5 outputs. Stripping away constant and linear components leaves a space of 15 distinct nonlinear output combinations. By testing all 2,048 possible input patterns, we verified that 12 of these 15 combinations have algebraic degree 3 or 4 (four are degree 3 and eight are degree 4), while only 3 are quadratic (degree 2). This confirms the theoretical prediction of Theorem D1 and supplies the degree separation needed to prove multiplication lower bounds for these circuits.
Result
For the two-column C7 transducer with 11 inputs, 5 outputs, and a nonlinear quotient space V modulo affine of dimension dim V = 4:
Across all 15 nonzero cosets in V:
- Exactly 12 cosets have algebraic degree >= 3. Specifically, 4 coset classes are cubic (degree 3) with 84 monomials each, and 8 coset classes are quartic (degree 4) with up to 119 monomials.
- Exactly 3 cosets are purely quadratic (degree 2).
This confirms the degree prediction of THEOREM D1 (MF-144, ML-083 v) and establishes the degree separation necessary for MC(F_c) >= 3c under the packing filtration.
Setting and definitions
The two-column C7 transducer is a multi-output Boolean function mapping 11 binary inputs to 5 binary outputs. Let V denote the nonlinear quotient space of the transducer modulo affine functions, where dim V = 4 over GF(2).
The space V contains 2^4 - 1 = 15 nonzero cosets. The algebraic degree of a Boolean function is the degree of the highest-degree monomial in its algebraic normal form (ANF). Multiplicative complexity MC(f) is the minimum number of binary AND gates required to evaluate f over the basis (AND, XOR, NOT). MC(F_c) denotes the multiplicative complexity of an aggregated transducer family F_c parameterized by c under a packing filtration.
Method
The algebraic normal form of every function in the quotient space was computed via a complete Mobius ANF transform over all 2^11 = 2,048 input assignments. Algebraic degrees and monomial counts for all 15 nonzero cosets in V were extracted directly from the transform output.
Verification script and artifact: wave2-zk-gadgets/scratch/check_c7_degrees.py.
Evidence tier: P + FC.
Discussion
The computation validates the structural prediction of THEOREM D1 in MF-144 and ML-083 v. Because 12 of the 15 nonzero cosets reach algebraic degree 3 or 4, this evaluation establishes the degree separation required for the linear lower bound MC(F_c) >= 3c under the packing filtration.
The verification is exhaustive across the full 11-variable domain. The result characterizes the quotient space of the two-column transducer; evaluating alternative transducer configurations requires separate packing filtration arguments. The register records no prior-art claims or index corrections for this entry.
For everyone — the takeaway
What this means
Proving the exact algebraic degree of circuit components allows researchers to establish hard lower bounds on computation costs. Checking every input assignment of the two-column C7 transducer confirms that almost all nonlinear output combinations have degree 3 or 4. This provides the structural separation needed to prove that larger assemblies of these circuits cannot bypass multiplication thresholds.
Register references
- MF-175
- MF-144
- ML-083 v
- Receipt: wave2-zk-gadgets/scratch/check_c7_degrees.py
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 0 of 1 receipt files bundled (1 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.