Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-263 | 20th October 2026 05:08

A short proof of a quadratic lower bound on the border determinantal complexity of the power sum polynomial over C: A simple human exposition

RSS-Feed




TR26-263
Authors: Karthik Sheshadri
Publication: 20th October 2026 07:47
Downloads: 84
Keywords: 


Abstract:

I give a short proof that the border determinantal complexity of F_n = x_1^n + ... + x_n^n over C 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 Theta(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.



ISSN 1433-8092 | Imprint