Proofs for quadratic forms #
- Sylvester's rank inequality (
rank_add_rank_le_rank_mul_add_card):rank B + rank V ≤ rank (B V) + width B, by rank–nullity forBrestricted to the column space ofV. - The product-class bound (
card_mul_card_le_of_dotProduct_mulVec_eq_zero): if(l - l')ᵀ B (r - r') = 0onL × R, letVhave the columnsr - r₀. ThenRembeds in the column space ofV, and the differencesl - l₀lie in the kernel of(B V)ᵀ, so|L| |R| ≤ |F| ^ (|ι| - rank (B V) + rank V) ≤ |F| ^ (|ι| + |κ| - rank B). - The mixed second difference (
trace_add_trace_eq_trace_mix_add_trace_mix,quadForm_add_quadForm_eq): by cut and paste, mixing two inputs with equal boundary keys only swaps the output values; writing each input as the sum of its parts onX_SandX_T(mix S x 0 + mix S 0 x), bilinearity leaves only the cross terms of the quadratic form. - The rank-cut bound (
blockRank_add_transpose_le): on a class of equal boundary keys, mixing two members realizes any left part with any right part (SingleCut.mix_mem_filter), so the parts satisfy the hypothesis of the product-class bound; summing over the at most|F| ^ (|A| + |B|)classes and comparing exponents givesrank ≤ |A| + |B|. Only the vanishing of the mixed second difference is used (blockRank_add_transpose_le_of_mix), so the bound also holds when a combination of several output wires is the quadratic form (blockRank_add_transpose_le_of_sum). - Symmetric Cauchy matrices (
totallyRegular_hankelCauchyZMod_add_transpose):M + Mᵀ = 2 Mfor symmetricM, and scaling a square block by2 ≠ 0keeps it nonsingular. - The finite bound (
half_le_of_quadForm_rank_cuts, for any field given the rank-cut bound at every split, andhalf_le_of_quadForm): the component of an input wire is closed, so the rank-cut bound and total regularity put every input into it (input_mem_component_of_quadForm). Along the ranking ofMultiOutput.exists_rank, the number of inputs in a prefix grows by at most one per wire, so the prefix ending at some input holds exactly⌊N/2⌋inputs; it is crossed by at least⌊N/2⌋signals and charged to the component holding all inputs. - The asymptotic bound (
eventually_lt_size_of_quadForm_of_orderingBound): assume at most(1 + 1/(2A) - ε) Ngates and chooseη = A² ε; the cycle term is then at most(1/2 - A ε/2) N, and the logarithmic term isO(log N).
Linear algebra #
Sylvester's rank inequality. For a matrix B with columns indexed by κ and a matrix
V with rows indexed by κ, rank B + rank V ≤ rank (B V) + |κ|.
A submodule of a finite space over a finite field has |F| ^ finrank elements.
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 mixed second difference #
Values on a class are additive under mixing. If two inputs have the same boundary key, the values of any wire at the two inputs sum to its values at the two mixed inputs: the mixed second difference vanishes.
The mixed second difference of a quadratic form is the bilinear cross term
(x_S - x'_S)ᵀ (M + Mᵀ)[X_S, X_T] (x_T - x'_T).
The rank-cut bound for quadratic forms #
Classes are isotropic. If the quadratic form of M is additive under mixing inputs with
equal boundary keys, then on the inputs with a given key any two left parts and any two right
parts satisfy (l - l')ᵀ (M + Mᵀ)[X_S, X_T] (r - r') = 0.
Classes are isotropic. On the inputs with a given boundary key, any two left parts and
any two right parts satisfy (l - l')ᵀ (M + Mᵀ)[X_S, X_T] (r - r') = 0, when a wire carries
the quadratic form of M.
The rank-cut bound for quadratic forms additive under mixing. If the quadratic form of
M is additive under mixing inputs with equal boundary keys for the split S, then
rank (M + Mᵀ)[X_S, X_T] ≤ |A| + |B|.
The rank-cut bound for quadratic forms. If the wire out of a program over a finite
field carries the quadratic form of M, then every split S has
rank (M + Mᵀ)[X_S, X_T] ≤ |A| + |B|.
The rank-cut bound for a combination of outputs. If the combination
∑ o, coeff o · out o of output wires of a program over a finite field is the quadratic form of
M, then every split S has rank (M + Mᵀ)[X_S, X_T] ≤ |A| + |B|: the mixed second difference
vanishes on every class for each output wire, hence for the combination.
Symmetric totally regular matrices #
If M is symmetric and totally regular and 2 ≠ 0, 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: it is twice a symmetric totally regular matrix, and 2 ≠ 0 as q is odd.
The finite bound #
All inputs lie in one component. If M + Mᵀ is totally regular and every split of a
program obeys the rank-cut bound for M + Mᵀ, the component of an input wire contains every
input: it is closed, hence crossed by no signal, so its inputs form a block of rank zero.
The finite bound from rank cuts. A fan-in-two program over any signature and any field
whose splits all obey the rank-cut bound for M + Mᵀ, with M + Mᵀ totally regular, has
⌊N/2⌋ ≤ (A + η) (s - N)⁺ + 3 log₂ (N + 3 s) + C.
All inputs lie in one component. If M + Mᵀ is totally regular, the component of an
input wire contains every input: it is closed, hence crossed by no signal, so by the rank-cut
bound its inputs form a block of rank zero.
The finite bound for quadratic forms. A fan-in-two program over any signature whose
wire out carries the quadratic form of M, with M + Mᵀ totally regular, has
⌊N/2⌋ ≤ (A + η) (s - N)⁺ + 3 log₂ (N + 3 s) + C.
Asymptotics #
The asymptotic bound from rank cuts. 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 single-output circuit over any field whose splits obey the rank-cut bound for a
totally regular M + Mᵀ has more than (1 + 1/(2A) - ε) N gates.
The asymptotic bound for quadratic forms with a general ordering coefficient.