Conjunction gates for binary-field multiplication

Let K be a binary field of degree n ≥ 1 with any basis b. Every signed unbounded AND/OR/XOR circuit computing all n coordinates of x * y from the 2n coordinates of x and y has at least 2n - 1 conjunction gates. XOR gates of every fan-in are free in this count, so it also bounds the number of unbounded-fan-in AND/OR gates in circuits with free XOR; fan-in, fanout, depth, and nonlinear reuse are unrestricted.

The proof applies the restriction–rank bound: every nonzero component ℓ(xy) is a quadratic form whose polar form ℓ(xy' + x'y) is nondegenerate on the 2n-dimensional input space, so the component is affine only on flats of dimension at most n.

theorem Algebraic.Aggregate.Geometry.FieldMul.boolFieldMul_nonaffineOnFlats {K : Type u_1} [Field K] [Algebra (ZMod 2) K] {n : ℕ} (b : Module.Basis (Fin n) (ZMod 2) K) : NonaffineOnFlats (boolFieldMul b) (n + 1)

No nonzero linear component of binary-field multiplication is affine on a flat with 2^(n+1) points.

theorem Algebraic.Aggregate.Geometry.FieldMul.two_mul_input_le_conjunctionCount_add_one {K : Type u_1} [Field K] [Algebra (ZMod 2) K] {n : ℕ} (b : Module.Basis (Fin n) (ZMod 2) K) (positive : 0 < n) (c : Circuit signature (n + n) n) (computes : c.Computes interpretation (boolFieldMul b)) : 2 * n ≤ conjunctionCount c.program + 1

Computing multiplication in a binary field of degree n ≥ 1, in any basis, requires at least 2n - 1 conjunction gates.