An n2loglog n Lower Bound for Permanent Circuits with Valid Division
Abstract
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.
Related
- An Exponential Lower Bound for the Permanent of Random Bernoulli Matrix
- Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries
- A rank bound for bases and circuits in binary matroids
- An explicit lower bound for the unit distance problem
- Optimizing Explicit Unit-Distance Lower-Bound Certificates
BibTeX
@misc{guo2026n2loglog,
title = {{An $n^2\log\log n$ Lower Bound for Permanent Circuits with Valid Division}},
author = {Jizhou Guo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.29568},
eprint = {2609.29568},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29568},
}
RIS
TY - UNPB
TI - An n^2loglog n Lower Bound for Permanent Circuits with Valid Division
AU - Jizhou Guo
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2609.29568
UR - https://arxiv.org/abs/2609.29568
AB - 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.
ER -