Decidability of the Zero Problem for Exponential Polynomials (the Continuous Skolem Problem)

The Zero Problem asks whether an effectively given exponential polynomial $f(t)=\sum_{k=1}^n P_k(t)e^{\lambda_k t}$ with algebraic data — equivalently, a solution of a homogeneous linear differential equation with constant algebraic coefficients and algebraic initial values — has a real zero on $[0,\infty)$; it is the continuous analogue of the Skolem problem for linear recurrence sequences and a fundamental reachability question for continuous-time linear dynamical systems. Chonev, Ouaknine, and Worrell (Journal of the ACM, 2023) proved that the Zero Problem is decidable for equations of order at most 8 subject to Schanuel's conjecture, that the companion Infinite Zeros Problem is decidable unconditionally at order at most 8, and that any decision procedure for the Infinite Zeros Problem at order 9 would compute the Lagrange constants of arbitrary real algebraic numbers — a long-standing open effectiveness problem in Diophantine approximation. All of these questions remain open: unconditional decidability is unknown even for zeros in a given bounded interval, unconditional decidability at order at most 8 is unknown, and no result bypasses the order-9 Diophantine barrier over algebraic data. The sharpest recent adjacent result (Collins, Hanzon, and Neumann, MFCS 2026) proves undecidability for a generalisation over computable discrete subfields of the reals (the exhibited field contains $\pi$), but explicitly leaves all algebraic-coefficient variants open.

Background

An exponential polynomial (also called an exponential-trigonometric polynomial or a C-finite function) is a real-valued function of a real variable of the form

$f(t)=\sum_{k=1}^{n}P_k(t)\,e^{\lambda_k t},$

where the $\lambda_k$ are distinct complex numbers, called the characteristic roots or eigenvalues, and the $P_k$ are nonzero polynomials, with conjugate-symmetric data so that $f$ takes real values. These are exactly the solutions of homogeneous linear ordinary differential equations with constant coefficients, $f^{(m)}+c_1f^{(m-1)}+\dots+c_m f=0$; the order of $f$ is the order $m$ of the least-order such equation, that is, the number of characteristic roots counted with multiplicity. When the coefficients $c_i$ and the initial values are real algebraic numbers, $f$ has a finite exact representation, so one can ask algorithmic questions about it. The Zero Problem — also called the Continuous Skolem Problem, by analogy with the Skolem Problem for linear recurrence sequences (the question whether a sequence satisfying a constant-coefficient linear recurrence ever takes the value zero) — asks whether $f$ has a zero in $[0,\infty)$. The bounded variant asks whether $f$ has a zero in a given interval $[0,T]$, and the Infinite Zeros Problem asks whether $f$ has infinitely many zeros. These are exactly reachability questions for continuous linear dynamical systems $\dot{x}=Ax$ with algebraic entries: a coordinate of the trajectory is an exponential polynomial, so hitting a target hyperplane is a zero question. The imaginary parts of the characteristic roots are called the frequencies of the equation; two frequencies are rationally independent if no nontrivial integer combination of them vanishes.

The decidability of these problems is a central open issue at the meeting point of computability theory, verification of hybrid systems, and transcendental number theory. Bell, Delvenne, Jungers, and Blondel first studied decidability for the continuous-time setting: they proved NP-hardness of the nonnegativity variant, established decidability of zero presence for several subcases including instances of depth at most two, and left general decidability open. Chonev, Ouaknine, and Worrell then proved that the bounded problem is decidable subject to Schanuel's conjecture, and analysed the unbounded problem through its frequencies. Schanuel's conjecture is the central unifying conjecture of transcendental number theory: it asserts that for complex numbers $z_1,\dots,z_n$ that are linearly independent over the rationals, the field $\mathbb{Q}(z_1,\dots,z_n,e^{z_1},\dots,e^{z_n})$ has transcendence degree at least $n$ over $\mathbb{Q}$. Under this conjecture, the first-order theory of the real numbers with exponentiation is decidable — the classical route surveyed by Karimov, Nieuwveld, Ouaknine, Vahanwala, and Worrell — and this is what powers the conditional decision procedures for bounded zero questions. Unconditionally, however, no decision procedure is known even for the bounded case.

For the unbounded case the obstruction is quantitative Diophantine approximation. Chonev, Ouaknine, and Worrell showed that decidability in the presence of two or more rationally independent frequencies would entail computability of the Diophantine-approximation types of all real algebraic numbers (the approximation type of a real number records the asymptotic quality of its rational approximations, formalised for instance through its Lagrange constant), and that a decision procedure for the Infinite Zeros Problem at order 9 would yield an algorithm computing the Lagrange constant of any given real algebraic number to arbitrary precision. The Lagrange constant of a real irrational $\alpha$ is $L(\alpha)=\limsup_{q\to\infty}\,(q\|q\alpha\|)^{-1}$, where $\|x\|$ denotes the distance from $x$ to the nearest integer; it measures the quality of the best rational approximations to $\alpha$ and can be read off from the continued-fraction expansion of $\alpha$. For quadratic irrationals that expansion is eventually periodic, so $L(\alpha)$ is computable; for algebraic numbers of degree at least 3 it is a famous open problem whether the partial quotients are even unbounded, and no algorithm computing $L(\alpha)$ is known — this is the long-standing effectiveness problem that blocks the order-9 case.

The Journal of the ACM paper of Chonev, Ouaknine, and Worrell unified and strengthened these results: for differential equations of order at most 8 the Zero Problem is decidable subject to Schanuel's conjecture, the Infinite Zeros Problem is decidable unconditionally, and the order-9 barrier via Lagrange constants stands; decidability of the Zero Problem in general, even in the bounded case, remains open. The discrete-time analogue has a parallel status: for linear recurrence sequences, the Skolem and Positivity problems are decidable only in low orders, with extension past the threshold provably tied to breakthroughs in Diophantine approximation of transcendental numbers (Ouaknine and Worrell), and conditional general algorithms for simple linear recurrence sequences exist under number-theoretic conjectures such as the Skolem conjecture and the $p$-adic Schanuel conjecture (Bilu, Luca, Nieuwveld, Ouaknine, Purser, and Worrell).

Problem Statement

Settle the decidability of the Zero Problem (Continuous Skolem Problem) for exponential polynomials with algebraic data. Concretely, given an exponential polynomial $f(t)=\sum_{k=1}^n P_k(t)e^{\lambda_k t}$ in which the characteristic roots $\lambda_k$ and the coefficients of the polynomials $P_k$ are algebraic numbers supplied in an exact representation (for example, minimal polynomials over the rationals with isolating intervals) — equivalently, a homogeneous linear differential equation with constant algebraic coefficients and algebraic initial values — the Zero Problem on $[0,\infty)$ is open, and decidability is open even for the Bounded Zero Problem: deciding, without assuming Schanuel's conjecture or any other unproved conjecture, whether $f$ has a zero on a given bounded interval $[0,T]$, with $T$ a given rational number. At present the bounded problem is decidable only subject to Schanuel's conjecture, and its unconditional decidability has been open for over a decade. Unconditional decidability at order at most 8 is likewise unknown — only a Schanuel-conditional procedure is currently known there — but it is not an independent target: it follows from unconditional decidability of the Bounded Zero Problem.

The question is whether, unconditionally, a decision procedure with correctness and termination proofs exists for the general Zero Problem on $[0,\infty)$ or for the Bounded Zero Problem on a given bounded interval $[0,T]$, or whether the Zero Problem, or its bounded variant, is undecidable over algebraic data. Any decision procedure for the companion Infinite Zeros Problem at order 9 or above must in particular overcome the established barrier that it would yield an algorithm computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision — an open effectiveness problem in Diophantine approximation already for algebraic numbers of degree at least 3.

References

1. Ventsislav Chonev, Joel Ouaknine, James Worrell, On the Zeros of Exponential Polynomials, Journal of the ACM 70(4), Article 26, pages 1-26, 2023. DOI: 10.1145/3603543, https://doi.org/10.1145/3603543
2. Ventsislav Chonev, Joel Ouaknine, James Worrell, On the Skolem Problem for Continuous Linear Dynamical Systems, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, pages 100:1-100:13, 2016. DOI: 10.4230/LIPIcs.ICALP.2016.100, https://doi.org/10.4230/LIPIcs.ICALP.2016.100; preprint arXiv:1506.00695, https://arxiv.org/abs/1506.00695
3. Ventsislav Chonev, Joel Ouaknine, James Worrell, On Recurrent Reachability for Continuous Linear Dynamical Systems, 31st ACM/IEEE Symposium on Logic in Computer Science (LICS 2016); preprint arXiv:1507.03632. DOI: 10.1145/2933575.2934548, https://doi.org/10.1145/2933575.2934548, https://arxiv.org/abs/1507.03632
4. Paul C. Bell, Jean-Charles Delvenne, Raphael M. Jungers, Vincent D. Blondel, The continuous Skolem-Pisot problem, Theoretical Computer Science 411(40-42):3625-3634, 2010. DOI: 10.1016/j.tcs.2010.06.005, https://doi.org/10.1016/j.tcs.2010.06.005; preprint arXiv:0809.2189 (2008), under the title The Continuous Skolem-Pisot Problem: On the Complexity of Reachability for Linear Ordinary Differential Equations, https://arxiv.org/abs/0809.2189
5. Rupak Majumdar, Mahmoud Salamati, Sadegh Soudjani, On Decidability of Time-Bounded Reachability in CTMDPs, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 168, pages 133:1-133:19, 2020. DOI: 10.4230/LIPIcs.ICALP.2020.133, https://doi.org/10.4230/LIPIcs.ICALP.2020.133; preprint arXiv:2006.05498, https://arxiv.org/abs/2006.05498
6. Pieter Collins, Bernard Hanzon, Eike Neumann, On Positivity of Exponential-Trigonometric Polynomials and Irrationality Exponents, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026), Leibniz International Proceedings in Informatics (LIPIcs), vol. 386, pages 65:1-65:17, 2026. DOI: 10.4230/LIPIcs.MFCS.2026.65, https://doi.org/10.4230/LIPIcs.MFCS.2026.65
7. Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, James Worrell, Algorithmic Applications of Schanuel's Conjecture, in Principles of Formal Quantitative Analysis, Lecture Notes in Computer Science, vol. 15760, pages 118-138, Springer, 2025. DOI: 10.1007/978-3-031-97439-7_5, https://doi.org/10.1007/978-3-031-97439-7_5
8. Rajab Aghamov, Christel Baier, Toghrul Karimov, Joel Ouaknine, Jakob Piribauer, Linear dynamical systems with continuous weight functions, 27th ACM International Conference on Hybrid Systems: Computation and Control (HSCC 2024), pages 1-11. DOI: 10.1145/3641513.3650173, https://doi.org/10.1145/3641513.3650173; preprint arXiv:2405.06512, https://arxiv.org/abs/2405.06512
9. Rajab Aghamov, Christel Baier, Toghrul Karimov, Joël Ouaknine, Jakob Piribauer, Linear dynamical systems with weight functions, Nonlinear Analysis: Hybrid Systems, vol. 60, article 101680, 2026. DOI: 10.1016/j.nahs.2026.101680, https://doi.org/10.1016/j.nahs.2026.101680
10. Rizeng Chen, Bican Xia, Reduction of Transcendental Decision Problems over the Reals, Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation (ISSAC 2024), pages 56-64. DOI: 10.1145/3666000.3669675, https://doi.org/10.1145/3666000.3669675
11. Eike Neumann, On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions, 17th International Conference on Reachability Problems (RP 2023), Lecture Notes in Computer Science, pages 98-112. DOI: 10.1007/978-3-031-45286-4_8, https://doi.org/10.1007/978-3-031-45286-4_8; preprint arXiv:2307.00363, https://arxiv.org/abs/2307.00363
12. Stéphane Fischler, Tanguy Rivoal, Zeros of $E$-functions and of exponential polynomials defined over $\overline{\mathbb{Q}}$, preprint arXiv:2503.20345 (2025), https://arxiv.org/abs/2503.20345
13. André Platzer, Long Qian, Axiomatization of Compact Initial Value Problems: Open Properties, Journal of the ACM 72(6), 2025. DOI: 10.1145/3763228, https://doi.org/10.1145/3763228
14. Yuri Bilu, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, James Worrell, Skolem Meets Schanuel, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Leibniz International Proceedings in Informatics (LIPIcs), vol. 241, pages 20:1-20:15, 2022. DOI: 10.4230/LIPIcs.MFCS.2022.20, https://doi.org/10.4230/LIPIcs.MFCS.2022.20; preprint arXiv:2204.13417, https://arxiv.org/abs/2204.13417
15. Joel Ouaknine, James Worrell, Positivity Problems for Low-Order Linear Recurrence Sequences, 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 366-379. DOI: 10.1137/1.9781611973402.27, https://doi.org/10.1137/1.9781611973402.27; preprint arXiv:1307.2779, https://arxiv.org/abs/1307.2779
16. Bertrand Teguia Tabuguia, Hypergeometric-type sequences, Journal of Symbolic Computation, vol. 125, article 102328, 2024. DOI: 10.1016/j.jsc.2024.102328, https://doi.org/10.1016/j.jsc.2024.102328
17. Stefano Bonaccorsi, Bernard Hanzon, Giulia Lombardi, A generalized Budan-Fourier approach to generalized Gaussian and exponential mixtures, AIMS Mathematics 9(10):26499-26537, 2024. DOI: 10.3934/math.20241290, https://doi.org/10.3934/math.20241290