Proofs for polynomial multiplication #
- The Hessian (
sum_smul_hessian_polyMulPolynomial): the Hessian of∑ₘ μₘ z_mis the block matrix[[0, Λ], [Λᵀ, 0]]withΛ = (μ (i + j))the Hankel matrix of the weights. - Its blocks (
min_add_min_le_blockRank_crossMatrix): ifΛis totally regular, the block of[[0, Λ], [Λᵀ, 0]]between a setXof inputs and its complement contains a nonsingular block-diagonal square block of sizemin(|X ∩ x|, |Xᶜ ∩ y|) + min(|X ∩ y|, |Xᶜ ∩ x|). - A generic Hankel matrix (
totallyRegular_genericHankel): over the rational functionsK(t)in any characteristic, the Hankel matrix(t ^ ((i + j)²))is totally regular. In the expansion of a square minor with increasing rowsrand columnsc, the term of a permutationπhas degree∑ (r (π a) + c a)², which by the rearrangement inequality is largest exactly for the identity; so the minor has a monomial with coefficient one. - The cut bound (
min_add_min_le_of_formallyComputes,min_add_min_le_of_computes_zmod): every split is crossed by at least that many signals, by the Hessian consequence of the Taylor cut lemma with these weights overK(t), or overZMod qby the counting rank-cut bound for the quadratic form∑ₘ μₘ z_m = xᵀ Λ ywith the Hankel Cauchy weights. - The finite bound (
le_of_cut): the cut bound puts all inputs in one component; the prefix ending at an input with exactlynof the2ninputs is crossed bynsignals.
The two halves of the inputs #
Block matrices #
The symmetrization of [[0, Λ], [0, 0]] is [[0, Λ], [Λᵀ, 0]].
The quadratic form of [[0, Λ], [0, 0]] is xᵀ Λ y.
Weighted sums of the outputs #
A weighted sum of sums over i + j = m is a sum over all i and j.
A weighted sum of the outputs of polynomial multiplication is ∑ᵢ ∑ⱼ μ (i + j) xᵢ yⱼ.
Polynomial multiplication evaluates its polynomials.
Over every commutative algebra, polynomial multiplication evaluates its polynomials.
Polynomial multiplication computes the coefficients of the product of two polynomials.
Every output of polynomial multiplication is a nonconstant function: it vanishes at zero and is one at the indicator of one first-factor and one second-factor coefficient.
The Hessian #
The Hessian of a weighted sum of the outputs. For every point, the Hessian of
∑ₘ μₘ z_m is [[0, Λ], [Λᵀ, 0]] for the Hankel matrix Λ = (μ (i + j)).
Blocks of [[0, Λ], [Λᵀ, 0]] #
The block rank. If Λ is totally regular, the block of [[0, Λ], [Λᵀ, 0]] with rows
X and columns Xᶜ has rank at least min(|X ∩ x|, |Xᶜ ∩ y|) + min(|X ∩ y|, |Xᶜ ∩ x|).
A generic totally regular Hankel matrix #
A strictly monotone permutation of Fin k is the identity.
Increasing minors. For increasing rows r and columns c, the minor of
(t ^ ((i + j)²)) has the monomial t ^ ∑ₐ (r a + c a)² with coefficient one.
Every square minor of (t ^ ((i + j)²)) over K[X] is nonzero.
A generic totally regular Hankel matrix. Over the rational functions K(t), in every
characteristic, the Hankel matrix (t ^ ((i + j)²)) is totally regular.
Counting the two halves #
The cut bound #
The cut bound for formal computation. If a program with polynomial gates over any field
carries the outputs of polynomial multiplication, every split S is crossed by at least
min(|X_S ∩ x|, |X_T ∩ y|) + min(|X_S ∩ y|, |X_T ∩ x|) signals: apply the Hessian consequence
of the Taylor cut lemma over K(t) with the weights t ^ (m²).
The cut bound over ZMod q, for arbitrary gates. If a program over ZMod q, q > 2n
prime, with arbitrary gate functions computes polynomial multiplication, every split S is
crossed by at least min(|X_S ∩ x|, |X_T ∩ y|) + min(|X_S ∩ y|, |X_T ∩ x|) signals: the weighted
sum ∑ₘ zₘ / (m + 2) = xᵀ Λ y with the Hankel Cauchy matrix Λ has vanishing mixed second
differences on every class, so the counting rank-cut bound applies.
One component #
All inputs lie in one component. If every split satisfies the cut bound, the component of the first input contains every input: it is crossed by no signal.
The finite bound #
The prefix argument. If all inputs lie in one component and every split holding exactly
k ≥ 1 inputs is crossed by at least β signals, then
β ≤ (A + η) (s - N)⁺ + 3 log₂ (N + 3 s) + C.
The finite bound for polynomial multiplication. If every split of a fan-in-two program
with the 2n inputs of polynomial multiplication satisfies the cut bound, then under the
graph-ordering hypothesis n ≤ (A + η) (s - 2n)⁺ + 3 log₂ (2n + 3 s) + C.
Asymptotics #
The asymptotic bound. If the graph-ordering hypothesis holds with coefficient A > 0 for
every positive slack, then for every ε > 0 and all large n, every size s satisfying the
finite bound for every ordering has s > (2 + 1/A - ε) n.