Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
Addressing an unverifiable claim from a recent AI-authored paper, this work provides a short, rigorous proof establishing an $\Omega(n^2)$ lower bound on the determinantal complexity of the power sum polynomial $\sum_{i=1}^n x_i^n$ over $\mathbb{C}$. Determining super-linear determinantal complexity lower bounds for explicit polynomials is a longstanding challenge in algebraic complexity theory closely linked to Valiant's VP vs. VNP conjecture. The result succeeds in establishing the first human-verifiable quadratic lower bound for this fundamental algebraic benchmark using a transparent and nearly self-contained argument.
Replacing an impenetrable AI-generated proof that stumped theorists, this short note establishes the first verified $\Omega(n^2)$ determinantal complexity lower bound for an explicit polynomial.
We prove an $Ω(n^2)$ lower bound on the determinantal complexity of the power sum polynomial $\sum_{i=1}^n x_i^n$ over the field of complex numbers. A similar result was claimed in a recent paper of Sheshadri (arXiv:2606.13628), via an AI-assisted and AI-written proof. Assuming its correctness, this was the first super-linear lower bound for this fundamental algebraic problem for any explicit polynomial. However, the authors of this note were unable to follow the details and verify the argument in arXiv:2606.13628, in spite of considerable effort on their part. The proof we provide here is short, (almost) self-contained and seemingly simpler.