Unrestricted Boolean Multiplicative Complexity of Four-Term Binary Polynomial Multiplication: Rational Places, Hasse Jets, and the Failure of Nonlinear Feedback
Gregory Morse
cs.CC
Aug 31, 2026 · v1
cs.DS
TL;DR
A complete Lean 4 formalization verifies the Boolean-ANF semantics, unrestricted circuit model, and the exact multiplicative-complexity theorem, using no project-specific axioms.
Abstract
Classical lower bounds show that multiplying two degree-three polynomials over $\mathbb F_2$ requires nine scalar products in bilinear or quadratic models. They do not settle unrestricted Boolean multiplicative complexity: an XOR–AND circuit may reuse nonlinear intermediate wires, and Boolean equality is taken modulo $x_i^2=x_i$, so a multiplication can lower algebraic degree. Let $\operatorname{Mul}_4:\mathbb F_2^8\to\mathbb F_2^7$ output the seven coefficients of the product of two four-term binary polynomials. We prove that its unrestricted XOR–AND multiplicative complexity is exactly nine. This resolves, for a natural vector-valued quadratic function, the Boyar–Find question of whether a quadratic-circuit lower bound can persist against unrestricted nonlinear reuse. The proof is structural rather than exhaustive. A useful purely quadratic prefix is forced onto the three rational places of $\mathbb P^1(\mathbb F_2)$. In a hypothetical eight-AND circuit, the unique non-useful gate must carry a cubic high part. Any useful continuation then forces a rational tangent and exposes a first Hasse jet, while exterior jet separation together with Boolean idempotence prevents the same defect from exposing the second Hasse jet. The required useful suffix therefore cannot exist. A complete Lean 4 formalization verifies the Boolean-ANF semantics, the unrestricted circuit model, and the exact theorem; it uses no project-specific axiom or native decision procedure. The same zero-defect flag argument gives multiplicative complexity six for three-term multiplication, and the method isolates the multi-defect obstruction for five terms.
Problem
Multiplying two degree-three polynomials over F_2 requires nine scalar products in bilinear/quadratic models, but whether this bound persists under unrestricted Boolean (XOR-AND) circuits that reuse nonlinear wires modulo x_i^2=x_i was open (the Boyar-Find question).
Approach
The function Mul_4: F_2^8 -> F_2^7 outputting seven product coefficients is analyzed via a structural (non-exhaustive) argument. A purely quadratic prefix is forced onto the three rational places of P^1(F_2); in a hypothetical eight-AND circuit the unique non-useful gate must carry a cubic high part, forcing a rational tangent exposing a first Hasse jet, while exterior jet separation with Boolean idempotence prevents exposure of the second jet. A complete Lean 4 formalization verifies the Boolean-ANF semantics, the unrestricted circuit model, and the exact theorem.
Results
The unrestricted XOR-AND multiplicative complexity of Mul_4 is exactly nine, resolving the Boyar-Find question for this quadratic vector-valued function. The same argument yields complexity six for three-term multiplication, giving the sequence (0,1,3,6,9) for Mul_0 through Mul_4.
| Mul_0 | Mul_1 | Mul_2 | Mul_3 | Mul_4 |
|---|
| 0 | 1 | 3 | 6 | 9 |
Multiplicative complexity of short binary polynomial multiplication