Deciding nonnegativity of unnormalized univariate trace polynomials
For a positive integer $d$ and a polynomial $F \in \mathbb{Q}[z_1, \dots, z_d]$, consider the statement $$F\bigl(\operatorname{tr}(A), \operatorname{tr}(A^2), \dots, \operatorname{tr}(A^d)\bigr) \ge 0 \quad \text{for every } n \ge 1 \text{ and every real symmetric } A \in \mathbb{R}^{n \times n},$$ where $\operatorname{tr}$ is the ordinary, unnormalized trace. The polynomial is a pure trace polynomial: there is no free matrix factor, and its constant term is the scalar $1$, not $\operatorname{tr}(I) = n$. Equivalently, the statement asks whether $$F\Bigl(\sum_{j=1}^n x_j, \sum_{j=1}^n x_j^2, \dots, \sum_{j=1}^n x_j^d\Bigr) \ge 0$$ for every $n \ge 1$ and every $(x_1, \dots, x_n) \in \mathbb{R}^n$. The matrix size is not bounded by the input. Acevedo, Blekherman, Debus and Riener proved that deciding nonnegativity of trace polynomials in several real symmetric matrices of all sizes, the number of matrices being part of the input, is undecidable, and that the problem with normalized traces $\operatorname{tr}(A)/n$ is decidable; their reduction does not apply to a single matrix. Klep, Pascoe and Volčič proved a Positivstellensatz for univariate normalized trace polynomials.
Problem. Is there an algorithm that, on every input $d$ and $F$, always terminates and correctly decides the statement above? Give such an algorithm, or prove that the decision problem is undecidable.
Source: Acevedo, Blekherman, Debus and Riener (2026), Section 7, for univariate trace polynomials; stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- AG — Algebraic Geometry
- Secondary
- LO, RA
- Keywords
- AIM Open Applied Problems, decidability, power sums, trace polynomials
References
@article{acevedo2026,
author = {Acevedo, Jose and Blekherman, Grigoriy and Debus, Sebastian and Riener, Cordian},
title = {The wonderful geometry of the {V}andermonde map},
journal = {Found. Comput. Math.},
volume = {26},
number = {4},
year = {2026},
pages = {2005--2051},
doi = {10.1007/s10208-025-09718-6},
eprint = {2303.09512},
archivePrefix = {arXiv},
}
@article{klep2021,
author = {Klep, Igor and Pascoe, James Eldred and Vol{\v{c}}i{\v{c}}, Jurij},
title = {Positive univariate trace polynomials},
journal = {J. Algebra},
volume = {579},
year = {2021},
pages = {303--317},
doi = {10.1016/j.jalgebra.2021.03.027},
eprint = {2009.10081},
archivePrefix = {arXiv},
}
@misc{aim-univariate-trace-decidability,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Deciding nonnegativity of unnormalized univariate trace polynomials}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/559-univariate-trace-decidability.md},
note = {Entry 559 at commit a153f46, 2026-10-13},
}
Resolution claims
We prove that no algorithm decides whether a rational polynomial in the ordinary traces of powers of one real symmetric matrix is nonnegative for all finite matrix sizes. The proof encodes nonnegative integers as spectral multiplicities. Stationary polynomial interpolation controls deviations from the encoding nodes with an error bound independent of the number of eigenvalues. A polynomial penalty then transfers …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: AIM @ a153f46, paper/trace_decidability.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00777, "Deciding nonnegativity of unnormalized univariate trace polynomials", clopen.solutions.