Lower bounds for totally regular linear maps #
A matrix is totally regular when every square submatrix is nonsingular (TotallyRegular).
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), compute the linear
map x ↦ M x for a totally regular N × N matrix M.
The finite bound (sub_one_le_of_totallyRegular). With the graph-ordering hypothesis for
coefficient A, slack η and constant C, a circuit of size s has
N - 1 ≤ (A + η) (s - N)⁺ + 3 log₂ (N + 3 s) + C.
The proof combines the two halves of the cut method. The ordering transfer
(MultiOutput.exists_rank) ranks the wires so that every prefix is crossed by few signals, and
the rank-cut bound (MultiOutput.blockRank_add_blockRank_le) shows that a prefix holding N
of the 2 N inputs and outputs is crossed by at least
rank M[Y_T, X_S] + rank M[Y_S, X_T] = |X_S| + |Y_S| = N signals, since every block of a totally
regular matrix has full rank (TotallyRegular.min_card_le_blockRank). Inputs and outputs are
counted separately: an output carried by an input wire counts twice, and as distinct outputs
of a totally regular map lie on distinct wires the count grows by at most two per wire, so a
prefix with N or N + 1 of them exists, which costs the - 1. All inputs and outputs lie in
one component of the wire graph (its component is closed, hence uncrossed, so the rank-cut bound
forces every input and output into it), and the prefix is charged to that component.
The asymptotic bound (eventually_lt_size_of_totallyRegular). 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/(2 κ_E) - ε) N gates, the
coefficient being 1 + π/(3 arccos((1 + 2√2)/4)) ≈ 4.5625; as 2 κ_E ≤ 9/32, also more than
(41/9 - ε) N gates (eventually_lt_size_of_totallyRegular_fortyOne_div_nine). The threshold
depends only on ε, not on the field or the signature.
Rectangular totally regular maps (sub_one_le_of_totallyRegular_rect,
eventually_lt_size_of_totallyRegular_rect). When M is an m × N totally regular matrix with
N ≤ m (such as a systematic Reed–Solomon encoding matrix), distinct outputs still lie on
distinct wires for N ≥ 2. Peeling the last gate of the program and at most one output wire
seated on it m - N times reduces the circuit to one of size s - (m - N) computing an N × N
totally regular row-submatrix of M, yielding the finite bound
N - 1 ≤ (A + η) (s - m)⁺ + 3 log₂ (N + 3 s) + C and the asymptotic lower bound
m + (1/(2 κ_E) - ε) N < s (hence m + (32/9 - ε) N < s,
eventually_lt_size_of_totallyRegular_rect_thirtyTwo_div_nine).
An explicit family (totallyRegular_cauchy, eventually_lt_size_cauchyZMod). Cauchy
matrices (1 / (x i - y j)) with distinct nodes are totally regular, as every square submatrix
is again a nonsingular Cauchy matrix. Over ZMod q for a prime q ≥ 2 N, the nodes x i = i
and y j = N + j give the explicit family cauchyZMod q N, and every fan-in-two circuit over
ZMod q computing it has more than (41/9 - ε) N gates for large N (by Bertrand's postulate
such a prime exists for every N ≥ 1).
Prior art. By a counting argument, the graph of a circuit computing a totally regular map is
a superconcentrator, whatever its gate functions (Valiant), and size lower bounds for
superconcentrators bound such circuits. The 5 N-edge lower bound of Lev and Valiant for
superconcentrators is the edge-counting analogue of the cutwidth coefficient κ = 1/6, that
is, of the ordering coefficient A = 1/3 (Multigraph.exists_orderingBound_one_third). Here
gates are counted, and the ordering coefficient is 2 κ_E ≈ 0.2807.
Totally regular matrices #
Blocks of a totally regular matrix have full rank: every block has rank at least the smaller of its dimensions.
Row submatrices of a totally regular matrix are totally regular: any injective selection of rows of a totally regular matrix is totally regular.
Square Cauchy matrices are nonsingular.
Cauchy matrices are totally regular. With distinct nodes x i, distinct nodes y j,
and x i ≠ y j for all i and j, every square submatrix of (1 / (x i - y j)) is
nonsingular.
The explicit Cauchy family is totally regular over ZMod q for a prime q ≥ 2 N.
The finite bound #
The finite bound for totally regular maps. If a circuit over a finite field, over any
signature with fan-in at most two, computes a totally regular linear map on N inputs, then
under the graph-ordering hypothesis N - 1 ≤ (A + η) (s - N)⁺ + 3 log₂ (N + 3 s) + C for its
size s.
The finite bound for rectangular totally regular maps. If a circuit over a finite field,
over any signature with fan-in at most two, computes an m × N totally regular linear map with
N ≤ m, then under the graph-ordering hypothesis
N - 1 ≤ (A + η) (s - m)⁺ + 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 a totally regular map on
N inputs has more than (1 + 1/A - ε) N gates.
Totally regular maps need (1 + 1/(2 κ_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 a
totally regular linear map on N inputs has more than (1 + 1/(2 κ_E) - ε) N gates, where
κ_E = Gaussian.frontierCoefficient; the coefficient is
1 + π/(3 arccos((1 + 2√2)/4)) ≈ 4.5625.
Totally regular maps need (41/9 - ε) N gates.
The asymptotic bound for rectangular totally regular maps 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, for every m ≥ N, every fan-in-two
circuit over a finite field computing an m × N totally regular map has more than
m + (1/A - ε) N gates.
Rectangular totally regular maps need m + (1/(2 κ_E) - ε) N gates. For every ε > 0
and all large N, for every m ≥ N, every circuit over a finite field, over any signature with
fan-in at most two, computing an m × N totally regular linear map has more than
m + (1/(2 κ_E) - ε) N gates, where κ_E = Gaussian.frontierCoefficient.
Rectangular totally regular maps need m + (32/9 - ε) N gates.
The explicit family needs (41/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 x ↦ cauchyZMod q N x has more than (41/9 - ε) N gates.