Lyapunov stability of polynomial vector fields is undecidable

Abstract

We show that there are integers $N$ and odd $D$ such that no algorithm can decide, from the rational coefficients of a homogeneous polynomial vector field $F$ in dimension $N$ of degree $D$, whether the origin is Lyapunov stable for $\dot Y=F(Y)$. This proves a conjecture of V. I. Arnold. We provide a Lean formalization of the proof. The smallest dimension $N$ for which we were able to prove undecidability is $N = 5$. An analogous undecidability result holds for global asymptotic stability and global exponential stability for non-homogenous vector fields. For dimension $N=2$ and homogenous vector fields, we establish decidability for all commonly used stability notions, building heavily on existing results.