Lower bounds for polynomial multiplication #

Polynomial multiplication polyMul n maps the coefficients x₀, …, x_{n-1} and y₀, …, y_{n-1} of two polynomials of degree below n (the first and the last n inputs) to the 2n - 1 coefficients z_m = ∑_{i + j = m} xᵢ yⱼ of their product.

The cut bound (min_add_min_le_of_polyMul). Let a circuit with polynomial gates over any field K, of any degree and arity, formally compute polynomial multiplication. Every split S of its wires, holding the inputs X_S and leaving X_T, is crossed by at least min(|X_S ∩ x|, |X_T ∩ y|) + min(|X_S ∩ y|, |X_T ∩ x|) signals. By the Hessian consequence of the Taylor cut lemma (Taylor.blockRank_hessian_le), for all weights μ the block H[X_S, X_T] of the Hessian of ∑ₘ μ m z_m has rank at most the number of crossing signals; this Hessian is [[0, Λ], [Λᵀ, 0]] for the Hankel matrix Λ = (μ (i + j)) (sum_smul_hessian_polyMulPolynomial). For the weights μ m = t ^ (m²) in the rational functions K(t), Λ is totally regular in every characteristic (totallyRegular_genericHankel): in the expansion of a square minor with increasing rows and columns, the identity permutation alone attains the largest degree, by the rearrangement inequality. So the two blocks of H[X_S, X_T] have the full ranks min(|X_S ∩ x|, |X_T ∩ y|) and min(|X_S ∩ y|, |X_T ∩ x|) (min_add_min_le_blockRank_crossMatrix). Over ZMod q for a prime q > 2n, the same bound holds for arbitrary gate functions (min_add_min_le_of_polyMul_zmod): the weights μ m = 1 / (m + 2) make Λ the Hankel Cauchy matrix, and the counting rank-cut bound (blockRank_add_transpose_le_of_sum) applies to the quadratic form ∑ₘ μ m z_m = xᵀ Λ y.

The finite bound (le_of_polyMul, le_of_polyMul_zmod). The component of the first input is crossed by no signal, so the cut bound puts every input into it. Along the ranking of MultiOutput.exists_rank, the prefix ending at a suitable input holds exactly n of the 2n inputs, a of the first factor and n - a of the second, so it is crossed by at least min(a, a) + min(n - a, n - a) = n signals. With a graph-ordering hypothesis for coefficient A, slack η and constant C, a fan-in-two circuit with s gates therefore has n ≤ (A + η) (s - 2n)⁺ + 3 log₂ (2n + 3 s) + C.

The asymptotic bound (eventually_lt_size_of_polyMul). 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. The threshold depends only on ε, not on the field, the signature or the gate polynomials. The bound holds

for formal computation with polynomial gates over every field (eventually_lt_size_of_polyMul),
for computation of the polynomial function with polynomial gates over every infinite field (eventually_lt_size_of_polyMul_of_infinite),
for the number of additions and multiplications of arithmetic circuits, with arbitrary constants free, computing the polynomial function over every infinite field (eventually_lt_arithmeticCost_of_polyMul) or formally computing the polynomials over every field (eventually_lt_arithmeticCost_of_polyMul_formal), and
for circuits with arbitrary gates of fan-in at most two over ZMod q for every prime q > 2n (eventually_lt_size_of_polyMul_zmod).

Gate polynomials carry their coefficients, so in the first two statements only explicit nullary gate occurrences are counted beyond the operations.

Prior art. Lower bounds for polynomial multiplication have counted multiplications: Kaminski and Bshouty (Multiplicative complexity of polynomial multiplication over finite fields, J. ACM 36, 1989) prove that bilinear algorithms over a fixed finite field need 3n - o(n) multiplications, while over fields with at least 2n - 2 elements 2n - 1 multiplications suffice. Read as bounds on the total number of operations they give about 4n. The coefficient here is not claimed to be a record beyond this comparison.

Lower bounds for polynomial multiplication #

Polynomial multiplication #

The cut bound #

The finite bound #

Asymptotic bounds #