A short proof of a quadratic lower bound on the border determinantal complexity of x1n+⋯+xnn over ℂ: A simple human exposition
Abstract
I give a short proof that the border determinantal complexity of Fn=x1n+⋯+xnn over ℂ is at least (n−1)2/(4e), and at least (n−1)2/(2e) in the symmetric model. The same argument shows that the border determinantal complexity of x1d+⋯+xNd is Θ(Nd) for all N≥3 and d≥2. The earlier article arXiv:2606.13628, by the same author, introduced the first superlinear lower bounds and includes verification by Lean formalization. However, the AI written exposition was hard to follow. Kumar and Volk (arXiv:2609.34462) give a short proof of the exact ordinary case, but do not address the border or symmetric cases. In this article, I provide a greatly simplified exposition of the border and symmetric cases, using the implicit function theorem and an explicit section of simple solutions in place of the conormal specialization arguments of arXiv:2606.13628. I choose an explicit polynomial system with n(n−1)n−2 simple solutions for Fn. I then use the implicit function theorem to ensure that each point persists under small perturbations. Finally, kernel equations and the multihomogeneous Bézout theorem bound the number of these points for a small determinant. The exposition is due to the human author. The mathematical simplification was obtained in discussion with ChatGPT Astra and refined in conversation with Claude Opus 5.5.
Related
- A Quadratic Lower Bound on Determinantal Complexity
- Asymptotics of Masur-Veech volume of strata of quadratic differentials with many simple poles
- A Simple Complexity Lower Bound for Solving Ax=b
- The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients
- Non-Terminal Complexity of Simple Semi-Conditional Grammars
BibTeX
@misc{sheshadri2026short,
title = {{A short proof of a quadratic lower bound on the border determinantal complexity of $x_1^n+\cdots+x_n^n$ over $\mathbbC$: A simple human exposition}},
author = {Karthik Sheshadri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.11090},
eprint = {2606.11090},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.11090},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A short proof of a quadratic lower bound on the border determinantal complexity of x_1^n+⋯+x_n^n over ℂ: A simple human exposition
AU - Karthik Sheshadri
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2606.11090
UR - https://arxiv.org/abs/2606.11090
AB - I give a short proof that the border determinantal complexity of F_n=x_1^n+⋯+x_n^n over ℂ is at least (n−1)^2/(4e), and at least (n−1)^2/(2e) in the symmetric model. The same argument shows that the border determinantal complexity of x_1^d+⋯+x_N^d is Θ(Nd) for all N≥3 and d≥2. The earlier article arXiv:2606.13628, by the same author, introduced the first superlinear lower bounds and includes verification by Lean formalization. However, the AI written exposition was hard to follow. Kumar and Volk (arXiv:2609.34462) give a short proof of the exact ordinary case, but do not address the border or symmetric cases. In this article, I provide a greatly simplified exposition of the border and symmetric cases, using the implicit function theorem and an explicit section of simple solutions in place of the conormal specialization arguments of arXiv:2606.13628. I choose an explicit polynomial system with n(n−1)^n−2 simple solutions for F_n. I then use the implicit function theorem to ensure that each point persists under small perturbations. Finally, kernel equations and the multihomogeneous Bézout theorem bound the number of these points for a small determinant. The exposition is due to the human author. The mathematical simplification was obtained in discussion with ChatGPT Astra and refined in conversation with Claude Opus 5.5.
ER -