The multiplicative complexity of a map 
over the two-element finite
field is the least number of AND gates in an XOR-AND circuit computing 
(Schnorr 1989, Boyar and Find 2018). The circuit may use XOR gates and the constant 1 without cost. Consequently, each
input to an AND gate may be any affine
function of the original inputs and the outputs of earlier AND
gates, and each output of the circuit may be any such affine
function. In this model, the multiplicative complexity of 
is denoted 
.
A map has multiplicative complexity zero iff all its coordinate functions are affine.
Each coordinate function has a unique representation
as a multilinear polynomial over 
. Its algebraic degree is the largest number of input variables
in any monomial appearing in the representation. If
is the largest algebraic degree among the coordinate functions,
then 
(Schnorr 1989). At the other extreme, Boyar and Find (2018) showed that for 
,
almost all maps 
have multiplicative complexity at least 
.
They also proved that every such map has multiplicative complexity
at most 
,
where 
tends to 0 as 
grows. This measure is especially useful in forms of secure
computation and homomorphic encryption where AND gates are
substantially more expensive than XOR gates.
For 
,
let 
send the coefficients of the polynomials 
and 
to the coefficients 
, for 
, of 
. Taking 
to be the unique map between zero-dimensional
vector spaces, Morse (2026) proved the exact unrestricted
values
 |
In particular, multiplication of two four-term binary polynomials requires exactly nine AND
gates. The upper bound is given by a Karatsuba
multiplication construction using nine AND gates. The
lower bound is new for unrestricted circuits, which
may reuse nonlinear intermediate values and exploit the Boolean
algebra identity 
. Earlier results established the value nine only for
the more restrictive bilinear or quadratic circuit models.
Boyar and Find (2018) asked whether every quadratic map over 
has an optimal unrestricted circuit in which all intermediate values also have degree
at most two. The four-term multiplication result
gives a positive answer for one natural map, but the general
question and the unrestricted multiplicative complexities of 
for 
remain open.
Morse (2026) states that GPT-5.6 Sol assisted with research, proof development, computation, Lean formalization, literature verification, and manuscript preparation, and that
Anthropic Opus 5 served as a referee. The Lean development checks the unrestricted
circuit semantics and the theorem 
. However, the correspondence between the formal
statement and the mathematical claim has not received independent review (VibeMathed
2026).
