Lower bounds for multiplication in a finite field #
Let K be a finite field of degree n over a finite field F, with a basis b, and let
fieldMul b : F ^ (n + n) → F ^ n be multiplication in K written in coordinates: the first
n inputs are the coordinates of x, the last n those of y, and the outputs are the
coordinates of x * y (fieldMul_append_equivFun). Consider circuits over F, over any
signature whose gates have at most two arguments, so with arbitrary functions F × F → F,
unary functions and constants as gates. Over F = GF(2) these are the circuits over the full
binary basis B₂.
The cut bound (le_add_two_of_fieldMul). Every split of the wires holding a inputs of
the first factor and n - a outputs is crossed by at least n - 2 signals. Fixing the second
factor y makes the map linear in x, so the restricted rank-cut bound
(MultiOutput.card_pow_le_supportedKernel) applies to the blocks
M_y[Y_T, X_S] and M_y[Y_S, X_T] of multiplication by y. Averaged over y, a block with
|X| ≤ |Y| has a kernel of average size at most 2: a nonzero vector u lies in the kernel
for a |F| ^ -|Y| fraction of the y, since y ↦ y · u is a bijection of K. So some y
makes both kernels number at most 4 together, and both blocks are nearly of full rank.
One component (mem_component_of_fieldMul). The component of an output is crossed by no
signal, so for every fixed factor the blocks between its inputs and the outputs outside it,
and between the inputs outside it and its outputs, vanish
(MultiOutput.apply_eq_zero_of_closed_of_trace). As y = (b j)⁻¹ b i makes the entry
(i, j) nonzero, the component holds every input of the first factor and every output, and by
fixing x instead, every input of the second factor.
The finite bound (sub_two_le_of_fieldMul). Under the graph-ordering hypothesis for
coefficient A, slack η and constant C, a circuit of size s has
n - 2 ≤ (A + η) (s - 2 n)⁺ + 3 log₂ (2 n + 3 s) + C. The outputs are distinct wires and none
is an input of the first factor, so along the ranking of MultiOutput.exists_rank some prefix
ending at one of these 2 n terminals holds exactly n of them; it is charged to the
component holding all 2 n inputs.
The asymptotic bound (eventually_lt_size_of_fieldMul). With the edge-score ordering
coefficient A = 2 κ_E, where κ_E = Gaussian.frontierCoefficient ≈ 0.14035, for every
ε > 0 and all large n, every such circuit has more than (2 + 1/(2 κ_E) - ε) n gates, the
coefficient being 2 + π/(3 arccos((1 + 2√2)/4)) ≈ 5.5625; as 2 κ_E ≤ 9/32, also more than
(50/9 - ε) n gates (eventually_lt_size_of_fieldMul_fifty_div_nine). The threshold depends
only on ε, not on the fields, the basis or the signature. In particular
(eventually_lt_size_galoisField), multiplication in GF(2 ^ n) = GaloisField 2 n over
GF(2) = ZMod 2, in any basis, needs more than (2 + 1/(2 κ_E) - ε) n binary gates; such
bases exist (nonempty_basis_galoisField).
Prior art. Earlier lower bounds for this multiplication count only the multiplications of
bilinear or quadratic algorithms; we know of no earlier bound on the number of gates over the
full binary basis. The coefficient is not claimed to be a record for explicit functions with
2 n inputs and n outputs in general.
Multiplication in coordinates #
fieldMul multiplies. On the coordinates of u and of v it returns the coordinates
of u * v.
Circuits for multiplication #
All inputs and outputs lie in one component. If a circuit over a field, over any
signature, computes multiplication in coordinates and n ≥ 1, the component of its first
output in the wire graph contains every input and every output.
The cut bound for multiplication. If a circuit over a finite field, over any signature,
computes multiplication in coordinates, then every set S of its wires holding a inputs of
the first factor and n - a outputs is crossed by at least n - 2 forward and backward
signals.
The finite bound for multiplication. If a circuit over a finite field, over any
signature with fan-in at most two, computes multiplication in a degree-n extension in
coordinates, then under the graph-ordering hypothesis
n - 2 ≤ (A + η) (s - 2 n)⁺ + 3 log₂ (2 n + 3 s) + C for its size s.
Asymptotic bounds #
The asymptotic bound with a general ordering coefficient. If the graph-ordering
hypothesis holds with coefficient A > 0 for every positive slack, then for every ε > 0 and
all large n, every fan-in-two circuit over a finite field F computing multiplication in a
degree-n extension K of F, in any basis, has more than (2 + 1/A - ε) n gates.
Multiplication in a degree-n extension needs (2 + 1/(2 κ_E) - ε) n gates. For every
ε > 0 and all large n, every circuit over a finite field F, over any signature with
fan-in at most two, computing multiplication in a degree-n extension of F in any basis has
more than (2 + 1/(2 κ_E) - ε) n gates, where κ_E = Gaussian.frontierCoefficient; the
coefficient is 2 + π/(3 arccos((1 + 2√2)/4)) ≈ 5.5625.
Multiplication in a degree-n extension needs (50/9 - ε) n gates.
Multiplication in GF(2 ^ n) #
GF(2 ^ n) has a basis over GF(2) indexed by Fin n for every n ≥ 1.
Multiplication in GF(2 ^ n) needs (2 + 1/(2 κ_E) - ε) n binary gates. For every
ε > 0 and all large n, every circuit over GF(2) = ZMod 2 with fan-in at most two, so in
particular every circuit over the full binary basis B₂, computing multiplication in
GF(2 ^ n) = GaloisField 2 n in any basis over GF(2) has more than
(2 + 1/(2 κ_E) - ε) n ≈ (5.5625 - ε) n gates.
Multiplication in GF(2 ^ n) needs (50/9 - ε) n binary gates.