← All papers
First page of Unrestricted Boolean Multiplicative Complexity of Four-Term Binary Polynomial Multiplication: Rational Places, Hasse Jets, and the Failure of Nonlinear Feedback

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
A complete Lean 4 formalization verifies the Boolean-ANF semantics, unrestricted circuit model, and the exact multiplicative-complexity theorem, using no project-specific axioms.
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.

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).

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.

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_0Mul_1Mul_2Mul_3Mul_4
01369
Multiplicative complexity of short binary polynomial multiplication