pith. sign in

arxiv: 2606.13628 · v1 · pith:OVRLD3INnew · submitted 2026-06-11 · 💻 cs.CC

A near-quadratic lower bound on the border determinantal complexity of sum_i x_i^n via conormal specialization

Karthik Sheshadri This is my paper

Pith reviewed 2026-06-27 04:36 UTC · model grok-4.3

classification 💻 cs.CC
keywords border determinantal complexityFermat hypersurfaceconormal varietyGauss graph cyclemultidegree bounddeterminantal complexityalgebraic complexity theoryspecialization argument
0
0 comments X

The pith

The border determinantal complexity of the sum of n nth powers is at least (n-1)^2 over 4e for every n at least 3.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that over the complex numbers the polynomial equal to the sum of the nth powers of n variables cannot be written as the limit of determinants of matrices smaller than roughly (n-1) squared over 4e. The same bound holds in the symmetric model up to a factor of two. The argument first bounds the relevant multidegree of the cycle attached to any determinant by a Bézout count, then shows that any degeneration to the target sum must carry a positive multiple of the conormal cycle of the Fermat cone. Extracting an (n-1)st root of the known dual degree of the Fermat hypersurface then yields the quadratic lower bound. These are the first superlinear lower bounds known for an explicit family in the border determinantal model.

Core claim

For every n greater than or equal to 3, the border determinantal complexity of the sum from i equals 1 to n of x sub i to the n is at least (n minus 1) squared over 4e, while the symmetric border determinantal complexity is at least (n minus 1) squared over 2e. The proof proceeds by establishing an unconditional multihomogeneous Bézout bound on the slot-(n-2) conormal multidegree of the multiplicity-one Gauss-graph cycle of an arbitrary affine-linear determinant, then applying a specialization argument that forces any flat limit along a degeneration to the Fermat sum to contain the conormal variety of the Fermat cone with positive coefficient; a cone-shift identity converts this multidegree

What carries the argument

The slot-(n-2) conormal multidegree of the Gauss-graph cycle of an affine-linear determinant, specialized along any degeneration to the Fermat sum so that it contains the conormal variety of the Fermat cone with positive coefficient.

If this is right

  • The new lower bounds match the known O(n squared) upper bounds up to the constant factor.
  • These are the first superlinear border determinantal lower bounds for any explicit family of polynomials.
  • The exact lower bounds proved in the author's companion manuscripts follow directly as corollaries.
  • The dual degree of the Fermat hypersurface is transferred into a complexity lower bound via the conormal specialization.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same specialization technique could be tested on other explicit polynomials whose dual varieties are known, such as other power-sum forms.
  • Improving the Bézout count on the Gauss-graph cycle would immediately strengthen the quadratic constant.
  • The method shows that algebraic invariants of the target hypersurface can be pulled back to give lower bounds even when the approximating objects are allowed to degenerate.

Load-bearing premise

Along any degeneration of a determinant to the sum of nth powers, the flat limit of the Gauss-graph cycles must contain the conormal variety of the Fermat cone with positive coefficient.

What would settle it

An explicit sequence of matrices of size smaller than (n-1) squared over 4e whose determinants converge to the sum of nth powers, yet whose associated Gauss-graph cycles have zero coefficient on the conormal variety of the Fermat cone in the flat limit.

read the original abstract

The border determinantal complexity $\dcb(f)$ of a polynomial $f$ is the least $m$ such that $f$ is a limit of determinants of $m\times m$ matrices of affine-linear forms. We prove that for every $n\ge3$, over $\CC$, \[ \dcb\Big(\sum_{i=1}^n x_i^n\Big)\ \ge\ \frac{(n-1)^2}{4e}, \qquad \sdcb\Big(\sum_{i=1}^n x_i^n\Big)\ \ge\ \frac{(n-1)^2}{2e} \] in the ordinary and symmetric models respectively; both match the known $O(n^2)$ upper bounds up to the constant. To our knowledge these are the first border determinantal lower bounds for an explicit family that are superlinear in the number of variables: the known quadratic border bound for the permanent reads the \emph{dimension} of the dual variety and is linear in its number of variables, whereas we transfer the dual \emph{degree}. The proof has two ingredients. The first is an unconditional bound on the slot-$(n-2)$ conormal multidegree of the multiplicity-one Gauss-graph cycle of an arbitrary affine-linear determinant -- singular, reducible, and non-reduced fibers allowed -- by a multihomogeneous B\'ezout count of a lifted kernel incidence. The second is a specialization argument: along any degeneration $\det A_c\to\sum_ix_i^n$, the flat limit of these Gauss-graph cycles contains the conormal variety of the Fermat cone with positive coefficient. A cone-shift identity converts that conormal multidegree into the classical dual degree $n(n-1)^{n-2}$ of the smooth Fermat hypersurface, and an $(n-1)$-st root yields the quadratic bound. The exact lower bounds of the author's companion manuscripts follow as corollaries.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper claims to prove near-quadratic lower bounds on border determinantal complexity: for every n≥3 over ℂ, dcb(∑_{i=1}^n x_i^n) ≥ (n-1)^2/(4e) and sdcb(∑_{i=1}^n x_i^n) ≥ (n-1)^2/(2e). These are obtained from an unconditional multihomogeneous Bézout bound on the slot-(n-2) conormal multidegree of the multiplicity-one Gauss-graph cycle of an arbitrary affine-linear determinant, combined with a specialization argument showing that along any degeneration det(A_c) → ∑ x_i^n the flat limit of these cycles contains the conormal variety of the Fermat cone with positive coefficient; a cone-shift identity then converts this to the classical dual degree n(n-1)^{n-2} of the smooth Fermat hypersurface, and an (n-1)st root yields the claimed quadratic bound. The bounds are the first superlinear border determinantal lower bounds for an explicit family.

Significance. If the specialization argument holds, the result is significant: it supplies the first superlinear lower bounds on border determinantal complexity for an explicit family (improving on the linear-in-variables bound obtained from dual-variety dimension for the permanent) while matching the known O(n^2) upper bounds up to a constant factor. The technique of transferring the dual degree via conormal specialization in flat limits is a new contribution to the toolkit for algebraic complexity lower bounds.

major comments (1)
  1. [specialization argument] The specialization step (abstract, second ingredient) asserts that in every flat family det(A_c) → ∑ x_i^n the flat limit of the Gauss-graph cycles contains the conormal variety of the Fermat cone with strictly positive coefficient. This containment is load-bearing: without a positive coefficient the unconditional multidegree bound cannot be transferred to a complexity lower bound. The manuscript must explicitly establish that the coefficient cannot vanish for any degeneration (including singular, reducible, or non-reduced cases) and that the cycle is multiplicity-one in the limit.
minor comments (1)
  1. The abstract states that the exact lower bounds of the companion manuscripts follow as corollaries; a one-sentence indication of the relation between the approximate and exact bounds would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting the significance of the result. We address the single major comment below.

read point-by-point responses

  1. Referee: [specialization argument] The specialization step (abstract, second ingredient) asserts that in every flat family det(A_c) → ∑ x_i^n the flat limit of the Gauss-graph cycles contains the conormal variety of the Fermat cone with strictly positive coefficient. This containment is load-bearing: without a positive coefficient the unconditional multidegree bound cannot be transferred to a complexity lower bound. The manuscript must explicitly establish that the coefficient cannot vanish for any degeneration (including singular, reducible, or non-reduced cases) and that the cycle is multiplicity-one in the limit.

    Authors: Section 4 contains the full specialization argument. It proceeds by first establishing that the Gauss-graph cycle of a generic affine-linear determinant is multiplicity-one, then showing via the definition of flat limit and the incidence geometry of the lifted kernel variety that any flat degeneration to the Fermat sum forces the limit cycle to contain the Fermat conormal variety with positive coefficient. The argument is uniform and does not rely on smoothness or reducedness of the special fiber; the unconditional Bézout bound of the first ingredient is invoked precisely to handle singular/reducible cases. The coefficient is shown to be at least 1 by a direct comparison of the multidegrees before and after specialization. We agree that the non-vanishing claim can be stated more explicitly and will insert a short clarifying paragraph (with a forward reference to the multiplicity-one property) in the revised version. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation uses independent AG tools

full rationale

The paper's claimed lower bound follows from two explicit steps: (1) an unconditional multihomogeneous Bézout count giving a slot-(n-2) conormal multidegree bound that holds for the Gauss-graph cycle of any affine-linear determinant (singular or reducible fibers allowed), and (2) a specialization claim that the flat limit along any det degeneration to the Fermat sum contains the Fermat conormal with positive coefficient, which is then converted via a cone-shift identity to the classical dual degree n(n-1)^{n-2}. Both steps invoke standard, externally verifiable algebraic-geometry statements (Bézout, flat limits, conormal varieties) whose statements do not presuppose the target complexity bound or any fitted parameter. No equation reduces the final quadratic expression to a self-definition, a renamed fit, or a load-bearing self-citation; companion manuscripts are invoked only for corollaries. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on standard results from algebraic geometry (Bézout theorem, properties of conormal varieties and flat limits) that are not derived in the paper; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • standard math Bézout theorem applies to the lifted kernel incidence variety in the multihomogeneous setting
    Invoked to bound the slot-(n-2) conormal multidegree of the Gauss-graph cycle
  • domain assumption Flat limits of cycles contain the conormal variety of the Fermat cone with positive coefficient under any degeneration to the target polynomial
    Central specialization step that transfers the multidegree to the dual degree

pith-pipeline@v0.9.1-grok · 5901 in / 1550 out tokens · 36841 ms · 2026-06-27T04:36:37.118023+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Alper, T

    J. Alper, T. Bogart, and M. Velasco. A lower bound for the determinantal complexity of a hypersurface.Found. Comput. Math.17(3):829–836, 2017. 24 K. Sheshadri

    2017

  2. [2]

    Bringmann, C

    K. Bringmann, C. Ikenmeyer, and J. Zuiddam. On algebraic branching programs of small width.J. ACM65(5), art. 32, 2018

    2018

  3. [3]

    B¨ urgisser.Completeness and Reduction in Algebraic Complexity Theory

    P. B¨ urgisser.Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics 7, Springer, 2000

    2000

  4. [4]

    Fulton, S

    W. Fulton, S. Kleiman, and R. MacPherson. About the enumeration of contacts. In Algebraic Geometry — Open Problems (Ravello, 1982), Lecture Notes in Math. 997, pp. 156–196, Springer, 1983

    1982

  5. [5]

    Fulton.Intersection Theory, 2nd ed

    W. Fulton.Intersection Theory, 2nd ed. Springer, 1998

    1998

  6. [6]

    I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky.Discriminants, Resultants, and Multidimensional Determinants. Birkh¨ auser, 1994

    1994

  7. [7]

    J. A. Grochow. Unifying known lower bounds via geometric complexity theory.Comput. Complexity24(2):393–475, 2015

    2015

  8. [8]

    Hartshorne.Algebraic Geometry

    R. Hartshorne.Algebraic Geometry. Graduate Texts in Mathematics 52, Springer, 1977

    1977

  9. [9]

    S. L. Kleiman. The transversality of a general translate.Compositio Math.28:287–297, 1974

    1974

  10. [10]

    Kr¨ amer

    T. Kr¨ amer. Semicontinuity of Gauss maps and the Schottky problem.Math. Ann. 380:821–856, 2021

    2021

  11. [11]

    Kumar and B

    M. Kumar and B. L. Volk. A lower bound on determinantal complexity. In36th Computa- tional Complexity Conference (CCC 2021), LIPIcs 200, art. 4. Journal version:Comput. Complexity31 (2022), art. 8. Full version:arXiv:2009.02452

    work page arXiv 2021

  12. [12]

    D. T. Lˆ e and B. Teissier. Limites d’espaces tangents en g´ eom´ etrie analytique.Comment. Math. Helv.63(4):540–578, 1988

    1988

  13. [13]

    J. M. Landsberg, L. Manivel, and N. Ressayre. Hypersurfaces with degenerate duals and the geometric complexity theory program.Comment. Math. Helv.88(2):469–484, 2013. See alsoarXiv:1004.4802

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  14. [14]

    Mignon and N

    T. Mignon and N. Ressayre. A quadratic bound for the determinant and permanent problem.Int. Math. Res. Not.2004(79):4241–4253, 2004

    2004

  15. [15]

    Mumford.The Red Book of Varieties and Schemes, 2nd expanded ed

    D. Mumford.The Red Book of Varieties and Schemes, 2nd expanded ed. Lecture Notes in Mathematics 1358, Springer, 1999

    1999

  16. [16]

    R. Piene. Polar classes of singular varieties.Ann. Sci. ´Ec. Norm. Sup´ er.11(2):247–276, 1978

    1978

  17. [17]

    Sheshadri

    K. Sheshadri. A near-quadratic lower bound on the determinantal complexity of P i xn i via the polar degree of the tangent cone.arXiv:7680505, 2026

    2026

  18. [18]

    Sheshadri

    K. Sheshadri. A symmetric determinantal lower bound for diagonal power sums via polar degree.arXiv:7685504, 2026

    2026

  19. [19]

    A. J. Sommese and C. W. Wampler.The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific, 2005

    2005

  20. [20]

    E. A. Tevelev.Projective Duality and Homogeneous Spaces. Encyclopaedia of Mathematical Sciences 133, Springer, 2005

    2005

  21. [21]

    Ghat_{t0} = det Ahat_{t0}

    L. G. Valiant. Completeness classes in algebra. InProc. 11th ACM Symposium on Theory of Computing, pp. 249–261, 1979. A Consistency checks and symbolic verification All computations were performed in exact arithmetic (Python integers; sympy for polynomial expansion and resultants); the script is available from the author on request. We record the actual o...

    1979