Affine pairing and entropy for unbounded signed gates #
Every signed AND/OR/XOR circuit computing the fixed explicit family has more than
(C - ε)n gates eventually, where C ≈ 1.2453914029 is defined exactly by
Algebraic.Cutwidth.Aggregate.Geometry.Fiber.Conditional.gateCoefficient. The natural signature
contains all binary Boolean functions without increasing their gate count.
Computing all n coordinates of inversion in a binary field requires at least
I * n - P gates, where I ≈ 1.5659486596 and P ≈ 0.6016050397, with exact constants in
Algebraic.Cutwidth.Aggregate.Geometry.Fiber.Conditional, for every linear basis and n ≥ 3.
The earlier finite bounds remain available; their smaller additive losses can help at small n.
If no nonzero output component of an m-output map is affine on a flat of 2^D points, every
circuit computing it has at least m + n - D conjunction gates. For the Gold map x ↦ x³ in odd
dimension n ≥ 3, this gives (3n - 3)/2 conjunctions and at least G * n - Q gates, where
G ≈ 1.771556 and Q ≈ 0.857781 are defined in Algebraic.Aggregate.Geometry.Gold.
Multiplication in a binary field of degree n ≥ 1 needs at least 2n - 1 conjunction gates.