Lyapunov stability of polynomial vector fields is undecidable
Arnold conjectured that no algorithm can decide whether the origin is Lyapunov stable for a polynomial vector field with rational coefficients of fixed degree and dimension. The work settles this conjecture.
A register machine with undecidable halting is simulated by a clocked ODE, using sample-and-hold, cubic relaxation and growing gain so that error bounds hold uniformly over all initial states. The ODE is then algebraized into a polynomial system with an accumulated-output functional, using smoothing, auxiliary radicals, a penalty and a time change. A projective lift turns this system into a homogeneous polynomial field whose stability is equivalent to halting. The Main Theorem is formalized in Lean; some later remarks are not.
There exist N and odd D for which Lyapunov stability of homogeneous degree-D polynomial fields in dimension N is undecidable; the smallest dimension obtained is N = 5. Analogous undecidability holds for global asymptotic and exponential stability of non-homogeneous fields, and all common stability notions are decidable for homogeneous fields in dimension 2.
