← All papers
First page of A fully Lean-verified quadratic lower bound on the border determinantal complexity of $x_1^n+\cdots+x_n^n$ over $\mathbb{C}$, including the symmetric and exact models

A fully Lean-verified quadratic lower bound on the border determinantal complexity of $x_1^n+\cdots+x_n^n$ over $\mathbb{C}$, including the symmetric and exact models

Karthik Sheshadri

cs.CC Jun 11, 2026 · v3
All four determinantal complexity lower bounds for the Fermat power sum are verified end-to-end in Lean 4 with Mathlib, using only the standard axioms.
We present the first end-to-end Lean-verified superlinear lower bound on border determinantal complexity. Let $F_n=x_1^n+\cdots+x_n^n$. We prove, over $\mathbb{C}$, that the border determinantal complexity of $F_n$ is at least $(n-1)^2/(4e)$ and its symmetric border determinantal complexity is at least $(n-1)^2/(2e)$; the same bounds therefore hold for exact determinantal complexity. Together with known $O(n^2)$ constructions, both border quantities are $Θ(n^2)$. The proof compares one enumerative invariant on two sides of a degeneration. On the determinant side, the $(n-2)$nd multidegree of the multiplicity-one Gauss graph of any size-$m$ affine-linear determinant is bounded by an explicit multihomogeneous Bézout number; no smoothness, irreducibility, or squarefreeness is assumed. On the target side, a flat limit of these effective Gauss-graph cycles contains the conormal variety of the projective Fermat cone, whose relevant multidegree is the classical dual degree $n(n-1)^{n-2}$. Effectivity gives the inequality in the correct direction, and an $(n-1)$st root yields the quadratic bound. All four bounds are fully verified in Lean 4 with Mathlib. The Lean theorems assume only $n\ge 3$ and a literal determinantal representation or literal border membership, and depend on no axioms beyond Lean's foundational ones. The formal proof follows a localized version of the argument presented here: where the text compares global cycles, it compares local intersection lengths of finite slices of those cycles. Lean sources: https://github.com/karthik202321/power-sum-dc-lean; archived release: https://doi.org/10.5281/zenodo.23274251

Lower bounds on determinantal complexity for explicit polynomials have stayed close to linear. The goal is a quadratic lower bound on the border (and symmetric border) determinantal complexity of the power sum F_n = x_1^n + ... + x_n^n over C. Known constructions give O(n^2).

The proof compares the multidegree δ_{n-2} on two sides of a degeneration. On the determinant side, the multidegree of the multiplicity-one Gauss graph of any size-m affine-linear determinant is bounded by a multihomogeneous Bézout number, obtained via kernel lifts. On the target side, a flat limit of these effective Gauss-graph cycles contains the conormal variety of the Fermat cone, whose multidegree is the dual degree n(n-1)^{n-2}. The Lean formalization follows a localized version of the argument, comparing local intersection lengths of finite slices instead of global cycles.

For n ≥ 3 the border determinantal complexity is at least (n-1)^2/(4e) and the symmetric border determinantal complexity is at least (n-1)^2/(2e). The same bounds hold for the exact models, so both border quantities are Θ(n^2). All bounds are fully verified in Lean 4 with Mathlib, depending only on propext, Classical.choice and Quot.sound.