Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 1 min ago
PreprintarXiv licencearXiv

A Quadratic Lower Bound on Determinantal Complexity

  • Mrinal Kumar
  • Ben Lee Volk
Open at sourcePDFDOICite

Abstract

We prove an Ω(n2) lower bound on the determinantal complexity of the power sum polynomial ∑i=1n xin 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.

Related

  1. A short proof of a quadratic lower bound on the border determinantal complexity of x1n+⋯+xnn over ℂ: A simple human exposition
    Karthik Sheshadri
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
    Santosh S. Vempala
    arXivPreprintarXiv licenceFull textAnalysis & PDEsOptimisation & controlarXiv
  3. A near-quadratic lower bound for the Brown--Erdős--Sós (9,6)-problem
    Xiangliang Kong, Chong Shangguan, Xin Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A Universal Lower Bound for the Complexity of Gaussian-Divisible Spin Glasses
    Pax Kivimae, Benjamin McKenna
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv
  5. A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
    Yoshiteru Ishida
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{kumar2026quadratic,
  title = {{A Quadratic Lower Bound on Determinantal Complexity}},
  author = {Mrinal Kumar and Ben Lee Volk},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.34462},
  eprint = {2609.34462},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.34462},
}
RIS
TY  - UNPB
TI  - A Quadratic Lower Bound on Determinantal Complexity
AU  - Mrinal Kumar
AU  - Ben Lee Volk
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.34462
UR  - https://arxiv.org/abs/2609.34462
AB  - We prove an Ω(n^2) lower bound on the determinantal complexity of the power sum polynomial ∑_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.
ER  -