Lower bounds for quadratic forms #
Let a circuit over a finite field F, over any signature whose gates have at most two arguments
(so any functions F × F → F, unary functions and constants are allowed, which covers arithmetic
circuits over F), compute the quadratic form x ↦ xᵀ M x (quadForm) of an N × N matrix
M, with one output. Write H = M + Mᵀ.
The rank-cut bound (blockRank_add_transpose_le). Split the wires into S and its
complement T, with forward signals A, backward signals B, and inputs X_S and X_T on
the two sides. Then rank H[X_S, X_T] ≤ |A| + |B|, wherever the output lies. The inputs with a
fixed boundary key form a product P_S × P_T of left and right parts (SingleCut). On such a
class the output depends on one side only (SingleCut.trace_mix), so the mixed second
difference f(x_S, x_T) - f(x'_S, x_T) - f(x_S, x'_T) + f(x'_S, x'_T) vanishes
(trace_add_trace_eq_trace_mix_add_trace_mix); for a quadratic form it is the cross term
(x_S - x'_S)ᵀ H[X_S, X_T] (x_T - x'_T) (quadForm_add_quadForm_eq). So the difference spaces
D_S and D_T of the two parts are orthogonal through H[X_S, X_T], which forces
dim D_S + dim D_T ≤ N - rank H[X_S, X_T] (card_mul_card_le_of_dotProduct_mulVec_eq_zero,
via Sylvester's rank inequality). Every class thus has at most |F| ^ (N - r) inputs, and there
are at most |F| ^ (|A| + |B|) classes. The argument only uses that the mixed second
difference vanishes, so it applies verbatim to a circuit with several outputs whose combination
∑ o, coeff o · f_o is a quadratic form (blockRank_add_transpose_le_of_sum): the difference
vanishes on every class for each output wire, hence for the combination.
The finite bound (half_le_of_quadForm). If H is totally regular, then with the
graph-ordering hypothesis for coefficient A, slack η and constant C, a circuit of size s
has ⌊N/2⌋ ≤ (A + η) (s - N)⁺ + 3 log₂ (N + 3 s) + C. The component of an input wire is closed,
hence crossed by no signal, so the rank-cut bound and total regularity put every input into it
(input_mem_component_of_quadForm). Along the ranking of MultiOutput.exists_rank, the prefix
ending at a suitable input holds exactly ⌊N/2⌋ inputs, so it is crossed by at least
rank H[X_S, X_T] ≥ min (⌊N/2⌋, ⌈N/2⌉) = ⌊N/2⌋ signals, and it is charged to the component
holding all N inputs.
The asymptotic bound (eventually_lt_size_of_quadForm). 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 (1 + 1/(4 κ_E) - ε) N gates, the
coefficient being 1 + π/(6 arccos((1 + 2√2)/4)) ≈ 2.7812; as 2 κ_E ≤ 9/32, also more than
(25/9 - ε) N gates (eventually_lt_size_of_quadForm_twentyFive_div_nine). The threshold
depends only on ε, not on the field, the matrix or the signature.
An explicit family (eventually_lt_size_hankelCauchyZMod). Over ZMod q for a prime
q > 2 N, the Hankel Cauchy matrix hankelCauchyZMod q N with entries 1 / (i + j + 2) is the
Cauchy matrix with nodes x i = i + 1 and y j = -(j + 1), hence totally regular, and it is
symmetric; as q is odd, H = 2 M is totally regular too
(totallyRegular_hankelCauchyZMod_add_transpose). Every fan-in-two circuit over ZMod q
computing its quadratic form has more than (25/9 - ε) N gates for large N.
The mixed second difference #
The mixed second difference vanishes on a class. If two inputs have the same boundary
key for a split S, the values of any wire at the two inputs sum to its values at the two
mixed inputs.
The mixed second difference of a quadratic form is the cross term
(x_S - x'_S)ᵀ (M + Mᵀ)[X_S, X_T] (x_T - x'_T).
The rank-cut bound #
The product-class bound. If (l - l')ᵀ B (r - r') = 0 for all l, l' ∈ L and
r, r' ∈ R, then |L| |R| ≤ |F| ^ (|ι| + |κ| - rank B).
The rank-cut bound for quadratic forms, for a program. If the wire out of a program
carries the quadratic form of M, every split S has rank (M + Mᵀ)[X_S, X_T] ≤ |A| + |B|.
The rank-cut bound for quadratic forms with vanishing mixed second differences. If the
quadratic form of M satisfies q x + q x' = q (mix S x x') + q (mix S x' x) whenever x and
x' have the same boundary key for the split S of a program over a finite field (as the value
of every wire does, by trace_add_trace_eq_trace_mix_add_trace_mix, and so does every linear
combination of wire values), then rank (M + Mᵀ)[X_S, X_T] ≤ |A| + |B|.
The rank-cut bound for quadratic forms. If a circuit with values in a finite field, over
any signature, computes the quadratic form x ↦ xᵀ M x, then every set S of its wires has
rank (M + Mᵀ)[X_S, X_T] ≤ |A| + |B|, where X_S and X_T are the inputs in S and outside
S, and A and B the forward and backward signals of S.
The rank-cut bound for a combination of outputs, for a program. If the combination
∑ o, coeff o · out o of output wires of a program carries the quadratic form of M, every
split S has rank (M + Mᵀ)[X_S, X_T] ≤ |A| + |B|.
The rank-cut bound for a combination of outputs. If a circuit with values in a finite
field, over any signature, computes f with several outputs and the combination
x ↦ ∑ o, coeff o · f x o is the quadratic form of M, then every set S of its wires has
rank (M + Mᵀ)[X_S, X_T] ≤ |A| + |B|.
All inputs lie in one component. If a circuit computes the quadratic form of M and
M + Mᵀ is totally regular, the component of any input wire contains every input.
Symmetric totally regular matrices #
Doubling a symmetric totally regular matrix. If M is symmetric and totally regular and
2 ≠ 0 in F, then M + Mᵀ = 2 M is totally regular.
The symmetrized Hankel Cauchy matrix is totally regular over ZMod q for a prime
q > 2 N.
The finite bound #
The finite bound for quadratic forms. If a circuit over a finite field, over any
signature with fan-in at most two, computes the quadratic form of an N × N matrix M with
M + Mᵀ totally regular, then under the graph-ordering hypothesis
⌊N/2⌋ ≤ (A + η) (s - N)⁺ + 3 log₂ (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 computing the quadratic form of an
N × N matrix M with M + Mᵀ totally regular has more than (1 + 1/(2A) - ε) N gates.
Quadratic forms need (1 + 1/(4 κ_E) - ε) N gates. For every ε > 0 and all large N,
every circuit over a finite field, over any signature with fan-in at most two, computing the
quadratic form of an N × N matrix M with M + Mᵀ totally regular has more than
(1 + 1/(4 κ_E) - ε) N gates, where κ_E = Gaussian.frontierCoefficient; the coefficient is
1 + π/(6 arccos((1 + 2√2)/4)) ≈ 2.7812.
Quadratic forms need (25/9 - ε) N gates.
The explicit family needs (25/9 - ε) N gates. For every ε > 0 and all large N,
for every prime q > 2 N, every circuit over ZMod q, over any signature with fan-in at most
two, computing the quadratic form x ↦ xᵀ (1 / (i + j + 2)) x of hankelCauchyZMod q N has
more than (25/9 - ε) N gates.