An $n^2\log\log n$ Lower Bound for Permanent Circuits with Valid Division

1. Introduction

• The lower bound has order n^2 log log n for valid-division circuits, with leading constant 1/12.This extends the division-free lower-bound order described in the introduction.Source: §1 · p. 1
• The complexity model counts nonscalar multiplications and valid divisions at unit cost, while additions and scalar operations are free.The stated setting is characteristic zero.Source: §1 · pp. 1–2
• The matching-minor critical-locus bound uses R_t,d, the exact sum of ranks of disjointness incidence matrices, instead of the full family of nonempty row-subset parameters.M_t,s,d is the sum of all size-d permanental minors of a t × s variable matrix.Source: §1 · p. 2
• A circuit-dependent transverse deformation preserves the finite gradient slice and places it inside the regular locus of the rational gate graph despite poles at the original specialization.The finite family preserves the special fiber’s length, and a norm argument makes divisors units on the generic formal fiber.Source: §1 · p. 2

2. Preliminaries

• Over an algebraically closed characteristic-zero field, the complexity measure counts nonscalar multiplications and divisions, while additions and scalar operations are free.Source: §2 · p. 3

2.1. Matching-minor polynomials.

• A matching-minor polynomial is the weight enumerator of size-d matchings in the complete bipartite graph associated with a variable matrix.Source: §2.1 · p. 3

2.2. Projective avoidance.

• When dim Crit(P) ≤ Δ, projective avoidance yields a k-variable projected gradient whose zero fiber is only the origin and has length (d−1)^k, for k ≤ m−Δ.The components have common degree d−1 and form a homogeneous system of parameters.Source: §2.2 · p. 3

2.3. Rational differentiation.

• Baur–Strassen differentiation computes all first derivatives of a valid rational circuit of nonscalar cost L with cost at most 3L.The gate-by-gate accounting gives three nonscalar operations for either multiplication or division, with additions and scalar operations free.Source: §2.3 · p. 4

3.1. A column-deletion recurrence.

• Splitting matchings according to whether they use a given column gives a deletion recurrence, whose operator form is nilpotent on the finite degree range.Source: §3.1 · p. 4

3.2. The shared coefficient spaces.

• At deletion size h, the equations depend on shared coefficients formed by summing weights of matchings with specified row sets.Source: §3.2 · p. 4
• The shared coefficient vectors lie in images of disjointness matrices; Gottlieb’s maximal-rank theorem determines these ranks in characteristic zero.Source: §3.2 · pp. 4–5
• Using rank-many abstract coordinates to reconstruct deletion vectors gives equations whose solutions map onto the critical scheme of the matching-minor polynomial.Source: §3.2 · p. 5
• Filtering the resulting algebra reduces the relevant variables to finitely many monomials, yielding finiteness over the coefficient ring.Source: §3.2 · p. 5
• For disjoint variable blocks, the critical scheme is the product of the summands’ critical schemes, so their dimensions add.Source: §3.2 · p. 5

• The block construction partitions the rows into size-t blocks and uses a primitive dth root of unity to form a constant matrix with nonzero coefficients.Source: §4 · p. 6
• The block-specialization proposition asserts the existence of nonzero coefficients λ1,…,λb for the construction.Source: §4 · p. 6
• For a matrix A, the coefficient of zK in the product of its column forms is the permanent of the submatrix on rows K.Source: §4 · p. 6
• The constructed minors vanish unless the omitted d rows lie in one block; in that case the minor equals λh(t−d)!(t!)^(b−1).Source: §4 · p. 6

• For parameters with k=m−Δ>0, linear maps W and Q define a projected gradient H0(x)=Q∇P(Wx).Source: §5 · p. 7
• The zero fiber of H0 consists only of the origin and has length (d−1)^k.Source: §5 · p. 7
• The projected-gradient expression is the interface between the geometric construction and an arbitrary circuit for the permanent.Source: §5 · p. 7

Pole avoidance

• A transverse direction A makes every numerator and denominator representing a differentiated-circuit divisor input remain nonzero after specialization.The choice avoids the finitely many hypersurfaces defined by the first nonzero Taylor forms at B.Source: §6 · p. 7

Formal deformation

• The deformed polynomial map reduces to H0 modulo ε and is computed with at most 3LC nonlinear gates.The construction transfers the gradient slice to the specialized rational gradient circuit.Source: §6 · pp. 7–8

Pole avoidance

• Every nonzero numerator or denominator supplied by the transverse-direction lemma is a unit in the generic finite algebra TK.Multiplication by such an element is injective on finite free T, so its determinant is nonzero and invertible over K.Source: §6 · p. 8

Conserved finite fiber

• The local map T over S is finite free of rank (d −1)k, equal to the closed fiber’s length.Finiteness and flatness yield finite freeness; the rank is preserved from the closed fiber.Source: §6 · p. 8
• The argument preserves the local finite length even if Hε has higher degree in x than H0.Only branches specializing to the origin are retained; additional global branches do not affect the lower bound.Source: §6 · p. 8

Generic fiber

• The coordinates of Hε are algebraically independent over F((ε)), so Hε is dominant and generically finite.A polynomial relation would reduce modulo ε to a nonzero relation among the coordinates of the finite map H0.Source: §7 · pp. 8–9
• The finite algebra TK is a length-(d −1)k quotient of the global generic fiber and contributes that many isolated geometric points.In characteristic zero the zero-dimensional generic fiber is reduced after extending to an algebraic closure.Source: §7 · p. 9

Rational gate graph

• Since every divisor input is a unit on the quotient, each point lifts gate by gate to the rational gate graph.Multiplication and division gates give quadratic equations, while the k output-fixing equations are affine.Source: §7 · p. 9

Bézout bound

• With at most 3LC nonlinear gates, affine Bézout bounds the isolated points by the product of the gate-equation degrees.Taking base-two logarithms yields the bound used to prove Theorem 1.2.Source: §7 · p. 9

Parameter choice

• log2(d−1) = (1−o(1)) log2 log2 n after subtracting a log2 log2 log2 n term and O(1).The expansion is log2(d−1) = log2 log2 n−log2 log2 log2 n−O(1).Source: §8 · p. 10

Final bound

• Substituting the parameter relations and logarithmic estimate into (1.2) proves Theorem 1.1.The selected parameters satisfy n = bt + s −d and the hypotheses of Theorem 1.2.Source: §8 · pp. 9–10

Concluding remarks

• The 1/12 constant comes from retaining (1/4 −o(1))n2 variables and rational Baur–Strassen’s factor of 1/3.Formal deformation preserves the finite geometric multiplicity despite poles.Source: §9 · p. 10
• A larger asymptotic order would require substantially higher degree with a quadratic-dimensional finite slice, or an invariant beyond the single-gradient-fiber architecture.Source: §9 · p. 10