Decidability of local asymptotic stability for polynomial ODEs
An input is a positive integer $n$ and a polynomial vector field $f \in \mathbb{Q}[x_1, \dots, x_n]^n$ with $f(0) = 0$, given by the exact rational coefficients of its monomials; the dimension and the degree are part of the input. Let $\phi(t, x_0)$ be the maximal solution of $\dot x = f(x)$ with $\phi(0, x_0) = x_0$, and $\|\cdot\|$ the Euclidean norm. The origin is locally asymptotically stable if (i) for every $\varepsilon > 0$ there is $\delta > 0$ such that for every $x_0$ with $\|x_0\| < \delta$ the solution exists for all $t \ge 0$ and $\|\phi(t, x_0)\| < \varepsilon$ for all $t \ge 0$, and (ii) there is $r > 0$ such that for every $x_0$ with $\|x_0\| < r$ the solution exists for all $t \ge 0$ and $\phi(t, x_0) \to 0$ as $t \to \infty$. Arnold asked whether the stability of a stationary point of a polynomial vector field with rational coefficients is algorithmically decidable. Local exponential stability is decidable in polynomial time, being equivalent to the linearization at the origin being Hurwitz, while Ahmadi and Parrilo proved that deciding local asymptotic stability is strongly NP-hard already for homogeneous cubic vector fields.
Problem. Is there an algorithm that halts on every such input and decides whether the origin is locally asymptotically stable?
Source: Arnold (1976), Problem XVII of the Problems of present day mathematics, for stability of a stationary point of a polynomial vector field of fixed degree; for local asymptotic stability, Ahmadi and Parrilo (2013), §1 and §3. Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- DS — Dynamical Systems
- Secondary
- LO, OC
- Keywords
- AIM Open Applied Problems, asymptotic stability, decidability, polynomial vector fields
References
@incollection{arnold1976,
author = {Arnold, V. I.},
title = {Problems of present day mathematics, {XVII} ({D}ynamical systems and differential equations)},
booktitle = {Mathematical Developments Arising from {H}ilbert Problems},
editor = {Browder, Felix E.},
series = {Proc. Sympos. Pure Math.},
volume = {28},
publisher = {Amer. Math. Soc.},
address = {Providence, RI},
year = {1976},
pages = {59},
doi = {10.1090/pspum/028.1/9812},
note = {In the collection Problems of present day mathematics, pp. 35--92},
}
@misc{ahmadi2013,
author = {Ahmadi, Amir Ali and Parrilo, Pablo A.},
title = {Stability of polynomial differential equations: complexity and converse {L}yapunov questions},
year = {2013},
eprint = {1308.6833},
archivePrefix = {arXiv},
}
@inproceedings{ahmadi2012,
author = {Ahmadi, Amir Ali},
title = {On the difficulty of deciding asymptotic stability of cubic homogeneous vector fields},
booktitle = {2012 American Control Conference (ACC)},
publisher = {IEEE},
year = {2012},
pages = {3334--3339},
doi = {10.1109/ACC.2012.6315687},
}
@inproceedings{dacosta1993,
author = {da Costa, N. C. A. and Doria, F. A.},
title = {On {A}rnol'd's {H}ilbert symposium problems},
booktitle = {Computational Logic and Proof Theory (KGC 1993)},
series = {Lecture Notes in Comput. Sci.},
volume = {713},
publisher = {Springer},
address = {Berlin},
year = {1993},
pages = {152--158},
doi = {10.1007/BFb0022563},
}
@misc{aim-polynomial-local-stability-decidability,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Decidability of local asymptotic stability for polynomial ODEs}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/338-polynomial-local-stability-decidability.md},
note = {Entry 338 at commit a153f46, 2026-10-13},
}
Resolution claims
We study the decision problem of global asymptotic stability (GAS) of the origin for homogeneous polynomial vector fields with rational coefficients. In the first part of the paper we give, for every fixed dimension $n$ and odd degree $2k+1$, a computable map which sends a homogeneous vector field of degree $2k+1$ on $\mathbb{R}^n$ to a homogeneous cubic vector field on …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: arXiv:2610.12434v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00495, "Decidability of local asymptotic stability for polynomial ODEs", clopen.solutions.