Global asymptotic stability of homogeneous polynomial vector fields is undecidable

arXiv:2610.12434 · math.DS, math.CA, math.LO · Submitted 2026-10-08 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Global asymptotic stability of homogeneous polynomial vector fields is undecidable".

Emmy: Here's the gist of the paper. The core findings revolve around establishing the undecidability of Global Asymptotic Stability (GAS) for rational homogeneous polynomial vector fields under specific conditions.

Ada: Here is the detailed synthesis: Comprehensive Research Summary: Undecidability of Global Asymptotic Stability for Homogeneous Polynomial Vector Fields This research addresses the computational complexity of determining whether the origin is Globally Asymptotically Stable (GAS) for a homogeneous polynomial vector field x dot = F(x) with rational coefficients in R N.

Emmy: The central thesis is that this problem becomes many-one complete and undecidable when restricted to cubic vector fields in a fixed dimension.

Ada: Key Theoretical Framework and Methodology: The paper employs a sophisticated reduction strategy, leveraging concepts from invariant probability measures and maximal averages along angular flows (Lemma 3.2).

Title and authors: Ada: So we're looking at this paper today, titled "Global asymptotic stability of homogeneous polynomial vector fields is undecidable." It tackles a fundamental question: can we ever build an algorithm that tells us if the origin is globally asymptotically stable for these kinds of vector fields?

Emmy: Exactly. It’s about whether you can write a program that takes the definition of a vector field, like its dimension and its coefficients, and always correctly answers yes or no about its stability. But this paper says that for cubic fields in fixed dimensions, the answer is no; it's undecidable.

Kolya: Undecidable is strong language. What does that mean for someone who just wants to know if their system will settle down over time? Does it mean we can never solve the problem even if we have infinite computing power?

Ada: Not quite infinite power, Kolya. It means there's a specific version of this problem—the one they call homogeneous cubic fields in a fixed dimension—that is fundamentally too hard for any algorithm to solve universally. It’s like trying to write a program that can correctly predict the behavior of every possible physical system at once.

Emmy: The authors set up a reduction. They show that if you can solve the stability problem for one type of field, you can use that solution to decide another stability problem entirely. This links the cubic case to things we already know are impossible to solve algorithmically, like the halting problem for computers.

Kolya: So they are basically saying this stability question is as hard as figuring out if a computer program will ever stop running or run forever? That makes it feel incredibly abstract when you think about actual physical systems.

Ada: It really does. The paper shows that they can encode the halting problem into the stability condition of these vector fields. They create a specific setup where the system being stable or not is directly linked to whether some computer program halts or not, which is what makes it undecidable according to section three of this paper <ref:2610.12434#pg1>.

Emmy: What I find particularly interesting is how they handle the general case. They establish a way to transform any vector field of any odd degree into an equivalent cubic one. This means if you can't solve the cubic problem, you probably can't solve the general problem for those odd degrees either, because they are pairwise many-one equivalent according to section one of this paper <ref:2610.12434#pg1,are pairwise many-one equivalent>.

Ada: That reduction is quite powerful. It takes a field of any odd degree 2k+one and maps it onto a cubic one in dimension m, where m is related to the original dimension n and the degree k <ref:2610.12434#pg1>. This transformation preserves both global asymptotic stability and Lyapunov stability, which is key for the equivalence they're proving > Page one <ref:2610.12434#pg1>.

Title and authors: Kolya: But if this reduction works for all odd degrees, what about even degrees? Does it still apply to those? I mean, we usually look at things in terms of their degree parity when we talk about these types of systems.

Emmy: The paper focuses specifically on odd degrees d at least three and it shows that the problem for every fixed odd degree is equivalent to the cubic case <ref:2610.12434#pg1>. It’s a statement about the structure imposed by the polynomial form itself, not just a limitation on our computational tools.

Ada: And then they go into part three, where they construct a specific fixed dimension N* and a specific odd degree d* where this problem is many-one complete. This means that if you can solve stability for that one specific setup, you can solve it for *every* other setup in the class of cubic fields > Page two <ref:2610.12434#pg2>.

Kolya: That leads to the core result, right? They show a direct link between being globally asymptotically stable and some kind of invariant average of the flow being negative. What does that average look like in practice? Is it something we can actually measure from data?

Emmy: It's related to how the system behaves when you look at its angular flow, using what they call maximal averages along angular flows > Lemma three point two <ref:2610.12434#pg1>. The condition for stability simplifies down to checking if this specific average is less than zero, which is a measurable quantity derived from the flow’s dynamics.

Ada: That's the operational part of it. They take a complex stability question and turn it into an inequality involving an invariant average > Page two <ref:2610.12434#pg2>. This moves it from being purely theoretical to something that involves checking a specific sign condition on some mathematical object related to the flow.

Kolya: So, if we have data from a physical system, can we use this average condition to decide if that system is globally stable? Does the AI approach make this solvable in practice?

Emmy: The paper suggests an improvement in how we think about stability. They propose transforming the decision problem into determining if a maximal invariant average of the radial rate is negative > Improvement three <ref:2610.12434#pg1>. This gives us a concrete, computable condition that replaces the original stability question.

Ada: That's a big step because it shifts the focus from an abstract "is it stable?" question to checking if this specific numerical quantity derived from the flow dynamics is less than zero. It makes the problem computationally tractable in a theoretical sense, even if we still can't solve it for every field.

Kolya: So, what about these other ideas mentioned in the paper? They talk about encoding Diophantine problems into Fourier series to determine integer solutions > Improvement seven. That sounds like they are using this undecidability result to tackle number theory problems too.

Title and authors: Emmy: Right, that’s a major implication. They use the undecidability of stability as a tool to solve other hard number theory questions by encoding those equations into the polynomial vector field structure > Improvement seven. It shows how deep this connection goes between dynamical systems and arithmetic constraints.

Ada: The paper also suggests that for homogeneous cubic fields in fixed dimensions, we can actually decide whether the origin is both globally asymptotically stable and Lyapunov stable > Improvement two <ref:2610.12434#pg2>. This is a concrete result about a specific class of fields that might be useful for engineering applications.

Kolya: That’s more practical, though it still depends on N and the degree d being large enough, which are the caveats they mention > Improvement two <ref:2610.12434#pg2>. So, we're not getting an easy answer for every cubic system out there just yet.

Emmy: The main implication is showing that we have a complete reduction chain from the undecidable halting problem to this stability problem > Page three <ref:2610.12434#pg1>. It solidifies the idea that this specific decision problem is at the very top of computational difficulty for homogeneous polynomial vector fields.

Ada: So, to wrap up, the paper "Global asymptotic stability of homogeneous polynomial vector fields is undecidable" proves that we can't have a universal algorithm to check GAS for these systems > Page one <ref:2610.12434#pg1,Global asymptotic stability of homogeneous polynomial vector fields is undecidable>. It does this by mapping it onto the halting problem using cubic fields in fixed dimensions.

Emmy: It also offers a path forward, showing that we can solve stability for cubic systems in specific, restricted settings by checking the sign of an invariant average > Improvement one <ref:2610.12434#pg1>.

Kolya: And I just want to say that while this is a theoretical ceiling for general solutions, it gives us concrete bounds and conditions—like needing N and d to be large enough—so we know where the current algorithmic limits are > Improvement two <ref:2610.12434#pg2>.

Ada: Exactly. It’s not about finding a magic algorithm; it’s about understanding precisely which problems are fundamentally beyond our reach, and then finding the specific cases where we can get some kind of answer through clever reformulation > Page four.

Emmy: So, the paper demonstrates that complex stability questions for homogeneous polynomial vector fields are deeply connected to fundamental limits in computation itself > Page two <ref:2610.12434#pg2>. We’re looking at how structure dictates computational complexity.

Kolya: It really puts things into perspective when you think about the sheer number of different systems out there and just realizing some of them are inherently unsolvable by any single method > Page three <ref:2610.12434#pg1>.

Ada: That's the point, Kolya. We’ve moved from asking if it's solvable to understanding precisely *why* it’s not solvable in the general case, while providing tools for solving restricted versions > Page four.

Emmy: So that’s where we are today with this paper on global asymptotic stability of homogeneous polynomial vector fields is undecidable. We have a clear picture of the hard problems and some ways to approach them > Page sixteen <ref:2610.12434#pg2>.

The paper's summary: Ada: So, we're looking at the core of this paper now about global asymptotic stability for homogeneous polynomial vector fields. Basically, they’ve shown that if you look at cubic vector fields in a fixed dimension, determining if the origin is globally stable is fundamentally impossible for any computer program to solve.

Emmy: It boils down to a reduction strategy where they take these general degree fields and transform them into simpler cubic ones, and the difficulty stays with the cubic case. They use this transformation to show that if you can't solve it for those specific cubic systems, you can't solve it for any other odd degree fields either.

Ada: The key mechanism they use is linking this stability question to invariant averages along flows on a compact space. They rewrite the stability condition as checking if a specific average of the flow—the maximal average—is negative.

Kolya: I see that formulation, and what I'm wondering is how much of this actually translates into something we can measure in the real world. Is this just some abstract math about an invariant average?

Emmy: It’s more than that because they connect it to the halting problem for a computer. They construct a specific set of cubic fields where being globally asymptotically stable is equivalent to whether a certain Turing machine halts or not.

Ada: That’s the heavy lifting here. They establish this many-one reduction, which means you can use the stability problem of these vector fields to decide if an arbitrary program will ever finish running. It proves that this decision problem is at least as hard as the halting problem itself for these specific systems.

Kolya: So, it’s not just hard; it’s fundamentally undecidable. That means there's no magic piece of software we can write that works for every possible cubic system to give us a definitive yes or no answer on global stability. What does that imply practically?

Emmy: It implies a boundary on what we can compute universally. They also showed they can solve the problem for specific, restricted cases—like homogeneous cubic fields in a fixed dimension—if the dimension and the degree are large enough.

Ada: So, there’s this trade-off. You lose universal solvability for the general case, but you gain concrete decision power if you restrict your system to these specific constraints. It sets a clear limit on what kind of stability questions we can ask algorithmically in this field.

The paper's improvements: Ada: We're looking at how these researchers are trying to fix the problem they just proved is undecidable about global asymptotic stability for these vector fields. They suggest moving away from checking if a system is stable in the abstract and instead focusing on a more concrete, computable quantity.

Emmy: Exactly. The core idea in their improvements is to reformulate that stability question into determining if a specific maximal invariant average of the radial rate is negative. That gives you an actual number or quantity you can check against zero.

Kolya: Checking if an average of a radial rate is negative sounds like something we could potentially measure from real system data, which makes sense for someone who deals with probability and statistical bounds.

Ada: Precisely. They call this checking the condition for forward completeness, which is equivalent to that maximal invariant average being negative. It turns the stability question into a check on a specific sign condition of an observable derived from the flow's dynamics.

Emmy: This shift means instead of needing an infinite algorithm to solve it, you’re looking at a specific inequality involving that average. If that quantity is less than zero, the origin is globally asymptotically stable.

Kolya: So they’re trading a universal undecidability proof for a specific condition on an observable. What are the practical limitations here? Does this new method work for all homogeneous polynomial vector fields, or just some subset?

Ada: The paper notes that this approach works well for homogeneous cubic vector fields in fixed dimensions, provided those dimensions and the degree are large enough. It’s a constrained win, not a universal fix.

Emmy: They also touch on encoding problems into Fourier series to solve Diophantine equations. That shows how this structural analysis of the vector field is being used as a tool to tackle number theory constraints, linking dynamics and arithmetic together.

Kolya: So, the improvement is less about solving every stability problem and more about finding tractable conditions for specific classes of systems while still leveraging the deep structural properties of these polynomial fields. This suggests that the difficulty isn't just in the math, but in how we choose to frame our measurement question.

Conclusion: Tom: So to wrap up this talk on "Global asymptotic stability of homogeneous polynomial vector fields is undecidable," we're saying that for cubic systems in fixed dimensions, we can't build a universal algorithm to determine if the origin is globally stable.

Ada: That’s right. The paper proves this by using a reduction from the halting problem into the stability condition of these specific vector fields. It shows that even with algebraic structure, there are certain problems that are fundamentally unsolvable by any fixed method.

Emmy: It highlights how deeply connected these dynamical systems are to computation itself; the stability question isn't just about physics, it's about limits in logic.

Kolya: I think the real value here is seeing where those algorithmic limits sit for specific systems, like cubic ones, even if you can't solve them all generally. It gives us a map of computational hardness.

Ada: Exactly. And the improvements they suggested show that we can still get answers for certain cases by looking at invariant averages and checking their sign, which is a way to turn an unsolvable problem into a computable inequality for those restricted fields.

Emmy: So the path forward isn't necessarily finding a general solver, but developing these specific checks for particular structures where they work. It’s about finding the right mathematical language for the right physical system.

Kolya: I just think it’s interesting how they connect this to things like encoding Diophantine problems into Fourier series as well; that shows how one field informs constraints in another.

Ada: It really does. This paper on "Global asymptotic stability of homogeneous polynomial vector fields is undecidable" sets a high bar for what we can expect from general computation in these areas.

Emmy: Next time, we’ll be looking at some of the results on cumulative angular cancellation in Maz'ya's endpoint inequalities to see how that relates to potential theory.

math.DS, math.CA, math.LO

Submitted: 2026-10-08

Updated: 2026-11-03

Comments: 84 pages

Code: https://github.com/j49liu/gas_decidability_lean

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

The gist: The core findings revolve around establishing the undecidability of Global Asymptotic Stability (GAS) for rational homogeneous polynomial vector fields under specific conditions.

Key concepts

Global Asymptotic Stability (GAS)
This condition means that every trajectory of the system eventually converges to the origin regardless of where it starts in space. For a vector field, this implies that all solutions spiral or move towards zero as time goes on, making the origin a stable attractor for the entire system.
Homogeneous Polynomial Vector Field
These are differential equations where every term in the defining function has the same degree (e.g., $x^3$, $xy^2$). The stability analysis focuses on how these specific polynomial structures influence whether trajectories approach or move away from the equilibrium point at the origin.
Many-one Complete
This is a measure of computational difficulty. A problem is many-one complete if every other problem in its complexity class can be transformed into it via a simple, computable reduction. In this context, it means that solving this specific stability problem is as hard as solving the most difficult problems in that complexity class.
Invariant Probability Measure
This concept relates to how trajectories distribute themselves over the state space of the system over long periods. Analyzing these measures helps reformulate stability conditions into inequalities involving averages, which is key to proving undecidability.

Terminology

Summary

The core findings revolve around establishing the undecidability of Global Asymptotic Stability (GAS) for rational homogeneous polynomial vector fields under specific conditions. p. 0

Where the paper says it

SHEVCHENKO, JUN LIU, AND XINZHI LIU October 9, 2026 Abstract. We study the decision problem of global asymptotic stability (GAS) of the origin for homogeneous polynomial vector fields with rational coefficients.

Here is the detailed synthesis:


Comprehensive Research Summary: Undecidability of Global Asymptotic Stability for Homogeneous Polynomial Vector Fields

This research addresses the computational complexity of determining whether the origin is Globally Asymptotically Stable (GAS) for a homogeneous polynomial vector field x dot = F(x) with rational coefficients in R N. The central thesis is that this problem becomes many-one complete and undecidable when restricted to cubic vector fields in a fixed dimension. p. 2

Where the paper says it

Part I (Sections 4–7) shows that every stability problem for homogeneous vector fields of odd degree reduces, in a fixed dimension, to the same problem for cubic vector fields. Part II (Sections 8–15) constructs one fixed dimension and one fixed odd degree in which GAS is many-one complete.

Key Theoretical Framework and Methodology:

The paper employs a sophisticated reduction strategy, leveraging concepts from invariant probability measures and maximal averages along angular flows (Lemma 3.2). The stability condition for the origin is reformulated as an inequality involving an invariant average: the origin is GAS if and only if beta(phi P, a P) < 0. p. 0

Where the paper says it

In the second part we prove that there are a fixed dimension N∗ and a fixed odd degree d∗ such that the set of homogeneous vector fields on R N∗ of degree d∗ whose origin is GAS is many-one complete. The reduction encodes an undecidable family of polynomial equations in integer unknowns into the constant term of a product of Jacobi theta series, realizes these series as outputs of a polynomial differential system with rational coefficients, and turns the existence of an integer solution into the sign of a maximal invariant average, which homogeneous GAS detects.

The methodology proceeds in two major phases:

  1. Reduction to Cubic Normal Form (Part I): The authors establish a computable map (Theorem 1.2) that transforms any rational homogeneous vector field F of odd degree 2k+1 into an equivalent homogeneous cubic vector field H. p. 0

    Where the paper says it

    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 R n to a homogeneous cubic vector field on R m, m = n+k−1 k , and preserves both GAS and Lyapunov stability.

    This transformation allows the problem of stability for a general degree to be reduced to the problem concerning cubic fields, suggesting that if the cubic case is undecidable, the general case is as well. p. 0
    Where the paper says it

    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 R n to a homogeneous cubic vector field on R m, m = n+k−1 k , and preserves both GAS and Lyapunov stability.

    Furthermore, Theorem 1. p. 2
    Where the paper says it

    Compared with the results posted in [28], the main result of this paper resolves the case of GAS. Furthermore, we build on these results to bring the undecidability of Lyapunov stability down to cubic vector fields in a fixed dimension (Corollary 1.

    3 establishes many-one equivalences between stability problems involving different odd degrees (d). p. 0
    Where the paper says it

    The map passes to new variables yα = x α (one for each monomial x α of degree k), in which the vector field becomes cubic, and adds a cubic penalty term transverse to the set of points of the form (x α )|α|=k; the main point is that this controls every initial state of the new system. As a consequence, the GAS problems for all degrees, for each fixed odd degree d ≥ 3, and for degree three are pairwise many-one equivalent.

  2. Encoding Undecidability (Part II): The paper constructs a specific fixed dimension N* and an odd degree d* such that the problem HGAS(N*, d*) is many-one complete (Theorem 1.5). This construction encodes the halting set K of a universal Turing machine into the positivity/negativity of a constant term derived from an explicit Fourier series, which is realized as the maximal invariant average being negative. p. 4

    Where the paper says it

    Outline of Part II. The reduction in Part II is a chain of equivalences, for e in the halting set K of a fixed universal Turing machine: e ∈ K ⇐⇒ a fixed Diophantine system with right-hand side c(e) has an integer solution ⇐⇒ an explicit Fourier series De on a torus has a nonzero constant term ⇐⇒ every relevant invariant measure of a polynomial source flow has nonzero drift ⇐⇒ the largest invariant average of a reward on a compact product of spheres is negative ⇐⇒ the origin of an explicit homogeneous polynomial vector field Fe is GAS.

The Reduction Chain and Undecidability Proof:

The critical step involves a chain of equivalences that links membership in the halting set K to the stability condition:

  • A parameter e (representing an instance from K) is mapped via a total, computable map (e to F e) to a homogeneous polynomial vector field x dot = F e(x) on R N* of degree d*.

  • The stability condition for this constructed field is shown to be equivalent to the membership of e in K: e in K beta e < 0 0 is GAS for x dot = F e(x).

  • Crucially, the mapping e to F e is total and computable but never tests whether e in K.

This establishes a many-one reduction from the undecidable set K to HGAS(N*, d*), proving that HGAS(N*, d*) is many-one hard. p. 0

Where the paper says it

In the second part we prove that there are a fixed dimension N∗ and a fixed odd degree d∗ such that the set of homogeneous vector fields on R N∗ of degree d∗ whose origin is GAS is many-one complete. The reduction encodes an undecidable family of polynomial equations in integer unknowns into the constant term of a product of Jacobi theta series, realizes these series as outputs of a polynomial differential system with rational coefficients, and turns the existence of an integer solution into the sign of a maximal invariant average, which homogeneous GAS detects.

Since the problem is also recursively enumerable (r. p. 2
Where the paper says it

GAS OF HOMOGENEOUS POLYNOMIAL VECTOR FIELDS IS UNDECIDABLE 3 Throughout, reductions are computable many-one reductions, and we write A ≤m B if A many-one reduces to B. A set is many-one complete if it is recursively enumerable and every recursively enumerable set many-one reduces to it, and it is many-one hard if every recursively enumerable set many-one reduces to it; see Section 2.

e.) by Proposition 3. p. 2
Where the paper says it

1], building on Rosier’s smooth homogeneous converse theorem [39, Theorem 2, p. Together with real quantifier elimination this shows that HGAS is recursively enumerable (Proposition 3.

4, it is many-one complete for this specific fixed dimension and degree. p. 0
Where the paper says it

As a consequence, the GAS problems for all degrees, for each fixed odd degree d ≥ 3, and for degree three are pairwise many-one equivalent. In the second part we prove that there are a fixed dimension N∗ and a fixed odd degree d∗ such that the set of homogeneous vector fields on R N∗ of degree d∗ whose origin is GAS is many-one complete.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Global asymptotic stability decision making for homogeneous polynomial vector fields is transformed into determining if a maximal invariant average of a flow on a compact space is negative, enabling algorithmic detection of GAS.

  2. The AI system can decide whether the origin of any homogeneous cubic vector field on R N with rational coefficients is GAS or Lyapunov stable, provided N and the degree d are sufficiently large (specifically for odd d >= 3).

  3. The system can verify if a given homogeneous polynomial vector field has a solution that is forward complete, which is equivalent to checking if the maximal invariant average of its radial rate is negative.

  4. The AI can classify zero-drift orbits for homogeneous polynomial vector fields by analyzing their validity residuals, moment averages, and detector observables along recurrent solutions.

  5. The system can determine if an input code for a homogeneous polynomial vector field belongs to the set HGAS or HLS by checking the computability of a sequence of sentences related to strict positivity on the sphere.

  6. The system can compute cubic normal forms for any given degree and dimension, allowing complex stability problems to be reduced to a fixed, simpler problem in dimension 3 and degree 3.

  7. The AI can solve complex Diophantine problems by encoding them into an explicit Fourier series whose constant term is positive if and only if the original Diophantine equation has an integer solution.

  8. The system can implement algebraic clocks that drive polynomial differential systems to determine recurrent solutions satisfying prescribed time averages, effectively realizing Jacobi theta functions as outputs of polynomial systems.

Abstract

We study whether global asymptotic stability (GAS) of the origin is decidable for homogeneous polynomial vector fields with rational coefficients. Our main technical contribution is showing that, for such vector fields of odd degree d at least 3 in every sufficiently large dimension n, the problem of deciding GAS of the origin is many-one complete for the class of recursively enumerable sets (and hence undecidable). Using the tools we have built up, we also improve on some recent work by proving a similar result for Lyapunov stability instead of GAS. The proof of our main contribution splits naturally into two parts: - In the first part we give, for every fixed dimension n and odd degree 2k+1, a computable map which sends a homogeneous polynomial vector field of degree 2k+1 on R n to a homogeneous polynomial vector field of degree three on R m, where m= k, and preserves both GAS and Lyapunov stability. As a consequence, the problems of deciding whether the origin is GAS or Lyapunov stable for rational-coefficient homogeneous polynomial vector fields of any degree, of any fixed odd degree d at least 3, and of degree three are pairwise many-one equivalent. - In the second part we prove that there is a fixed dimension n* and a fixed odd degree d* such that the set of rational-coefficient homogeneous polynomial vector fields on R n* of degree d* whose origin is GAS is many-one complete. This is done by "transferring" many-one completeness between several different problems, starting from the solvability of a Diophantine equation and eventually arriving at our desired GAS decision problem.

Sources

Related papers