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

Abstract

We prove an $n^2\log\log n$ lower bound for rational arithmetic circuits computing the permanent over characteristic zero. Additions and scalar operations are free, while every nonscalar multiplication or valid division has unit cost. If $L_{\mathrm{div}}(\mathrm{per}_n)$ denotes the resulting complexity, then $\liminf_{n\to\infty} L_{\mathrm{div}}(\mathrm{per}_n)/(n^2\log_2\log_2 n)\ge 1/12$. The proof refines the critical-locus method for the permanent in two ways. First, a column-deletion recurrence and the maximal-rank theorem for inclusion matrices compress the shared coefficient space in the critical equations of the matching-minor polynomial. Second, a circuit-dependent formal deformation transfers the resulting finite gradient slice through an arbitrary valid division circuit. Finite flatness preserves the length of the special fiber, while a norm argument makes every divisor a unit on the generic formal fiber. Rational Baur--Strassen differentiation and affine B\'ezout then give the lower bound with the stated constant.