On Recurrent Reachability for
Continuous Linear Dynamical Systems
Ventsislav Chonev

Joël Ouaknine

arXiv:1507.03632v2 [] 8 May 2016

Institute of Science and Technology Austria
vchonev@ist.ac.at

James Worrell

University of Oxford
{joel,jbw}@cs.ox.ac.uk

finitely often then reduces to whether v T x(t) = 0 for infinitely
many values of t ≥ 0. Now the function f : R≥0 → R defined
T
by f (t) =
written as an exponential-polynomial
Pkv x(t) canαjbe
t
f (t) =
, where the αj and the coefficients of
j=1 Pj (t)e
each polynomial Pj are algebraic numbers. Thus the problem of
reaching a hyperplane infinitely often reduces to the Infinite Zeros
Problem: given an exponential polynomial f , decide whether f has
infinitely many non-negative real zeros. Note that since f is an analytic function on the whole real line it only has finitely many zeros
in a bounded interval. Thus the Infinite Zeros Problem is equivalent
to asking whether the set of zeros of f is unbounded.
This paper is concerned with the decidability of the Infinite
Zeros Problem. In order to formulate our main results, recall that
exponential polynomials can equivalently be characterised as the
solutions of ordinary differential equations

Abstract
The continuous evolution of a wide variety of systems, including
continous-time Markov chains and linear hybrid automata, can be
described in terms of linear differential equations. In this paper we
study the decision problem of whether the solution x(t) of a system of linear differential equations dx/dt = Ax reaches a target
halfspace infinitely often. This recurrent reachability problem can
equivalently be formulated as the following Infinite Zeros Problem:
does a real-valued function f : R≥0 → R satisfying a given linear
differential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most
7, then the Infinite Zeros Problem is decidable. On the other hand,
we show that a decision procedure for the Infinite Zeros Problem
at order 9 (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing
the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.

f (n) + an−1 f (n−1) + . . . + a0 f = 0 ,

Categories and Subject Descriptors F.2.m [Analysis of Algorithms and Problem Complexity]: Miscellaneous

(1)

with the coefficients aj and the initial conditions f (j) (0) being real
algebraic numbers for j ∈ {0, . . . , n − 1}. We say that f has order
n if it satisfies a linear differential equation of the form (1).
Our main results concern both decision procedures and hardness results for the Infinite Zeros Problem. We show that the problem is decidable for exponential polynomials of order at most 7.
With regards to hardness, we exhibit a reduction to show that decidability of the Continuous Infinite Zeros Problem for instances
of order at least 9 would entail major advancements in the field of
Diophantine Approximation, namely the computability of the Lagrange constants of arbitrary real algebraic numbers.
Let us expand on the significance of the above hardness result.
Essentially nothing is known about the Lagrange constant of any
real algebraic number of degree three or above. For example, it has
been a longstanding open problem since the 1930s whether some
real algebraic number of degree at least three has strictly positive
Lagrange constant and, on the other hand, whether some such number has Lagrange constant 0 (see, e.g., (Guy 2004)). These questions are often formulated in terms of the simple continued fraction
expansion of a real number α, which has unbounded elements if
and only if α has Lagrange constant 0.
The reader will notice that there is a gap between our decidability and hardness results for exponential polynomials of order 8.
We claim decidability in this case but defer the details to a longer
version of this paper.
Another way to calibrate the difficulty of the
Zeros
PInfinite
k
αj t
Problem for an exponential polynomial f (t) =
j=1 pj (t)e
is in terms of the dimension of the Q-vector space spanned by
{Im(αj ) : j = 1, . . . , k}. We show decidability in case this space
is one-dimensional and we observe that the above hardness result
already applies in the two-dimensional case.

Keywords linear dynamical systems, reachability, differential
equations, Diophantine Approximation, Skolem problem

1. Introduction
A simple type of continuous-time system is one that satisfies a
= Ax, where A is an n × n matrix
linear differential equation dx
dt
of rational numbers and x(t) ∈ Rn gives the system state at time t.
In particular, such differential equations describe the state evolution
of finite-state continuous-time Markov chains (via the so-called rate
equation) and the continuous evolution of linear hybrid automata.
A fundamental reachability question in this context is whether
x(t) infinitely often reaches a target hyperplane v T x = 0, where
v ∈ Rn is the normal vector. Such a hyperplane could represent a
transition guard in a hybrid automaton or a linear constraint on the
state probability distribution of a continuous-time Markov chain
(e.g., that the probability to be in a given state is exactly one half).
= Ax adA solution x(t) to the differential equation dx
dt
mits a matrix-exponential representation x(t) = eAt x(0). The
problem of whether x(t) reaches the hyperplane v T x = 0 in-

[Copyright notice will appear here once ’preprint’ option is removed.]

1

2018/3/15

1.1 Related Work

3. As a function of the form

Closely related to the Infinite Zeros Problem is the problem of
whether an exponential polynomial has some zero. This problem is considered in (Bell et al. 2010) under the name Continuous
Skolem-Pisot Problem. The techniques considered in the present
paper are relevant to the latter problem, but significant extra difficulties arise in this new setting since we cannot discount the behaviour of f on some bounded initial segment of the reals. Our
work on the Continuous Skolem-Pisot Problem will be reported
elsewhere.
There is a natural discrete analog of the Infinite Zeros Problem:
given a linear recurrence sequence, determine whether it has infinitely many zero terms. The decidability of the latter problem was
established by Berstel and Mignotte (Berstel and Mignotte 1976).
The problem of deciding whether a given linear recurrence sequence has some zero term is called Skolem’s Problem. This is a
longstanding and celebrated open problem which essentially asks
to give an effective proof of the Skolem-Mahler-Lech Theorem for
linear recurrences; see, e.g., the exposition of Tao (Tao 2008, Section 3.9).
Macintyre and Wilkie (Macintyre and Wilkie 1996) showed decidability of the first-order theory of hR, +, ×, 0, 1, <, expi, the
real field with exponentiation, subject to Schanuel’s Conjecture in
transcendence theory. In this paper we are concerned with the complex exponential function, and we do not use this result. Moreover,
although we do make use of transcendence theory, all the results in
this paper are unconditional.

f (t) =

bj,l tl cos(aj t + ϕj,l )

l=0

We refer the reader to (Bell et al. 2010, Theorem 7) for details.
2.2 Number-theoretic tools
Throughout this paper we denote by A the set of algebraic numbers.
Recall that a standard way to represent an algebraic number α
is by its minimal polynomial M and a numerical approximation
of sufficient accuracy to distinguish α from the other roots of
M (Cohen 1993, Section 4.2.1). Given two algebraic numbers α
and β under this representation, the Field Membership Problem is
to determine whether β ∈ Q(α) and, if so, to return a polynomial
P with rational coefficients such that β = P (α). This problem
can be decided using the LLL algorithm, see (Cohen 1993, Section
4.5.4).
Given the characteristic polynomial χ of a linear differential
equation we can compute approximations to each of its roots
λ1 , . . . , λn to within an arbitrarily small additive error (Pan 1996).
Moreover, by repeatedly using an algorithm for the Field Membership Problem we can compute a primitive element θ for the splitting
field of χ and representations of λ1 , . . . , λn as polynomials in θ.
Thereby we can determine maximal Q-linearly independent subsets of {Re(λj ) : 1 ≤ j ≤ n} and {Im(λj ) : 1 ≤ j ≤ n}.
We now move to some techniques from Transcendental Number Theory on which our results depend in a critical way. The
following theorem was originally proven in 1934 by A. Gelfond
(Gelfond 1934; Gelfond and Vinogradov 1934) and independently
by T. Schneider (Schneider 1935a,b), settling Hilbert’s seventh
problem in the affirmative.

We recall some facts about the general form of solutions of ordinary linear differential equations. Consider a homogeneous linear
differential equation

Theorem 1. (Gelfond-Schneider) If a and b are algebraic numbers
with a 6= 0, 1 and b 6∈ Q, then ab is transcendental.

(2)

of order n. The characteristic polynomial of (2) is

The following lemma, proven in (Bell et al. 2010), is a useful
consequence of the powerful Baker’s Theorem (Baker 1975, Theorem 3.1):

χ(x) := xn + cn−1 xn−1 + . . . + c0 .
If λ is a root of χ of multiplicity m, then the function f (t) = tj eλt
satisfies (2) for j = 0, 1, . . . , m − 1. There are n distinct linearly
independent solutions of (2) having this form, and these span the
space of all solutions.
Let the distinct roots of χ be λ1 , . . . , λk , with respective multiplicities m1 , . . . , mk . We refer to λ1 , . . . , λk as the characteristic
roots of the differential equation. We also refer to the characteristic roots of maximum real part as dominant. Write λj = rj + iaj
for real algebraic numbers rj , aj , j = 1, . . . , k. It follows from
the discussion above that, given real algebraic initial values of
f (0), f ′ (0), . . . , f (n−1) (0), the uniquely defined solution f of (2)
can be written in one of the following three equivalent forms.

Lemma 2. (Bell et al. 2010, Lemma 13) Let a, b ∈ R ∩ A be
linearly independent over Q and let ϕ1 , ϕ2 be logarithms of algebraic numbers, that is, eiϕ1 , eiϕ2 ∈ A. There exist effective
constants C, N, T > 0 such that for all t ≥ T , at least one of
1 − cos(at + ϕ1 ) > C/tN and 1 − cos(bt + ϕ2 ) > C/tN holds.
Another necessary tool is a version of Kronecker’s well-known
Theorem in Diophantine Approximation.
Theorem 3. (Kronecker, appears in (Hardy and Wright 1999)) Let
λ1 , . . . , λm and x1 , . . . , xm be real numbers. Suppose that for all
integers u1 , . . . , um such that u1 λ1 + · · · + um λm ∈ Z, we also
have u1 x1 + · · · + um xm ∈ Z, that is, all integer relations among
the λj also hold among the xj (modulo Z). Then for all ǫ > 0,
there exist p ∈ Zm and n ∈ N such that |nλj − xj − pj | < ǫ
for all 1 ≤ j ≤ m. In particular, if 1, λ1 , . . . , λm are linearly
independent over Z, then there exist such n ∈ N and p ∈ Zm for
all x ∈ Rm and ǫ > 0.

1. As an exponential polynomial
k
X

X

where bj,l is real algebraic and eiϕj,l algebraic for each j, l.

2.1 General Form of a Solution

f (t) =

ml −1

e rj t

j=1

2. Mathematical Background

f (n) + cn−1 f (n−1) + . . . + c0 f = 0

k
X

Pj (t)eλj t

j=1

where each Pj is a polynomial with (complex) algebraic coefficients and degree at most mj − 1.

A direct consequence is the following:

2. As a function of the form
k
X
erj t (Pj (t) cos(aj t) + Qj (t) sin(aj t))
f (t) =

Lemma 4. Let a1 , . . . , am ∈ R ∩ A be linearly independent
over Q and let ϕ1 , . . . , ϕm ∈ R. Write x mod 2π to denote
mink∈Z |x + 2kπ| for any x ∈ R. Then the image of the mapping
h(t) : R≥0 → [0, 2π)m given by

j=1

where the polynomials Pj , Qj have real algebraic coefficients
and degrees at most mj − 1.

h(t) = ((a1 t + ϕ1 ) mod 2π, . . . , (am t + ϕm ) mod 2π)

2

2018/3/15

is dense in [0, 2π)m . Moreover, the set

sign of the coefficient of the dominant term in the expansion of
P (ea1 t , . . . , eak t ) as an exponential polynomial. It follows that
the sign of P (ea1 t , . . . , eak t ) is eventually constant. It is moreover clear that one can effectively compute a threshold beyond
which the sign of P (ea1 t , . . . , eak t ) remains the same. Since
the set S is defined by a Boolean combination of inequalities
P (u1 , . . . , uk ) ∼ 0, for ∼ ∈ {<, =}, the proposition immediately follows.

{h(t) | (a1 t + ϕ1 ) mod 2π = 0}

is dense in {0} × [0, 2π)m−1 .

Proof. For the first part of the claim, note that the linear independence of 1, a1 /2π, . . . , am /2π follows from the linear independence of a1 , . . . , am and the transcendence of π. Then by
Kronecker’s Theorem, the restriction {h(t) | t ∈ N} is dense in
[0, 2π)m , so certainly the whole image of h(t) must also be dense
in [0, 2π)m . For the second part, the trajectory h(t) has zero first
coordinate precisely when t = −ϕ1 /a1 + 2nπ for some n ∈ Z, at
which times the trajectory is


−ϕ1
def
+ 2nπ
g(n) = h
a1


a1 ϕj − ϕ1 aj
2πaj
+
mod 2π
= {0} × n
a1
a1
2≤j≤m

2.4 Useful Results About Exponential Polynomials
We restate two useful theorems due to Bell et al. (Bell et al. 2010).
Theorem 6. (Bell et al. 2010, Theorem 12) Exponential polynomials with no real dominant characteristic roots have infinitely many
zeros.
Theorem 7. (Bell et al. 2010, Theorem 15) Suppose we are given
an exponential polynomial whose dominant characteristic roots are
simple, at least four in number and have imaginary parts linearly
independent over Q. Then the existence of infinitely many zeros is
decidable.

As before, we have that {1, 2πa2 /a1 , . . . , 2πam /a1 } are linearly
independent over Q from the linear independence of a1 , . . . , am
and the transcendence of π, so applying Kronecker’s Theorem to
the last m − 1 components of this discrete trajectory yields the
second part of the claim.

3. One Linearly Independent Oscillation
In
we consider exponential polynomials f (t) =
Pkthis section
λj t
P
(t)e
under the assumption that the span of {Im(λj ) :
j
j=1
j = 1, . . . , k} is a one-dimensional Q-vector space. In this case we
can use fundamental geometric properties of semi-algebraic sets to
decide whether or not f has finitely many zeros.
P
Theorem 8. Let f (t) = kj=1 Pj (t)eλj t be an exponential polynomial such that the span of {Im(λj ) : j = 1, . . . , k} is a onedimensional Q-vector space. Then the existence of infinitely many
zeros of f is decidable.

2.3 First-Order Theory of the Reals
We denote by L the first-order language hR, +, ×, 0, 1, <i. Atomic
formulas in this language are of the form P (x1 , . . . , xn ) = 0 and
P (x1 , . . . , xn ) > 0 for P ∈ Z[x1 , . . . , xn ] a polynomial with
integer coefficients. A set X ⊆ Rn is definable in L if there exists
some L-formula φ(x̄) with free variables x̄ which holds precisely
for valuations in X. Analogously, a function is definable if its graph
is a definable set.
We denote by Th(R) the first-order theory of the reals, that
is, the set of all valid sentences in the language L. It is worth remarking that any real algebraic number is readily definable within
L using its minimal polynomial and a rational approximation to
distinguish it from the other roots. Thus, we can treat real algebraic numbers constants as built into the language and use them
freely in the construction of formulas. A celebrated result due to
Tarski (Tarski 1951) is that the first-order theory of the reals admits quantifier elimination: that each formula φ1 (x̄) in L is equivalent to some effectively computable formula φ2 (x̄) which uses
no quantifiers. This immediately entails the decidability of Th(R).
It also follows that sets definable in L are precisely the semialgebraic sets. Tarski’s original result had non-elementary complexity,
but improvements followed, culminating in the detailed analysis of
Renegar (Renegar 1992).
Decidability and geometrical properties of definable sets in the
first-order theory of the structure Lexp = hR, +, ×, 0, 1, <, expi,
the reals with exponentiation, have been explored by a number of
authors. Most notably, Wilkie (Wilkie 1996) showed that the theory is o-minimal and Macintyre and Wilkie (Macintyre and Wilkie
1996) showed that if Schanuel’s conjecture is true then the theory
is decidable. We will not need the above two results in this paper,
however we use the following, which is very straightforward to establish directly.

Proof. Write λj = aj + ibj , where aj , bj are real algebraic numbers for j = 1, . . . , k. By assumption there is a single real algebraic
number b such that each bj is an integer multiple of b. Recall that
for each integer n, both cos(nbt) and sin(nbt) can be written as
polynomials in sin(bt) and cos(bt) with integer coefficients. Using
this fact we can write f in the form
f (t) = Q(t, ea1 t , . . . , eak t , cos(bt), sin(bt)) ,
for some multivariate polynomial Q with algebraic coefficients.
Now consider the semi-algebraic set
n


o
2
2s
E := (u, s) ∈ Rk+2 : Q u0 , . . . , uk , 1−s
,
=
0
.
2
2
1+s
1+s
n

o
1−s2
Recall that
, 2s
: s ∈ R comprises all points in the
1+s2 1+s2

unit circle in R2 except (−1, 0). Indeed, given θ ∈ (−π, π),
2
and sin(θ) =
setting s := tan(θ/2) we have cos(θ) = 1−s
1+s2
2s
.
It
follows
that
f
(t)
=
0
and
cos(bt)
=
6
−1
imply that
1+s2
(t, ea1 t , . . . , eak t , tan(bt/2)) ∈ E.
By the Cell Decomposition Theorem for semi-algebraic sets
(Marker 2002), there are semi-algebraic sets C1 , . . . , Cm ⊆ Rk+2 ,
D1 , . . . , Dm ⊆ Rk+1 , and continuous semi-algebraic functions
(1)
(2)
ξj , ξj , ξj : Dj → R such that E can be written as a disjoint
union E = C1 ∪ . . . ∪ Cm , where either

Proposition 5. There is a procedure that, given a semi-algebraic
set S ⊆ Rk and real algebraic numbers a1 , . . . , ak , returns an
integer T such that {t ≥ 0 : (ea1 t , . . . , eak t ) ∈ S} either contains
the interval (T, ∞) or is disjoint from (T, ∞). The procedure also
decides which of these two eventualities is the case.

Cj = {(u, s) ∈ Rk+2 : u ∈ Dj ∧ s = ξj (u)}

(3)

or

Proof. Consider a polynomial P ∈ Z[u1 , . . . , uk ]. For suitably large t the sign of P (ea1 t , . . . , eak t ) is identical to the

(1)

(2)

Cj = {(u, s) ∈ Rk+2 : u ∈ Dj ∧ ξj (u) < s < ξj (u)}
3

(4)

2018/3/15

s

ηj
T

t

Figure 1. Intersection points of ηj (t) and tan(bt/2).
Moreover such a decomposition is computable from E. Clearly
then
m
[
{t ∈ R : (t, ea1 t , . . . , eak t ) ∈ Dj }∪Z ,
{t ∈ R : f (t) = 0} ⊆
j=1

where Z := {t ∈ R : cos(bt) = −1}.
The restriction of the exponential polynomial f to Z is given
by f (t) = Q(t, ea1 t , . . . , eak t , −1, 0). Since this expression is a
linear combination of terms of the form tj ert for real algebraic r,
for sufficiently large t the sign of f (t) is determined by the sign
of the coefficient of the dominant term. Thus f is either identically
zero on Z (in which case f has infinitely many zeros) or there exists
some threshold T such that all zeros of f in Z lie in the interval
[0, T ].
We now consider zeros of f that do not lie in Z. There are two
cases. First suppose that each set {t ∈ R : (t, ea1 t , . . . , eak t ) ∈
Dj } is bounded for j = 1, . . . , m. In this situation, using Proposition 5, we can obtain an upper bound T such that if f (t) =
0 then t < T . On the other hand, if some set {t ∈ R≥0 :
(t, ea1 t , . . . , eak t ) ∈ Dj } is unbounded then, by Proposition 5,
it contains an infinite interval (T, ∞). We claim that in this case f
must have infinitely many zeros t ≥ 0. We first give the argument
in the case Cj satisfies (3).
Define ηj (t) = ξj (t, ea1 t , . . . , eak t ) for t ∈ (T, ∞). Then for
t ∈ (T, ∞) \ Z,
f (t) = 0

⇐=

⇐⇒

part as the dominant characteristic roots. Let also mul(λ) denote
the multiplicity of λ as a root of the characteristic polynomial of f .
We will now perform a case analysis on the number of dominant
characteristic roots. By Theorem 6, it is sufficient to confine our
attention to exponential polynomials with an odd number of dominant characteristic roots. Throughout, we rely on known general
forms of solutions to ordinary linear differential equations, outlined
in Section 2.1.
Case I. Suppose first that there is only one dominant, necessarily
real, root r. Then if we divide f by ert , we have:


f (t)
= P1 (t) + O e(r2 −r)t ,
rt
e
as the contribution of the non-dominant roots shrinks exponentially,
relative to that of the dominant root. Thus, for large t ≥ 0, the sign
of f (t) matches the sign of the leading coefficient of P1 (t), so f
cannot have infinitely many zeros.
Case II. We now move to the case of three dominant characteristic roots: r and r ± ia, so that


f (t)
= P1 (t) + P2 (t) cos(at) + P3 (t) sin(at) + O e(r2 −r)t ,
rt
e
def

where P1 , P2 , P3 ∈ (R ∩ A)[x] have degrees d1 = deg(P1 ) ≤
def
mul(r) − 1 and d2 = deg(P2 ) = deg(P3 ) ≤ mul(r ± ai).
Case IIa. Suppose d1 > d2 . Now, it is easy to see that for large
t the sign of f (t) matches the sign of the leading coefficient p1 of
P1 :


f (t)
(r2 −r)t
=
p
+
O(1/t)
+
O
e
,
1
ert td1
so clearly some bound T exists such that t > T ⇒ f (t) 6= 0.
Similarly, if d2 > d1 , then f (t) clearly has infinitely many zeros.
Indeed, if p2 , p3 are the leading coefficients of P2 , P3 , respectively,
then we have:


f (t)
= p2 cos(at) + p3 sin(at) + O(1/t) + O e(r2 −r)t
rt
d
2
e t


cos(at + ϕ)
(r2 −r)t
= p 2
+
O(1/t)
+
O
e
p2 + p23

(t, ea1 t , . . . , eak t , tan(bt/2)) ∈ Cj

(t, ea1 t , . . . , eak t ) ∈ Dj ∧ ηj (t) = tan(bt/2).

where ϕ ∈ [0, 2π) with tan(ϕ) = −p3 /p2 , so f is infinitely often
positive and infinitely often negative.
Thus, we can now assume d1 = d2 . Notice that since the order
of our exponential polynomial is no greater than 7, we must have
d1 = d2 ≤ 2.
Case IIb. Suppose that d1 = d2 = 2. Then our function is of
the form
f (t)
= t(A cos(at+ϕ1 )+B)+(C cos(at+ϕ2 )+D)+e(r2 −r)t F,
ert

In other words, f has a zero at each point t ∈ (T, ∞) \ Z at
which the graph of ηj intersects the graph of tan(bt/2). Since
ηj is continuous there are clearly infinitely many such intersection
points, see Figure 1.
The case when Cj satisifes (4) is handled similarly. In fact,
this case cannot arise at all, since by the above argument, if Cj
satisfies (4), then f has a non-trivial interval of zeros. This is
impossible, since f is analytic, and hence has only isolated zeros.
This completes the proof.

for constants A, B, C, D, F, a ∈ R∩A with a > 0 and eiϕ1 , eiϕ2 ∈
A. In this case, Theorem 9 follows from Lemma 16 in Section 4.4.
Case IIc. Suppose that d1 = d2 = 1, so that

4. Decidability Results up to Order 7

f (t)
= A1 cos(at + ϕ1 ) + A2 + e(r2 −r)t F1 (t),
ert

We now shift our attention to instances of the Infinite Zeros Problem of low order. In particular, for exponential polynomials corresponding to differential equations of order at most 7, we establish
decidability of the Infinite Zeros Problem.

where A1 , A2 , a ∈ R ∩ A, a > 0, eiϕ1 ∈ A and F1 is an
exponential polynomial with dominant characteristic root whose
real part is 0. Consider first the magnitudes of A1 and A2 . If
|A1 | > |A2 |, then the term A1 cos(at + ϕ1 ) makes f change
sign infinitely often, so f must have infinitely many zeros. On the
other hand, if |A1 | < |A2 |, then f is clearly ultimately positive
or ultimately negative, depending on the sign of A2 . The remaining
case is that |A1 | = |A2 |. Dividing f by A2 , replacing ϕ1 by ϕ1 +π
if needed and scaling constants by A2 as necessary, we can assume

Theorem 9. The Infinite Zeros Problem is decidable for differential
equations of order at most 7.
Proof. Suppose we are given an exponential polynomial f of order
at most 7. Sort the characteristic roots according to their real parts,
and let rj denote throughout the j-th largest real part of a characteristic root. We will refer to the characteristic roots of maximum real

4

2018/3/15

where A, B, C, a, b ∈ R ∩ A, a, b > 0, eiϕ1 , eiϕ2 ∈ A and F
is an exponential polynomial of order at most 2 whose dominant
characteristic roots have real part equal to 0. In this case, Theorem
9 follows from Lemma 14 in Section 4.2.
Case IV. Finally, suppose there are seven dominant characteristic roots: r, r ±ai, r ±bi and r ±ci. Since we are limiting ourselves
to instances of order 7, these roots must all be simple, and there can
be no other characteristic roots. Thus, the exponential polynomial
has the form
f (t)
= A cos(at + ϕ1 ) + B cos(bt + ϕ2 ) + C cos(ct + ϕ3 ) + D,
ert
with A, B, C, D, a, b, c ∈ R ∩ A, a, b, c > 0 and eiϕ1 , . . . , eiϕ3 ∈
A. In this case, Theorem 9 follows from Lemma 15 in Section 4.3.

the function has the form:
f (t)
= 1 − cos(at + ϕ1 ) + e(r2 −r)t F1 (t).
ert
We now enumerate the possibilities for the dominant characteristic
roots of the exponential polynomial F1 , that is, the characteristic
roots of f with second-largest real part. Since f has order at most
7, there are the following cases to consider:
• F1 has four simple, necessarily complex, dominant roots, so

that
f (t)
= 1 − cos(at + ϕ1 )
ert
+ e(r2 −r)t (B cos(bt + ϕ2 ) + C cos(ct + ϕ3 )),
where B, C, b, c ∈ R ∩ A with b, c > 0 and eiϕ2 , eiϕ3 ∈ A. In
this case, Theorem 9 follows from Lemma 12 in Section 4.1.
• F1 has some subset of one real and two complex numbers as
dominant roots, all simple, so that

In the remainder of this section, we provide the technical lemmas invoked throughout the proof of Theorem 9.
4.1 One dominant oscillation
Lemma 10. Let A, B, a, b, r ∈ R ∩ A where a, b, r > 0. Let
ϕ1 , ϕ2 ∈ R be such that eiϕ1 , eiϕ2 ∈ A. Suppose also that a, b are
linearly dependent over Q and that whenever 1−cos(at+ϕ1 ) = 0,
it holds that A cos(bt + ϕ2 ) + B > 0. Define the function

f (t)
= 1 − cos(at + ϕ1 )
ert
+ e(r2 −r)t (B cos(bt + ϕ2 ) + C) + e(r3 −r)t F2 (t),
where B, C, b ∈ R ∩ A, b > 0, eiϕ2 ∈ A and F2 is an exponential polynomial with dominant characteristic root whose
real part is 0. In this case, Theorem 9 follows from Lemma 11
in Section 4.1.
• F1 has a repeated real and possibly two simple complex dominant roots, so that

f (t) = 1 − cos(at + ϕ1 ) + e−rt (A cos(bt + ϕ2 ) + B).

Then f (t) = Ω(e−rt ), that is, there exist effective constants T ≥ 0
and c > 0 such that for t ≥ T , we have f (t) ≥ ce−rt .
Proof. The case of A = 0 is easy: by the premise of the Lemma, we
have B > 0 and then f (t) ≥ Be−rt for all t. Thus, assume A 6= 0
throughout. Let the linear dependence between a, b be given by
an1 −bn2 = 0 for n1 , n2 ∈ N coprime and let C be the equivalence
class of −ϕ1 /a modulo 2π/a, that is,


−ϕ1 + 2kπ
def
C =
k∈Z .
a

f (t)
= 1 − cos(at + ϕ1 )
ert
+ e(r2 −r)t (B cos(bt + ϕ2 ) + P (t)) + e(r3 −r)t F2 (t),
where B, b ∈ R ∩ A, b > 0, eiϕ2 ∈ A, and P ∈ (R ∩ A)[x] is
non-constant. Now, if the leading coefficient of P is negative,
then f will be infinitely often negative (consider large times
t such that cos(at + ϕ1 ) = 1) and infinitely often positive
(consider large times t such that cos(at + ϕ1 ) = 0), so f must
have infinitely many zeros. On the other hand, if the leading
coefficient of P is positive, then it is easy to see that f is
ultimately positive.
• F1 has a repeated pair of complex roots, so that

We will refer to C as the set of critical points throughout.
It is clear that at critical points, we have 1 − cos(at + ϕ1 ) = 0.
Moreover, the linear dependence of a, b entails that for each fixed
value of (cos(at), sin(at)), there are only finitely many possible
values for (cos(bt), sin(bt)). Indeed, we have
eibt ∈ {ωeiatn1 | ω an n2 -th root of unity},

so in particular, for t ∈ C, we have

f (t)
= 1 − cos(at + ϕ1 )
ert
+ e(r2 −r)t (Bt cos(bt + ϕ2 ) + C cos(bt + ϕ3 )),
iϕ2

eibt ∈ {ωe−in1 ϕ1 | ω an n2 -th root of unity}.

Thus, the possible values of (cos(bt), sin(bt)) for t critical are
def
algebraic and effectively computable. Let M = min{A cos(bt +
ϕ2 ) + B | t ∈ C}. By the premise of the Lemma, we have M > 0.
Let t1 , t2 , . . . , tj , . . . be the non-negative critical points. Note
that by construction we have |tj − tj−1 | = 2π/a. For each tj ,
define the critical region to be the interval [tj − δ, tj + δ], where

iϕ3

where B, C, b ∈ R ∩ A, b > 0 and e , e
∈ A. In this case,
Theorem 9 follows from Lemma 13 in Section 4.1.
Case III. We now consider the case of five dominant characteristic roots. Let these be r, r ± ai and r ± bi. If r ± ai are
repeated, i.e., mul (r ± ai) ≥ 2, then we must have mul(r) =
mul(r ± bi) = 1, since otherwise the order of our exponential
polynomial exceeds 7. Then by an argument analogous to Case IIa
above, f must have infinitely many zeros. The situation is symmetric when mul(r ± bi) ≥ 2. Similarly, if mul (r) ≥ 2, then
mul(r ± ai) = mul(r ± bi) = 1, since otherwise the instance
exceeds order 7. Then by the same argument as in Case IIa, f is ultimately positive or ultimately negative. Thus, we may assume that
all the dominant roots are simple, so the exponential polynomial is
of the form:
f (t)
= A cos(at + ϕ1 ) + B cos(bt + ϕ2 ) + C + e(r2 −r)t F (t),
ert

def

δ =

M
.
2|A|b

def

Let g(t) = A cos(bt + ϕ2 ) + B and notice that g ′ (t) ≤ |A|b
everywhere. We first prove the claim for t inside critical regions:
suppose t lies in a critical region and let j minimise |t − tj | ≤ δ.
Then by the Mean Value Theorem, we have
M
,
|g(t) − g(tj )| ≤ |t − tj ||A|b ≤ δ|A|b =
2
so
M
M
g(t) ≥ g(tj ) −
≥
,
2
2
5

2018/3/15

whence f (t) ≥ e−rt g(t) ≥ M e−rt /2 = Ω(e−rt ).
Now suppose t is outside all critical regions and let j minimise
|t − tj |. Since the distance between critical points is 2π/a by
construction, we have a|t − tj | ≤ π. Therefore,
1 − cos(at + ϕ1 ) = 1 − cos(at − atj ) ≥

Now, if D < 0, it is easy to show that f has infinitely many zeros.
Indeed, consider the times t where the dominant term 1 − cos(at +
ϕ1 ) vanishes. For all large enough such t, since t−N shrinks more
slowly than e−r2 t , we will have

|a(t − tj )|2
2

f (t) = e−r1 t D(1 − cos(bt + ϕ2 )) + e−(r1 +r2 )t F (t)
< e−r1 t (EDt−N + e−r2 t F (t))
1
≤ e−r1 t EDt−N
2
< 0,

(aδ)2
a2 M 2
>
=
> 0.
2
8|A|2 b2
Thus, there exists a computable constant D > 0 such that f (t) =
1 − cos(at + ϕ1 ) + e−rt g(t) ≥ D for all large enough t outside
critical regions.
Combining the two results, we have f (t) = Ω(e−rt ) everywhere.

so f has infinitely many zeros. Similarly, if D > 0, we can show
that f is ultimately positive. Indeed, for all t large enough, we have
f (t) ≥ e−r1 t D(1 − cos(bt + ϕ2 )) + e−(r1 +r2 )t F (t)

Lemma 11. Let C, D, a, b, r1 , r2 be real algebraic numbers such
that a, b, r1 , r2 > 0 and C, D are not both 0. Let also ϕ1 , ϕ2 ∈ R
be such that eiϕ1 , eiϕ2 ∈ A. Define the exponential polynomial f
by

> e−r1 t DEt−N + e−(r1 +r2 )t F (t)
> 0,

f (t) = 1 − cos(at + ϕ1 )

or

+ e−r1 t (C cos(bt + ϕ2 ) + D) + e−(r1 +r2 )t F (t).

f (t) ≥ 1 − cos(at + ϕ1 ) + e−(r1 +r2 )t F (t)

Here F is an exponential polynomial whose dominant characteristic roots are purely imaginary. Suppose also that f has order at
most 7. Then it is decidable whether f has infinitely many zeros.

> Et−N + e−(r1 +r2 )t F (t)
> 0.

Proof. Notice that the dominant term of f is always non-negative,
so the function is positive for arbitrarily large t. Thus, f (t) = 0 for
some t if and only if f (t) ≤ 0 for some t, and analogously, f has
infinitely many zeros if and only if f (t) ≤ 0 infinitely often. We
can eliminate the case |D| > |C|, since then f is clearly ultimately
positive or oscillating, depending on the sign of D. Thus, we can
assume |D| ≤ |C|.
We now consider two cases, depending on whether a/b ∈ Q.
Case I. Suppose first that a, b are linearly independent over Q.
By Lemma 4, the trajectory (at + ϕ1 mod 2π, bt + ϕ2 mod 2π)
is dense in [0, 2π)2 , and moreover the restriction of this trajectory
to at + ϕ1 mod 2π = 0 is dense in {0} × [0, 2π).
If |D| < |C|, then we argue that f is infinitely often negative,
and hence has infinitely many zeros. Indeed, |D| < |C| entails the
existence of a non-trivial interval I ⊆ [0, 2π) such that

Therefore, f has only finitely many zeros.
Case II. Now suppose a, b are linearly dependent. By the
premise of the Lemma, the order of F is at most 2 (in fact, at
most 1 if D 6= 0). However, by Theorem 8, the claim follows immediately for all cases in which the characteristic roots of F are
all real or complex but with frequencies linearly dependent on a.
Thus, the only remaining case to consider is the function
f (t) = 1 − cos(at + ϕ1 )

+ e−r1 t C cos(bt + ϕ2 ) + e−(r1 +r2 )t H cos(ct + ϕ3 ),

where H, c ∈ R ∩ A, c > 0 and a/c 6∈ Q.
As explained at the beginning of the proof of Lemma 10, due to
the linear dependence of a, b over Q, when 1 − cos(at + ϕ1 ) = 0,
there are only finitely many possibilities for the value of C cos(bt+
ϕ2 ), each algebraic, effectively computable and occurring periodically. If at least one of these values is non-positive, then by the
linear independence of a, c over Q, we will simultaneously have
1−cos(at+ϕ1 ) = 0, C cos(bt+ϕ2 ) ≤ 0 and H cos(ct+ϕ3 ) < 0
infinitely often, which yields f (t) < 0 infinitely often and entails the existence of infinitely many zeros. On the other hand,
if at the critical points 1 − cos(at + ϕ1 ) = 0 we always have
C cos(bt + ϕ2 ) > 0, then by Lemma 10, we have

t mod 2π ∈ I ⇒ C cos(bt + ϕ2 ) + D < 0.

What is more, we can in fact find ǫ > 0 and a subinterval I ′ ⊆ I
such that
t mod 2π ∈ I ′ ⇒ C cos(bt + ϕ2 ) + D < −ǫ.
Thus, by density, 1 − cos(at + ϕ1 ) = 0 and C cos(bt + ϕ2 ) + D <
−ǫ will infinitely often hold simultaneously. Then just take t large
enough to ensure, say, |e−r2 t F (t)| < ǫ/2 at these infinitely many
points, and the claim follows.
Thus, suppose now |C| = |D|. Replacing ϕ2 by ϕ2 + π if
necessary, we can write the function as:

1 − cos(at + ϕ1 ) + e−r1 t C cos(bt + ϕ2 ) = Ω(e−r1 t ),
whereas obviously
e−(r1 +r2 )t H cos(ct + ϕ3 ) = O(e−(r1 +r2 )t ).

f (t) = 1 − cos(at + ϕ1 )

If follows that f is ultimately positive and hence has only finitely
many zeros.

+ De−r1 t (1 − cos(bt + ϕ2 )) + e−(r1 +r2 )t F (t).

As a, b are linearly independent, for all t large enough, 1 −
cos(at + ϕ1 ) and 1 − cos(bt + ϕ2 ) cannot simultaneously be ‘too
small’. More precisely, by Lemma 2, there exist effective constants
E, T, N > 0 such that for all t ≥ T , we have

Lemma 12. Let A, B, a, b, c, r be real algebraic numbers such
that a, b, c, r > 0, A, B 6= 0. Let also ϕ1 , ϕ2 , ϕ3 ∈ R be such
that eiϕ1 , eiϕ2 , eiϕ3 ∈ A. Define the exponential polynomial f by

f (t) = 1−cos(ct+ϕ3 )+e−rt (A cos(at+ϕ1 )+B cos(bt+ϕ2 )).

1 − cos(at + ϕ1 ) > E/tN or 1 − cos(bt + ϕ2 ) > E/tN .

Then it is decidable whether f has infinitely many zeros.

6

2018/3/15

We are now interested in the extrema of P (sin(t), cos(t)). Let

Proof. We argue the function is infinitely often positive and infinitely often negative by looking at the values of t for which the
dominant term 1 − cos(ct + ϕ3 ) vanishes. This happens precisely
at the times t = −(ϕ3 + 2kπ)/c for k ∈ Z, giving rise to a discrete
restriction of f :



k
2πa
aϕ3
def
g(k) = erϕ3 e2πr
A cos k
−
+ ϕ1 +
c
c


bϕ3
2πb
.
−
+ ϕ2
B cos k
c
c

def

M1 =
def

M2 =

min

x2 +y 2 =1

P (x, y) = min α(t),
t≥0

max P (x, y) = max α(t).
t≥0

x2 +y 2 =1

We can construct defining formulas φ1 (u), φ2 (u) in the first-order
language L of real closed fields for M1 , M2 , so that each φj (u)
holds precisely for the valuation u = Mj . Then performing quantifier elimination on these formulas using Renegar’s algorithm
(Renegar 1992), we convert φ1 , φ2 into the form
_^
Pl,k (u) ∼l,k 0,
φj (u) ≡

This is a linear recurrence sequence over R of order 4, with characteristic roots e2π(r±ia/c) and e2π(r±ib/c) . In particular, it has no
real dominant characteristic root. It is well-known that real-valued
linear recurrence sequences with no dominant real characteristic
root are infinitely often positive and infinitely often negative: see
for example (Győri and Ladas 1991, Theorem 7.1.1). Therefore, by
continuity, f must have infinitely many zeros.

l

k

where Pl,k are polynomials with integer coefficients and each ∼l,k
is either < or =. Now φj (u) must have a satisfiable disjunct. Using
the decidability of the theory Th(R), we can readily identify this
disjunct. Moreover, since φj (u) has a unique satisfying valuation,
namely u = Mj , this disjunct must contain at least one equality predicate. It follows immediately that M1 , M2 are algebraic.
Moreover, we can effectively compute from φj (u) a representation for Mj consisting of its minimal polynomial and a sufficiently
accurate rational approximation to distinguish Mj from its Galois
conjugates. By an analogous argument, the pairs (sin(t), cos(t))
at which P (sin(t), cos(t)) achieves the extrema M1 , M2 are also
algebraic and effectively computable.
We now perform a case analysis on the signs of M1 and M2 .

Lemma 13. Let A, B, a, b, r be real algebraic numbers such that
a, b, r > 0, A 6= 0. Let also ϕ1 , ϕ2 , ϕ3 ∈ R be such that
eiϕ1 , eiϕ2 , eiϕ3 ∈ A. Define the exponential polynomial f by

f (t) = 1−cos(at+ϕ1 )+e−rt (At cos(bt+ϕ2 )+B cos(bt+ϕ3 )).
Then it is decidable whether f has infinitely many zeros.
Proof. If a/b ∈ Q, then the claim follows immediately from
Theorem 8. If a/b 6∈ Q, then by Lemma 4, it will happen infinitely
often that 1 − cos(at + ϕ1 ) = 0 and At cos(bt + ϕ2 ) < −|A|t/2.
Then clearly f (t) < 0 infinitely often. Since f (t) > 0 infinitely
often as well, due to the non-negative dominant term 1 − cos(at +
ϕ1 ), it follows that f has infinitely many zeros.

• First, if 0 < M1 ≤ M2 , then f (t) cannot have infinitely many

zeros: if t is large enough to ensure |β(t)| < M1 , we have
f (t) > 0.
• Second, if M1 ≤ M2 < 0, then by the same reasoning, the
function will ultimately be strictly negative.
• Third, if M1 < 0 < M2 , then f oscillates around 0: for
all t such that α(t) = M1 < 0 and large enough to ensure
|β(t)| < |M1 |, we will have f (t) < 0, and similarly, for large
enough t such that α(t) = M2 > 0, we will have f (t) > 0, so
the function must have infinitely many zeros.
• Next, we argue that the case M1 = M2 = 0 is impossible.
Indeed, if M1 = M2 = 0, then α(t) = P (sin(t), cos(t)) is
identically zero, and the same holds for all derivatives of α(t).
Thus, from α′ (t) ≡ α′′′ (t) ≡ 0, we have

4.2 Two dominant oscillations
Lemma 14. Let A, B, C, a, b, r be real algebraic numbers such
that a, b, r > 0, a 6= b and A, B, C 6= 0. Let also ϕ1 , ϕ2 ∈ R be
such that eiϕ1 , eiϕ2 ∈ A. Define the exponential polynomial f by
f (t) = A cos(at + ϕ1 ) + B cos(bt + ϕ2 ) + C + e−rt F (t).

where F is an exponential polynomial whose dominant characteristic roots are purely imaginary. Suppose also f has order at most
8. It is decidable whether f has infinitely many zeros.

0 ≡ −Am sin(mt + ϕ1 ) − Bn sin(nt + ϕ2 ),

0 ≡ Am3 sin(mt + ϕ1 ) + Bn3 sin(nt + ϕ2 ).

Proof. If the frequencies a, b of the dominant term’s oscillations are
linearly independent over Q, then the claim follows immediately by
Theorem 7. Therefore, assume na − mb = 0 for some n, m ∈ N+ .
Notice that a 6= b guarantees n 6= m. We perform the change of
variable t → tm/a, so that:

f (t) = P (sin(t), cos(t)) + e−rmt/a F (tm/a),

Multiplying the first identity through by m2 and summing, we
have
Bn sin(nt + ϕ2 )(n2 − m2 ) ≡ 0.
By the premise of the Lemma, B 6= 0, so n(n − m)(n + m) =
0, which is a contradiction.
• Finally, only the symmetric cases M1 < M2 = 0 and 0 =
M1 < M2 remain. Without loss of generality, by replacing f
by −f if necessary, we need only consider the case 0 = M1 <
M2 .

where P ∈ (R ∩ A)[x, y] has effectively computable coefficients.
It is clear that the dominant term is periodic. It is immediate from
the definition of exponential polynomials and the premise of the
def
Lemma that F (tm/a) = F2 (t) is an exponential polynomial in
t, of the same order as F (t), also with purely imaginary dominant
def
def
characteristic roots. Let α(t) = P (sin(t), cos(t)), r2 = rm/a >
def −rmt/a
−r2 t
0 and β(t) = e
F (tm/a) = e
F2 (t).

Thus, assume 0 = M1 < M2 . We now move our attention to
the possible forms of F2 . Since f has order at most 8, it follows that
F2 has order at most 3. Thus, there are three possibilities for the set
of dominant characteristic roots of F2 : {0}, {±ic}, or {0, ±ic},
for some positive c ∈ R ∩ A. We consider each of these cases in
turn.
First, if F2 only has the real dominant eigenvalue 0, then F2 is
ultimately positive or ultimately negative, depending on the sign of

f (t) = A cos(mt+ϕ1 )+B cos(nt+ϕ2 )+C+e−rmt/a F (tm/a).
Using the standard trigonometric identities, we express the dominant term as a polynomial in sin(t), cos(t):

7

2018/3/15

formulas in the first-order language L of real closed fields, and then
perform quantifier elimination using Renegar’s algorithm (Renegar
1992). Then f clearly has infinitely many zeros if and only if
M1 ≤ 0 ≤ M2 .
Case III. Finally, suppose that a, b, c span a Q-vector space
of dimension 2, so that a, b, c satisfy a single linear dependence
am + bn + cp = 0 where m, n, p ∈ Z are coprime. At most
one of the ratios a/b, a/c and b/c is rational (otherwise we have
dim span{a, b, c} = 1), so assume without loss of generality that
a/c 6∈ Q and b/c 6∈ Q.
Define the set
def 
T = x ∈ [0, 2π)3 ∀u ∈ Z3 . u · (a, b, c) ∈ 2πZ ⇒ u · x ∈ 2πZ

= (x1 , x2 , x3 ) ∈ [0, 2π)3 mx1 + nx2 + px3 ∈ 2πZ

the most significant term of F2 . Ultimate positivity of F2 entails
ultimate positivity of f as well, since P (sin(t), cos(t)) ≥ 0 everywhere, whereas an ultimately negative F2 makes f change sign
infinitely often.
Second, assume the dominant characteristic roots of F2 are
{±ic}, so that

f (t) = P (sin(t), cos(t)) + e−r2 t D cos(ct + ϕ3 ) + Ee−r3 t

for some r3 > 0 and ϕ3 ∈ R such that eiϕ3 ∈ A. Without loss
of generality, we can assume c 6∈ Q, since otherwise, we are done
by Theorem 8. But by Lemma 4, it will happen infinitely often that
P (sin(t), cos(t)) = 0 and D cos(ct + ϕ3 ) < −|D|/2, say. For
large enough such t, |Ee−(r2 +r3 )t | < |D|/4, so we conclude that
f is infinitely often negative, and hence has infinitely many zeros.
Third, assume the dominant characteristic roots of F2 (t) are
{0, ±ic}, so that

Notice that if mx1 + nx2 + px3 = 2kπ for some x1 , x2 , x3 , then
k ≤ |m| + |n|
S + |p|, so T partitions naturally into finitely many
subsets: T = N
k=1 Tk , where
def 
Tk = (x1 , x2 , x3 ) ∈ [0, 2π)3 mx1 + nx2 + px3 = 2kπ .

f (t) = P (sin(t), cos(t)) + e−r2 t (D cos(ct + ϕ3 ) + E).

We again assume c 6∈ Q, since otherwise the claim follows from
def
Theorem 8. Let M3 = E − |D| = mint≥0 F2 (t). If M3 > 0,
then f (t) clearly has no zeros. If M3 < 0, then there exists a
non-trivial interval I ⊆ [0, 2π) such that if ct + ϕ3 mod 2π ∈
I, then F2 (t) < 0. Since c 6∈ Q, Lemma 4 guarantees that
F2 (t) < 0 = P (sin(t), cos(t)) happens infinitely often, so f must
have infinitely many zeros. Finally, if M3 = 0, we argue that f
is ultimately positive. Indeed, since P (sin(t), cos(t)) and F2 (t)
are both non-negative everywhere, f (t) = 0 can only happen if
P (sin(t), cos(t)) = D cos(ct + ϕ3 ) + E = 0. This, however,
would entail eit ∈ A and eict ∈ A, which contradicts the GelfondSchneider Theorem, since c 6∈ Q. Thus, we conclude f has no
zeros.

def

Consider the trajectory h(t) = {(at, bt, ct) mod 2π | t ≥ 0}. Dedef
def
fine also the sets R = {h(2kπ) | k ∈ N} and H = {h(t) | t ≥
0}. Because of the linear dependence satisfied by a, b, c, it is easy
to see that R ⊆ H ⊆ T. By Kronecker’s Theorem, R is a dense
subset of T, so clearly H must be a dense subset of T as well.
Now define the function
def

F (x1 , x2 , x3 ) = A cos(x1 + ϕ1 ) + B cos(x2 + ϕ2 )
+ C cos(x3 + ϕ3 ) + D,
so that the image of f is exactly {F (x1 , x2 , x3 ) | (x1 , x2 , x3 ) ∈
H}. Let also the extrema of F over T be:
def

M1 = min F (x1 , x2 , x3 ),

4.3 Three dominant oscillations

T

Lemma 15. Let A, B, C, a, b, c be real algebraic numbers such
that a, b, c > 0 and A, B, C 6= 0. Let also ϕ1 , ϕ2 , ϕ3 ∈ R be such
that eiϕ1 , eiϕ2 , eiϕ3 ∈ A. Define the exponential polynomial f by

def

M2 = max F (x1 , x2 , x3 ).
T

f (t) = A cos(at + ϕ1 ) + B cos(bt + ϕ2 ) + C cos(ct + ϕ3 ) + D.

Both of these values are algebraic and can be computed using
quantifier elimination in the first-order language L of the real
numbers: just use separate variables for cos(xj ), sin(xj ) and apply the standard trigonometric identities to convert the linear dependence on x1 , x2 , x3 into a polynomial dependence between
cos(xj ), sin(xj ).
Now, by the density of H in T, if M1 < 0 < M2 , then f must
clearly be infinitely often positive and infinitely often negative, so
it must have infinitely many zeros. The case M1 < 0 = M2
is symmetric to 0 = M1 < M2 (just replace f and F by −f
and −F , respectively), so without loss generality, we can assume
0 = M1 < M2 . In this case, we argue that f has no zeros, that is,
even though F vanishes on some points in T, none of these points
appear in the dense subset H. Indeed, consider the set

It is decidable whether f has infinitely many zeros.
Proof. The argument consists of three cases, depending on the
linear dependencies over Q satisfied by a, b and c.
Case I. First, if a, b, c are linearly independent over Q, then the
claim follows directly from Theorem 7.
Case II. Second, suppose that a, b, c are all rational multiples of
one another:
k
n
b = a, c = a where n, m, k, l ∈ N+ .
m
l
We make the change of variable t → tml to obtain:
f (t) = A cos((at)ml + ϕ1 ) + B cos((at)nl + ϕ2 )
+ C cos((at)km + ϕ3 ) + D
= P (sin(at), cos(at)),

def

Z = {(cos(x1 ), sin(x1 ), . . . , cos(x3 ), sin(x3 )) |
(x1 , x2 , x3 ) ∈ T, F (x1 , x2 , x3 ) = 0} .

where P ∈ A[x, y] is a polynomial obtained using the standard
trigonometric identities. It is now clear that f is periodic, so it has
either no zeros or infinitely many zeros. Let
def

M1 =
def

M2 =

min

x2 +y 2 =1

Note that Z is clearly semi-algebraic, as one can directly write
a defining formula in L from F (x1 , x2 , x3 ) = 0 and mx1 +
nx2 + px3 ∈ 2πZ. Moreover, by the Zero-Dimensionality Lemma
(Ouaknine and Worrell 2014, Lemma 10), the function F (x1 , x2 , x3 )
achieves its minimum M1 = 0 at only finitely many points in Tk ,
for each k. Since T is the union of finitely many Tk , we immediately have that Z is finite. By the Tarski-Seidenberg Theorem,
projecting Z to any fixed component will also give a finite, semialgebraic subset of R, that is, a finite subset of A. Thus, we have
shown that if F (x1 , x2 , x3 ) = 0, then eixj ∈ A for all j = 1, 2, 3.

P (x, y) = min f (t),
t≥0

max P (x, y) = max f (t).

x2 +y 2 =1

t≥0

Using the same reasoning as in Lemma 14, we see that M1 , M2
are algebraic and effectively computable: simply construct defining

8

2018/3/15

Now if f (t) = 0 for some t ≥ 0, then we must have eati , ecti ∈ A,
which by the Gelfond-Schneider Theorem entails a/c ∈ Q, a contradiction.

On the other hand, we have the following chain of inequalities:
|a(t − tj )|2
2
> { |t − tj | > δj }

(aδj )2
2
= { definition of δj }
2(|C| + |D|)
tj−1
> { by t > tj−1 }
2(|C| + |D|)
t
≥ { triangle inequality and | cos(x)| ≤ 1 }
|C cos(at + ϕ2 ) + D|
|C| + |D|
+
.
t
t

4.4 One repeated oscillation
Lemma 16. Let A, B, C, D, a, r be real algebraic numbers such
that a, r > 0 and A 6= 0. Let also ϕ1 , ϕ2 ∈ R be such that
eiϕ1 , eiϕ2 ∈ A. Define the exponential polynomial f by
f (t) = t(A cos(at+ϕ1 )+B)+(C cos(at+ϕ2 )+D)+e−rt F (t)
where F is an exponential polynomial with purely imaginary dominant characteristic roots. Suppose also that f has order at most 8.
It is decidable whether f has infinitely many zeros.

Proof. Since f has order no greater than 8, it follows that F has
order at most 2. Therefore, F (t) must be of the form E cos(bt+ϕ3 )
for some E, b ∈ R ∩ A, b > 0, such that a/b 6∈ Q, and some ϕ3
such that eiϕ3 ∈ A, since otherwise the imaginary parts of the
characteristic roots of f are pairwise linearly dependent over Q, so
our claim is proven immediately by Theorem 8.
Consider first the magnitudes of A and B. If |A| > |B|, then
the term tA cos(at + ϕ1 ) makes f change sign infinitely often,
whereas if |B| > |A|, then for t large enough, the term tB makes f
ultimately positive or ultimately negative, depending on the sign of
B. Thus, we can assume |A| = |B|. Dividing f by B, and replacing
ϕ1 by ϕ1 +π if necessary, we can assume the function has the form:

Combining, we have
α(t) + β(t) ≥ α(t) − |β(t)|
= t(1 − cos(at + ϕ1 )) − |C cos(at + ϕ2 ) + D|
≥ |C| + |D|.
Thus, if t is large enough to ensure |γ(t)| < |C| + |D|, we have
f (t) > 0 outside critical regions.
For the second part of the argument, we consider t in critical
regions. Notice that the values of β(t) on [tj − δj , tj + δj ] are
independent of the choice of tj . Moreover, we have β(tj ) = M >
0, so there exists some ǫ > 0 such that for all t ∈ [tj −ǫ, tj +ǫ], we
have β(t) ≥ M/2, say. Now for any critical point tj chosen large
enough, we will have [tj − δj , tj + δj ] ⊆ [tj − ǫ, tj + ǫ], so β(t) >
M/2 on the entire critical region. Let also tj be large enough so
that for any t in the critical region, we have |γ(t)| < M/2. Then
we have f (t) = α(t)+β(t)+γ(t) ≥ β(t)−|γ(t)| > 0, completing
the claim.

f (t) = t(1 − cos(at + ϕ1 ))

+ (C cos(at + ϕ2 ) + D) + e−rt E cos(bt + ϕ3 ).

Considering the dominant term, it is clear that f is infinitely often
def
def
positive. Let α(t) = t(1 − cos(at + ϕ1 )), β(t) = C cos(at +
def −rt
ϕ2 ) + D and γ(t) = e E cos(bt + ϕ3 ).
We now focus on the sign of the term β(t) at the positive
def
critical times tj = −ϕ1 /a + 2jπ/a (j ∈ Z) when 1 − cos(at +
def
ϕ1 ) vanishes. Notice that β(tj ) = C cos(ϕ2 − ϕ1 ) + D =
M is independent of j. First, if M < 0, then for all tj large
enough, f (tj ) < 0, so the function must have infinitely many
zeros. Second, if M = 0, then by the linear independence of a, b
and Lemma 4, we have α(tj ) = β(tj ) = 0 > γ(tj ) for infinitely
many tj , so we can conclude f has infinitely many zeros.
Finally, suppose M > 0. We will prove that f is ultimately
positive. For each tj , define the critical region [tj − δj , tj + δj ],
given by
p
|C| + |D|
def 2
√
δj =
.
a tj−1

5. Hardness at Order 9
Diophantine approximation is a branch of number theory concerned with approximating real numbers by rationals. A central role
is played in this theory by the notion of continued fraction expansion, which allows to compute a sequence of rational approximations to a given real number that is optimal in a certain well-defined
sense. For our purposes it suffices to note that the behaviour of the
continued fraction expansion of a real number a is closely related to
the following two constants associated with a. The Lagrange constant (or homogeneous Diophantine approximation constant) of a
is defined by
o
n
c
n
< 2 for infinitely many m, n ∈ Z .
L∞ (a) = inf c : a −
m
m
By definition L∞ (a) is a non-negative real number.
A real number a is called badly approximable if L∞ (a) >
0. The badly approximable numbers are precisely those whose
continued fraction expansions have bounded partial quotients.
Khinchin showed in 1926 that almost all real numbers (in the
measure-theoretic sense) have Lagrange constant equal to zero.
However, information on the Lagrange constants of specific numbers or classes of numbers has proven to be elusive. In particular,
concerning algebraic numbers, Guy (Guy 2004) asks

From here onwards, we only consider t large enough for any two
adjacent critical regions to be disjoint. The argument consists of
two parts: first we show f (t) > 0 for all large enough t outside all
critical regions, and then we show f (t) > 0 for large enough t in a
critical region.
Suppose t is outside all critical regions and let j minimise
|t − tj |. Since the distance between critical points is 2π/a by
construction, we have a|t − tj | ≤ π. Therefore,

Is there an algebraic number of degree greater than two
whose simple continued fraction expansion has unbounded

|a(t − tj )|2
≤ 1 − cos(at − atj ) = 1 − cos(at + ϕ1 ).
2
9

2018/3/15

partial quotients? Does every such number have unbounded
partial quotients?

Grant (267989: QUAREM). Joël Ouaknine is supported by ERC
grant AVS-ISS (648701). James Worrell is supported by EPSRC
grant EP/N008197/1.

The above question can equivalently be formulated in terms of
whether any algebraic number of degree greater than two has stricly
positive Lagrange constant or whether all such numbers have Lagrange constant 0.
Recall that a real number a is computable if there is an algorithm
which, given any rational ε > 0 as input, returns a rational q such
that |q − x| < ε. We can now state the main result of the section.
In this section, we will show that a decision procedure for the
Infinite Zeros Problem would yield the computability of L∞ (a) for
all a ∈ R ∩ A.
Fix positive a ∈ R ∩ A, c ∈ Q and define the functions:

References
A. Baker. Transcendental number theory. Cambridge University Press,
Cambridge, 1975.
P. C. Bell, J.-C. Delvenne, R. M. Jungers, and V. D. Blondel. The Continuous Skolem-Pisot Problem. Theoretical Computer Science, 411(40-42):
3625–3634, 2010. ISSN 0304-3975.
J. Berstel and M. Mignotte. Deux propriétés décidables des suites
récurrentes linéaires. Bulletin de la Société Mathématique de France,
104:175–184, 1976.

def

f1 (t) = et (1 − cos(t)) + t(1 − cos(at)) − c sin(at),
def

H. Cohen. A Course in Computational Algebraic Number Theory. Springer,
1993.

t

f2 (t) = e (1 − cos(t)) + t(1 − cos(at)) + c sin(at),

A. O. Gelfond. On Hilbert’s seventh problem. In Dokl. Akad. Nauk. SSSR,
volume 2, pages 1–6, 1934.

def

f (t) = et (1 − cos(t)) + t(1 − cos(at)) − c| sin(at)|
= min{f1 (t), f2 (t)}.

A. O. Gelfond and I. Vinogradov. Sur le septieme probleme de Hilbert.
Bull. Acad. Sci. URSS, pages 623–634, 1934.

It is easy to see that f1 and f2 are exponential polynomials of order
9, with six characteristic roots: three simple (1 and 1 ± i) and three
repeated (0 and ±ai). Thus, the problem of determining whether
fj has infinitely many zeros is an instance of the Infinite Zeros
Problem. Moreover, it is easy to check that f has infinitely many
zeros if and only if at least one of f1 and f2 has infinitely many
zeros.
We will first state two lemmas which show a connection between the existence of infinitely many zeros of f and the Lagrange
constant of a. We defer the proofs to Appendix A.

R. Guy. Unsolved Problems in Number Theory. Springer, third edition,
2004.
I. Győri and G. Ladas.
Oscillation Theory of Delay Differential
Equations: with Applications.
Oxford mathematical monographs.
Oxford University Press, 1991.
ISBN 9780198535829.
URL
https://books.google.co.uk/books?id=6CnvAAAAMAAJ.
G. Hardy and E. Wright. An introduction to the theory of numbers. Oxford,
1:979, 1999.
A. Macintyre and A. J. Wilkie. On the decidability of the real exponential
field. 1996.

Lemma 17. Fix a ∈ R ∩ A and ε, c ∈ Q with a, c > 0
and ε ∈ (0, 1). If f (t) = 0 for infinitely many t ≥ 0, then
L∞ (a) ≤ c/2π 2 (1 − ε).

D. Marker. Model Theory: An Introduction. Graduate Texts in Mathematics.
Springer, 2002.
J. Ouaknine and J. Worrell. On the positivity problem for simple linear
recurrence sequences. In Automata, Languages, and Programming,
pages 318–329. Springer, 2014.

Lemma 18. Fix a ∈ R ∩ A and ε, c ∈ Q with a, c > 0 and
ε ∈ (0, 1). If L∞ (a) ≤ c(1 − ε)/2π 2 , then f (t) = 0 for infinitely
many t ≥ 0.

V. Pan. Optimal and nearly optimal algorithms for approximating polynomial zeros. Computers & Mathematics with Applications, 31(12):97 –
138, 1996.

We now use the above lemmas to derive an algorithm to compute L∞ (a) using an oracle for the Infinite Zeros Problem, establishing our central hardness result:

J. Renegar. On the computational complexity and geometry of the firstorder theory of the reals. part i: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of Symbolic Computation, 13(3):255 – 299,
1992. ISSN 0747-7171. doi: http://dx.doi.org/10.1016/S0747-7171(10)
80003-3.

Theorem 19. Fix a positive real algebraic number a. If the Infinite
Zeros Problem is decidable for instances of order 9, then L∞ (a)
may be computed to within arbitrary precision.
Proof. Suppose we know L∞ (a) ∈ [p, q] for non-negative p, q ∈
Q. Choose c ∈ Q with c > 0 and ε ∈ Q with ε ∈ (0, 1) such that
p<
def

T. Schneider. Transzendenzuntersuchungen periodischer Funktionen I.
Transzendenz von Potenzen. Journal für die reine und angewandte
Mathematik, 172:65–69, 1935a.

c
c(1 − ε)
<
< q.
2π 2
2π 2 (1 − ε)

T. Schneider. Transzendenzuntersuchungen periodischer Funktionen II.
Transzendenzeigenschaften elliptischer Funktionen. Journal für die
reine und angewandte Mathematik, 172:70–74, 1935b.

def

Write A = c(1 − ε)/2π 2 and B = c/2π 2 (1 − ε). Use the
oracle for the Infinite Zeros Problem to determine whether at least
one of f1 , f2 has infinitely many zeros. If this is the case, then f
also has infinitely many zeros, so by Lemma 17, L∞ (a) ≤ B and
we continue the approximation recursively on the interval [p, B].
If not, then L(a) ≥ A by Lemma 18, so we continue on the
interval [A, q]. Notice that in this procedure, one can choose c, ε at
each stage in such a way that the confidence interval shrinks by at
least a fixed factor, whatever the outcome of the oracle invocations.
It follows therefore that L∞ (a) can be approximated to within
arbitrary precision.

T. Tao. Structure and randomness: pages from year one of a mathematical
blog. American Mathematical Society, 2008.
A. Tarski. A decision method for elementary algebra and geometry. 1951.
A. J. Wilkie. Model completeness results for expansions of the ordered
field of real numbers by restricted Pfaffian functions and the exponential
function. Journal of the American Mathematical Society, pages 1051–
1094, 1996.

A. Proofs of Hardness Lemmas
Throughout this section, let

Acknowledgements Ventsislav Chonev is supported by Austrian
Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE),
ERC Start grant (279307: Graph Games), and ERC Advanced

def

f (t) = et (1 − cos(t)) + t(1 − cos(at)) − c| sin(at)|.
10

2018/3/15

Lemma 17. Fix a ∈ R ∩ A and ε, c ∈ Q with a, c > 0
and ε ∈ (0, 1). If f (t) = 0 for infinitely many t ≥ 0, then
L∞ (a) ≤ c/2π 2 (1 − ε).

and
if 1 − cos(x) ≤ c/eT and |x| ≤ π, then x2 /4 ≤ 1 − cos(x).
(8)
The following chain of inequalities holds:

Proof. Suppose f (t) = 0 for infinitely many t. Clearly, this also
entails f (t) = 0 for infinitely many t ≥ T , for any particular
threshold T ≥ 0. (Indeed, f (t) = min{f1 (t), f2 (t)} for exponential polynomials f1 and f2 given at the beginning of Section 5.
Thus, on any bounded interval, f has no more zeros than f1 and f2
combined, i.e., only finitely many, by the analiticity of f1 and f2 .)
We will show that T can be chosen in such a way that every zero
of f (t) on [T, ∞) yields a pair (n, m) ∈ N2 which satisfies the
inequality
c
n
.
<
a−
m
2π 2 m2 (1 − ε)
This is sufficient, since infinitely many zeros of f yield infinitely
many solutions, and therefore witness L∞ (a) ≤ c/2π 2 (1 − ε).
Thus, consider some t such that f (t) = 0 and t ≥ T for
some threshold T to be specified later. Let t = 2πm + δ1 and
at = 2πn + δ2 , where m, n ∈ N and δ1 , δ2 ∈ [−π, π). Then we
have
n
|δ2 − aδ1 |
a−
.
=
m
2πm
We will show that for T large enough, f (t) = 0 for t ≥ T allows
us to bound |δ2 | and |aδ1 | separately from above and then apply the
triangle inequality to bound |δ2 − aδ1 |.
First, choose ϕ1 , ϕ2 ∈ (0, 1) such that 1−ϕ2 > 1−ϕ1 > 1−ε.
Let T be large enough for the following property to hold:

1 − cos(δ1 )
= { by f (t) = 0 }
c| sin(δ2 )| − t(1 − cos(δ2 ))
et
≤ { by | sin(δ2 )|, | cos(δ2 )| ≤ 1}
c
et
≤ { by (7) }

2
c2 α2
2π
4π 2 a2 t + π
≤ { by |δ1 | ≤ π }
2

c2 α2
2π
4π 2 a2 t − δ1
= { t = 2πm + δ1 }
c2 α2
.
4π 2 a2 m2

Moreover, as 1 − cos(δ1 ) ≤ ce−t ≤ ce−T , by (8), we have

δ12
,
4
so combining the lower and upper bound on 1 − cos(δ1 ), we can
conclude
cα
.
|aδ1 | ≤
πm
Finally, by the triangle inequality and the bounds on |aδ1 | and
|δ2 |, we have
1 − cos(δ1 ) ≥

1 − ϕ2
t+π
for all t ≥ T .
≤
t − 2π
1 − ϕ1

In particular, since m = (t − δ1 )/2π and |δ1 | ≤ π, we have
2m
t+π
1 − ϕ2
.
≤
≤
2m − 1
t − 2π
1 − ϕ1

(5)

Let also T be large enough to make the following property valid:

a−

(1 − ϕ2 )x2
c|x|
∧ |x| ≤ π ⇒
≤ 1 − cos(x). (6)
T
2
Now we have the following chain of inequalities:
1 − cos(x) ≤

Now, by the premise of the Lemma, there are infinitely many t ≥ T
such that f (t) = 0, each yielding a pair (n, m) ∈ N2 which
satisfies the above inequality. These infinitely many pairs (n, m)
witness L∞ (a) ≤ c/2π 2 (1 − ε), as required.

1 − cos(δ2 )

≤ { f (t) = 0, noting et (1 − cos(t)) ≥ 0 }
c| sin(δ2 )|
t
≤ { by | sin(x)| ≤ |x| }
c|δ2 |
.
t

Lemma 18. Fix a ∈ R ∩ A and ε, c ∈ Q with a, c > 0 and
ε ∈ (0, 1). If L∞ (a) ≤ c(1 − ε)/2π 2 , then f (t) = 0 for infinitely
many t.
Proof. We will show that there exists an effective threshold M ,
dependent on a, c, ε, such that if

Then by (6), we have

c(1 − ε)
n
(9)
≤
m
2π 2 m2
for natural numbers n, m with m ≥ M , then f (2πm) ≤ 0. Note
that this is sufficient to prove the Lemma: the premise guarantees
infinitely many solutions (n, m) ∈ N2 of (9), so there must be
infinitely many solutions with m ≥ M , each yielding f (2πm) ≤
0. Since f is continuous and moreover is positive for arbitrarily
large times, it must have infinitely many zeros on [2πM, ∞).
Now let M be large enough, so that c(1 − ε)/πM < π and
a−

(1 − ϕ2 )δ22
.
1 − cos(δ2 ) ≥
2
Thus, combining the upper and lower bounds on 1 − cos(δ2 ) and
using (5) on the last step, we have
|δ2 | ≤

|δ2 | + |aδ1 |
|δ2 − aδ1 |
n
≤
=
m
2πm 
2πm
c
1
c
=
α+
.
≤
2π 2 m2
1 − ϕ1
2π 2 m2 (1 − ε)

2c
2c
c
≤
≤
.
t(1 − ϕ2 )
(2m − 1)π(1 − ϕ2 )
mπ(1 − ϕ1 )
def

Second, let α = (1−ε)−1 −(1−ϕ1 )−1 > 0. Let the threshold
T be large enough so that

2
2π
cα2
−t
for t ≥ T
(7)
e ≤
4π 2 a2 t + π

if |x| < c(1 − ε)/πM , then (1 − ε)|x| ≤ | sin(x)|.

(10)

Suppose that (9) holds for n, m ∈ N with m ≥ M and write
def
t = 2πm. We will show that f (t) ≤ 0. By (9), we have |am −
11

2018/3/15

n| ≤ c(1 − ε)/2π 2 m. Therefore, at = 2πam = 2πn + δ where
|δ| ≤ c(1 − ε)/πm < π. We have
f (t)
= { as cos(t) = 1 }
t(1 − cos(δ)) − c| sin(δ)|

≤ { by (10) and 1 − cos(x) ≤ x2 /2 }

πmδ 2 − c(1 − ε)|δ|
≤ { by |δ| ≤ c(1 − ε)/πm }
0.

12

2018/3/15

