← All papers
First page of An $n^2\log\log n$ Lower Bound for Permanent Circuits with Valid Division

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

Jizhou Guo

cs.CC Aug 26, 2026 · v2 math.AG
Rebuilds a third-party OpenAI Lean 4/Mathlib development and restates twelve of its declarations, checking types and axioms, to derive a permanent slice.
We record lower bounds for permanent circuits with valid division over characteristic zero, counting nonscalar multiplications and divisions while additions and scalar operations are free. Chapter 5 of OpenAI's Ten Advances supplies the block construction and critical-locus estimate; these, with the parameter choice made here and the classical bounds of Strassen and Baur-Strassen, give liminf as n tends to infinity of L_div(per_n)/(n^2 log_2 log_2 n) >= 1/12. Our finite-parameter refinement for matching-minor polynomials observes that the coefficient vector at deletion size h lies in a space of dimension at most min{binom(t,h), binom(t,d-h)}. Twelve machine-checked declarations of the Lean development accompanying OpenAI's manuscript on border determinantal complexity of the permanent (September 24, 2026) imply, by a short written argument, the existence of a geometric slice; a further written, unformalized application of the same criterion gives L_div(per_n) >= (n^2/119790) log_2(n/44) for n >= 1936. Assuming Proposition 7.3 of that manuscript gives the bound (n^2/86400) log_2(n/48) for n >= 1408. These are order-of-growth results; the elementary Hessian bound n^2/2 is larger at practical orders.

The paper seeks lower bounds on the nonscalar complexity of computing the permanent with circuits that allow valid divisions over characteristic-zero fields. Earlier n^2 log log n bounds from OpenAI's Ten Advances (Chapter 5) were stated only for division-free circuits.

It combines Chapter 5's block construction and critical-locus estimates with Strassen's degree bound and Baur–Strassen differentiation, which together give a gradient-graph criterion valid with division. A refined coefficient-space bound for matching-minor polynomials improves the finite parameters. Separately, twelve declarations from OpenAI's Lean development on border determinantal complexity were rebuilt with Lean 4.34.1 and Mathlib. Each was restated in its own file, closed with `exact`, and checked with `#print axioms`. A written, unformalized argument then derives a smooth permanent slice from these declarations.

The asymptotic bound is liminf L_div(per_n)/(n^2 log2 log2 n) >= 1/12. From the slice there are explicit bounds: L_div(per_n) >= (n^2/119790) log2(n/44) for n >= 1936, and (n^2/86400) log2(n/48) for n >= 1408 assuming Proposition 7.3 of OpenAI's manuscript. The refined coefficient space also improves the finite-n constants.

nfull 2^t-1truncated T_{t,d}refined R_{t,d}
2^160.1314110.1489710.189746
2^320.1893400.2153180.263163
Optimized block bound divided by n^2, by coefficient budget