Is any-dimensional nonnegativity of symmetric functions decidable?
A symmetric function in the power sums truncates to a symmetric polynomial in variables for every . Call any-dimensional nonnegative if on for every . For a fixed this is decidable (Tarski-Seidenberg), and Artin's solution of Hilbert's 17th problem supplies a sum-of-squares multiplier. Is there an algorithm that decides whether a given with rational coefficients is any-dimensional nonnegative? Equivalently, is nonnegativity of univariate trace polynomials, that is, polynomials in the unnormalized traces of one real symmetric matrix of arbitrary size, decidable? Acevedo, Blekherman, Debus and Riener proved undecidability for several groups of variables and left the single-group case open as a natural question; Debus and Schabert repeated it in 2026 and asked in addition for analogs of Hilbert's 17th problem, meaning certificates of nonnegativity that are uniform in the number of variables.
- Result
- Disproved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Real algebraic geometry; symmetric functions, sums of squares
- Posed by
- Acevedo, Blekherman, Debus and Riener, The wonderful geometry of the Vandermonde map (arXiv 2023, Section 7)
- Year posed
- 2023
- Years open
- 3y
- Solved
- 2026-11-12
- Model
- GPT-6 Astra; Claude Fable 5.1
- Vendor
- OpenAI; Anthropic
- Collaborators
- Sebastian Debus, Robin Schabert
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 14 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 2.2 of arXiv:2611.16690 (Sebastian Debus and Robin Schabert, Konstanz, 17 pages): it is undecidable whether a symmetric function with rational coefficients is nonnegative in every number of variables, already for homogeneous even symmetric functions in . The proof reduces Hilbert's tenth problem in nine unknowns (Jones) through an explicit map . Theorem 3.1: an explicit homogeneous octic is positive definite in every dimension, yet no nonzero power series of bounded degree has and sums of squares for all , so Artin's theorem and the Krivine-Stengle Positivstellensatz have no any-dimensional analog. Not the first public proof of undecidability: Kaiwen Jin's 4-page manuscript, prepared with OpenAI Codex, was posted to the AIM Open Applied Problems repository on 12 October 2026, a month earlier, with non-homogeneous instances; the authors date their own AI-found proofs to September 2026.
What the AI did
From the paper's AI Declaration: initial proofs of both main results (Theorem 2.2 and Theorem 3.1) were found by GPT 6.0 Astra in September 2026. The authors then verified, simplified and strengthened the proofs with further help from Claude Fable 5.1, and wrote the final presentation themselves, using AI for grammar, spelling and readability. The Lean formalization was almost entirely generated by coding agents (mainly Claude, according to the repository README); the authors say that the statements in AnyDim/Paper.lean are the part they compared with the paper.
Verification
No independent mathematician has checked this yet. Unreviewed on this site's ladder: a Lean formalization of the undecidability reduction exists, but nobody outside the authors has been seen to compile it. Checked here on 19 November 2026: arXiv 2611.16690v1 (introduction, Theorem 2.2, Remark 2.7, AI declaration) and the repository RobinSchabert/positive-sym-func-h17-undecidability-lean at commit 2318a73 (Lean v4.35.0-rc3, pinned Mathlib, 24 files). Read: theorem_2_2, theorem_2_2_nine and theorem_3_1 in AnyDim/Paper.lean, and HasNatZero. What Lean states is the many-one reduction: for every integer polynomial , all truncations of are nonnegative on if and only if has no zero in , with homogeneous and even in when . Decidability itself, the DPRM theorem, Jones's theorem and the computability of are not formalized. A grep found no axiom, native_decide or unsafe code and exactly one sorry: Blekherman's hypercube theorem (Theorem 3.2, quoted from the literature). The Section 2 files do not import that file, and theorem_3_1 is proved through an elementary replacement bound; the repository's #guard_msgs record only the three standard axioms for both. Not built here, and the repository has no CI, so compilation rests on the authors. The question was read in arXiv 2303.09512 (Section 7) and 2606.27551 (Section 8).
Sources
- PaperarXiv
- Lean proofLean repository at commit 2318a73
- Lean statementHeadline statements (AnyDim/Paper.lean)
- Independent workKaiwen Jin, undecidability manuscript for AIM problem 559 (posted 12 Oct 2026, OpenAI Codex), concurrent proof
- Problem recordAcevedo, Blekherman, Debus and Riener, The wonderful geometry of the Vandermonde map (question in Section 7)Debus and Schabert, Any-dimensional Positivstellensaetze for symmetric functions (question repeated, Section 8)
Submitted by MellowGander562 on