A Universal Ordinary Differential Equation∗
Olivier Bournez†1 and Amaury Pouly2
1
2

Ecole Polytechnique, LIX, 91128 Palaiseau Cedex, France
bournez@lix.polytechnique.fr
MPI-SWS, Saarbrucken, Germany
pamaury@mpi-sws.org

arXiv:1702.08328v2 [math.CA] 29 Apr 2017

Abstract
An astonishing fact was established by Lee A. Rubel (1981): there exists a fixed non-trivial fourthorder polynomial differential algebraic equation (DAE) such that for any positive continuous
function ϕ on the reals, and for any positive continuous function (t), it has a C ∞ solution with
|y(t) − ϕ(t)| < (t) for all t. Lee A. Rubel provided an explicit example of such a polynomial
DAE. Other examples of universal DAE have later been proposed by other authors.
However, while these results may seem very surprising, their proofs are quite simple and are
frustrating for a computability theorist, or for people interested in modeling systems in experimental sciences. First, the involved notions of universality is far from usual notions of universality
in computability theory because the proofs heavily rely on the fact that constructed DAE does
not have unique solutions for a given initial data. Indeed, in general a DAE may not have a
unique solution, given some initials conditions. But Rubel’s DAE never has a unique solution,
even with a countable number of conditions of the form y (ki ) (ai ) = bi . This is very different from
usual notions of universality where one would expect that there is clear unambiguous notion of
evolution for a given initial data, for example as in computability theory. Second, the proofs usually rely on solutions that are piecewise defined. Hence they cannot be analytic, while analycity
is often a key expected property in experimental sciences. Third, the proofs of these results can
be interpreted more as the fact that (fourth-order) polynomial algebraic differential equations is
a too loose a model compared to classical ordinary differential equations. In particular, one may
challenge whether the result is really a universality result.
The question whether one can require the solution that approximates ϕ to be the unique
solution for a given initial data is a well known open problem [Rubel 1981, page 2], [Boshernitzan
1986, Conjecture 6.2]. In this article, we solve it and show that Rubel’s statement holds for
polynomial ordinary differential equations (ODEs), and since polynomial ODEs have a unique
solution given an initial data, this positively answers Rubel’s open problem. More precisely, we
show that there exists a fixed polynomial ODE such that for any ϕ and (t) there exists some
initial condition that yields a solution that is -close to ϕ at all times.
The proof uses ordinary differential equation programming. We believe it sheds some light
on computability theory for continuous-time models of computations. It also demonstrates that
ordinary differential equations are indeed universal in the sense of Rubel and hence suffer from
the same problem as DAEs for modelization: a single equation is capable of modelling any
phenomenon with arbitrary precision, meaning that trying to fit a model based on polynomial
DAEs or ODEs is too general (if it has a sufficient dimension).
1998 ACM Subject Classification G.1.7 Ordinary Differential Equations F.1.1 Models of Computation. F.1.3 Complexity Measures and Classes.
Keywords and phrases Ordinary Differential Equations, Universal Differential Equations, Ana-

∗
†

Full version at https://arxiv.org/abs/1702.08328.
Olivier Bournez was partially supported by ANR PROJECT RACAF

licensed under Creative Commons License CC-BY
42nd Conference on Very Important Topics (CVIT 2016).
Editors: John Q. Open and Joan R. Acces; Article No. 23; pp. 23:1–23:35
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

23:2

A Universal Ordinary Differential Equation

t
t
Figure 1 On left, graphical representation of function g. On right, two S-modules glued together.

log Models of Computation, Continuous-Time Models of Computation, Computability, Computational Analysis, Computational Complexity
Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23

1

Introduction

A very astonishing result was established by Lee A. Rubel in 1981 [19]. There exists a
universal fourth-order algebraic differential equation in the following sense.
I Theorem 1 ([19]). There exists a non-trivial fourth-order implicit differential algebraic
equation
P (y 0 , y 00 , y 000 , y 0000 ) = 0

(1)

where P is a polynomial in four variables with integer coefficients, such that for any continuous
function ϕ on (−∞, ∞) and for any positive continuous function (t) on (−∞, ∞), there
exists a C ∞ solution y such that
|y(t) − ϕ(t)| < (t)
for all t ∈ (−∞, ∞).
Even more surprising is the fact that Rubel provided an explicit example of such a
polynomial P that is particularly simple:
4

00

3y 0 y y 0000

2

4

2

0000

3

2

2

4

−4y 0 y 000 y + 6y 0 y 00 y 000 y 0000 + 24y 0 y 00 y 0000
3
3
2
3
2
7
−12y 0 y 00 y 000 − 29y 0 y 00 y 000 + 12y 00

=0

(2)

While this result looks very surprising at first sight, Rubel’s proofs turns out to use basic
arguments, and can be explained as follows. It uses the following classical trick to build C ∞
2
piecewise functions: let g(t) = e−1/(1−t ) for −1 < t < 1, and g(t) = 0 otherwise. It is not
hard to see that function g is C ∞ and Figure 1 shows that g looks like
R t a “bump”. Since it
g 0 (t)
2t
0
2 2
satisfies g(t) = − (1−t2 )2 , then g (t)(1 − t ) + g(t)2t = 0 and f (t) = 0 g(u)du satisfies the
polynomial differential algebraic equation f 00 (1 − t2 )2 + f 0 (t)2t = 0. Since this equation is
homogeneous, it also holds for af + b for any a and b. The idea is then to obtain a fourth
order DAE that is satisfied by every function y(t) = γf (αt + β) + δ, for all α, β, γ, δ. After
some computations, Rubel obtained the universal differential equation (2).
Functions of the type y(t) = γf (αt + β) + δ generate what Rubel calls S-modules: a
function that values A at a, B at b, is constant on [a, a + δ], monotone on [a + δ, b − δ],

O. Bournez and A. Pouly

23:3

constant on [b − δ, b], by an appropriate choice of α, β, γ, δ. Summing S-modules corresponds
to gluing then together, as is depicted in Figure 1. Note that finite, as well as infinite sums1
of S-modules still satisfy the equation (2) and thus any piecewise affine function (and hence
any continuous function) can be approximated by an appropriate sum of S-modules. This
concludes Rubel’s proof of universality.
As one can see, the proof turns out to be frustrating because the equation essentially
allows any behavior. This may be interpreted as merely stating that differential algebraic
equations is simply too lose a model. Clearly, a key point is that this differential equation
does not have a unique solution for any given initial condition: this is the core principle used
to glue a finite or infinite number of S-modules and to approximate any continuous function.
Rubel was aware of this issue and left open the following question in [19, page 2].
“It is open whether we can require in our theorem that the solution that approximates
ϕ to be the unique solution for its initial data.”
Similarly, the following is conjectured in [4, Conjecture 6.2].
“Conjecture. There exists a non-trivial differential algebraic equation such that any
real continuous function on R can be uniformly approximated on all of R by its
real-analytic solutions”
The purpose of this paper is to provide a positive answer to both questions. We prove
that a fixed polynomial ordinary differential equations (ODE) is universal in above Rubel’s
sense. At a high level, our proofs are based on ordinary differential equation programming.
This programming is inspired by constructions from our previous paper [7]. Here, we mostly
use this programming technology to achieve a very different goal and to provide positive
answers to these above open problems.
We also believe they open some lights on computability theory for continuous-time models
of computations. In particular, it follows that concepts similar to Kolmogorov complexity
can probably be expressed naturally by measuring the complexity of the initial data of a
(universal-) polynomial ordinary differential equations for a given function. We leave this
direction for future work.

Related work and discussions
First, let us mention that Rubel’s universal differential equation has been extended in several
papers. In particular, Duffin proved in [12] that implicit universal differential equations with
0000
000 00
00 3
2
simpler expressions exists, such as n2 y y 0 + 3n(1 − n)y y y 0 + (2n2 − 3n + 1)y = 0 for
any n > 3. The idea of [12] is basically to replace the C ∞ function g of [19] by some piecewise
polynomial of fixed degree, that is to say by splines. Duffin also proves that considering
trigonometric polynomials for function g(x) leads to the universal differential equation
0000
000 00
2
3
ny y 0 + (2 − 3n)y y y 0 + 2(n − 1)y 00 = 0. This is done at the price of approximating
function ϕ respectively by splines or trigonometric splines solutions which are C n (and n
can be taken arbitrary big) but not C ∞ as in [19]. Article [8] proposes another universal
differential equation whose construction is based on Jacobian elliptic functions. Notice that
[8] is also correcting some statements of [12].

1

With some convergence or disjoint domain conditions.

CVIT 2016

23:4

A Universal Ordinary Differential Equation

All the results mentioned so far are concerned with approximations of continuous functions
over the whole real line. Approximating functions over a compact domain seems to be a
different (and somewhat easier for our concerns) problem, since basically by compactness,
one just needs to approximate the function locally on a finite number of intervals. A 1986
reference survey discussing both approximation over the real line and over compacts is [4].
Recently, over compact domains, the existence of universal ordinary differential equation
C ∞ of order 3 has been established in [11]: it is shown that for any a < b, there exists a
third order C ∞ differential equation y 000 = F (y, y 0 , y 00 ) whose solutions are dense in C 0 ([a, b]).
Notice that this is not obtained by explicitly stating such an order 3 universal ordinary
differential, and that this is a weaker notion of universality as solutions are only assumed to
be arbitrary close over a compact domain and not all the real line. Order 3 is argued to be a
lower bound for Lipschitzian universal ODEs [11].
Rubel’s result has sometimes been considered to be related to be the equivalent, for
analog computers, of the universal Turing machines. This includes Rubel’s paper motivation
given in [19, page 1]. We now discuss and challenge this statement.
Indeed, differential algebraic equations are known to be related to the General Purpose
Analog Computer (GPAC) of Claude Shannon [20], proposed as a model of the Differential
Analysers [9], a mechanical programmable machine, on which he worked as an operator.
Notice that the original relations stated by Shannon in [20] between differential algebraic
equations and GPACs have some flaws, that have been corrected later by [18] and [15]. Using
the better defined model of GPAC of [15], it can be shown that functions generated by GPAC
exactly correspond to polynomial ordinary differential equations. Some recent results have
established that this model, and hence polynomial ordinary differential equations can be
related to classical computability [5] and complexity theory [7].
However, we do not really follow the statement that Rubel’s result is the equivalent,
for analog computers, of the universal Turing machines. In particular, Rubel’s notion of
universality is completely different from the ones in computability theory. For a given initial
data, a (deterministic) Turing machine has only one possible evolution. On the other hand,
Rubel’s equation does not dictate any evolution but rather some conditions that any evolution
has to satisfy. In other words, Rubel’s equation can be interpreted as the equivalent of an
invariant of the dynamics of (Turing) machines, rather than a universal machine in the sense
of classical computability.
Notice that while several results have established that (polynomial) ODEs are able to
simulate the evolution of Turing machines (see e.g. [5, 14, 7]), the existence of a universal
ordinary differential equation does not follow from them. To understand the difference, let us
restate the main result of [14], of which [7] is a more advanced version for polynomial-time
computable functions.
I Theorem 2. A function f : [a, b] → R is computable (in the framework of Computable
Analysis) if and only if there exists some polynomials p : Rn+1 → Rn , p0 : R → R with
computable coefficients and α1 , . . . , αn−1 computable reals such that for all x ∈ [a, b], the
solution y : [a, b] → Rn to the Cauchy problem
y(0) = (α1 , . . . , αn−1 , p0 (x)),

y 0 = p(y)

satisfies that for all t > 0 that
|f (x) − y1 (t)| 6 y2 (t)

and

lim y2 (t) = 0.

t→∞

Since there exists a universal Turing machine, there exists a “universal” polynomial ODE
for computable functions. But there are major differences between Theorem 2 and the result

O. Bournez and A. Pouly

23:5

of this paper (Theorem 3). Even if we have a strong link between the Turing machines’s
configuration and the evolution of the differential equation, this is not enough to guarantee
what the trajectory of the system will be at all times. Indeed, Theorem 2 only guarantees
that y1 (t) → f (x) asymptotically. On the other hand, Theorem 3 guarantees the value of
y1 (t) at all times. Notice that our universality result also applies to functions that are not
computable (in which case the initial condition is computable from the function but still not
computable).
We would like to mention some implications for experimental sciences that are related to
the classical use of ODEs in such contexts. Of course, we know that this part is less formal
from a mathematical point of view, but we believe this discussion has some importance:
A key property in experimental sciences, in particular physics is analyticity. Recall that a
function is analytic if its is equal to its Taylor expansion in any point. It has sometimes been
observed that “natural” functions coming from Nature are analytic, even if this cannot be a
formal statement, but more an observation. We obtain a fixed universal polynomial ODEs,
so in particular all its solution must be analytic2 , and it follows that universality holds even
with analytic functions. All previous constructions mostly worked by gluing together C ∞ or
C n functions, and as it is well known “gluing” of analytic functions is impossible. We believe
this is an important difference with previous works.
As we said, Rubel’s proof can be seen as an indication that (fourth-order) polynomial
implicit DAE is too loose model compared to classical ODEs, allowing in particular to glue
solutions together to get new solutions. As observed in many articles citing Rubel’s paper,
this class appears so general that from an experimental point of view, it makes littles sense to
try to fit a differential model because a single equation can model everything with arbitrary
precision. Our result implies the same for polynomial ODEs since, for the same reason, a
single equation of sufficient dimension can model everything.
Notice that our constructions have at the end some similarities with Voronin’s theorem.
This theorem states that Riemann’s ζ function is such that for any analytic function f (z)
that is non-vanishing on a domain U homeomorphic to a closed disk, and any  > 0, one
can find some real value t such that for all z ∈ U , |ζ(z + it) − f (z)| < . Notice that ζ
function is a well-known function known not to be solution of any polynomial DAE (and
consequently polynomial ODE), and hence there is no clear connexion to our constructions
based on ODEs. We invite to read the post [17] in “Gödel’s Lost Letter and P=NP” blog for
discussions about potential implications of this surprising result to computability theory.

Formal statements
I Theorem 3 (Universal PIVP). There exists a fixed polynomial vector p in d variables
such that for any functions f ∈ C 0 (R) and ε ∈ C 0 (R, R>0 ), there exists α ∈ Rd such that
there exists a unique solution y : R → Rd to y(0) = α, y 0 = p(y). Furthermore, this solution
satisfies that |y1 (t) − f (t)| 6 ε(t) for all t ∈ R, and it is analytic.
It is well-known that polynomial ODEs can be transformed into DAEs that have the
same analytic solutions, see [10] for example. The following then follows for DAEs.
I Theorem 4 (Universal DAE). There exists a fixed polynomial p in d + 1 variables such that
for any functions f ∈ C 0 (R) and ε ∈ C 0 (R, R>0 ), there exists α0 , . . . , αd−1 ∈ R such that

2

Which is not the case for polynomial DAEs.

CVIT 2016

23:6

A Universal Ordinary Differential Equation

there exists a unique analytic solution y : R → R to y(0) = α0 , y 0 (0) = α1 , . . . , y (d−1) (0) =
αd−1 , p(y, y 0 , . . . , y d ) = 0. Furthermore, this solution satisfies that |y(t) − f (t)| 6 ε(t) for all
t ∈ R.
I Remark. Notice that both theorems apply even when f is not computable. In this case, the
initial condition(s) α exist but are not computable. We believe that α is always computable
from f and ε, that is the mapping (f, ε) 7→ α is computable in the framework of Computable
Analysis, with an adequate representation of f, ε and α.
I Remark. Notice that we do not provide explicitly in this paper the considered polynomial
ODE, nor its dimension d. But it can be derived by following the constructions. We currently
estimate d to be more than three hundred following the precise constructions of this paper
(but also to be very far from the optimal). We did not try to minimize d in the current
paper, as we think our results are sufficiently hard to be followed in this paper for not beeing
complicated by considerations about optimizations of dimensions.
I Remark. Both theorems are stated for total functions f and ε over R. It trivially applies
to any continuous partial function that can be extended to a continuous function over R. In
particular, it applies to any functions over [a, b]. It is not hard to see that it also applies to
functions over (a, b) by rescaling R into (a, b) using the cotangent:



π
t−a
π
satisfies z 0 (t) = φ0 (t)p(z(t)), φ0 (t) = b−a
(1 + φ(t)2 ).
z(t) = y − cot b−a
More complex domains such as [a, b) and (a, b] (with a possibly infinite) can also be obtain
in a similar fashion.

2

Overview of the proof

A first a priori difficulty is that if one considers a fixed polynomial ODE y 0 = p(y), one could
think that the growth of its solutions is constrained by p and thus cannot be arbitrary. This
would then prevent us from building a universal ODE simply because it could not grow fast
enough. This fact is related to Emil Borel’s conjecture in [3] (see also [16]) that a solution,
defined over R, to a system with n variables has growth bounded by roughly en (x), the n−th
iterate of exp. The conjecture is proved for n = 1 [3], but has been proven to be false for
n = 2 in [21] and [2]. Bank [1] then adapted the previous counter-examples to provide a DAE
whose non-unique increasing real-analytic solutions at infinity do not have any majorant. See
the discussions (and Conjecture 6.1) in [4] for discussions about the growth of solutions of
DAEs, and their relations to functions en (x).
Thus, the first important part of this paper is to refine Bank’s counter-example to build
fastgen, a fast-growing function that satisfies even stronger properties. The second major
ingredient is to be able to approximate a function with arbitrary precision everywhere.
Since this is a difficult task, we use fastgen to our advantage to show that it is enough to
approximate functions that are bounded and change slowly (think 1-Lipschitz, although the
exact condition is more involved). That is to say, to deal with the case where there is no
problem about the growth and rate of change of functions in some way. This is the purpose
of the function pwcgen which can build arbitrary almost piecewise constant functions as long
as they are bounded and change slowly.
It should be noted that the entire paper, we construct generable functions (in several
variables) (see Section 3.1). For most of the constructions, we only use basic facts like the
fact that generable functions are stable under arithmetic, composition and ODE solving. We
know that generable functions satisfy polynomial partial equations and use this fact only at

O. Bournez and A. Pouly

23:7

the very end to show that the generable approximation that we have built, in fact, translates
to a polynomial ordinary differential equation.
The rest of the paper is organized as follows. In Section 3, we recall some concepts and
results from other articles. The main purpose of this section is to present Theorem 10. This
theorem is the analog equivalent of doing an assignment in a periodic manner. Section 4
is devoted to fastgen, the fast-growing function. In Section 5, we show how to generate a
sequence of dyadic rationals. In Section 6, we show how to generate a sequence of bits. In
Section 7, we show how to leverage the two previous sections to generate arbitrary almost
piecewise constant functions. Section 8 is then devoted to the proof of our main theorem.

3
3.1

Concepts and results from other articles
Generable functions

The following concept can be attributed to [20]: a function f : R → R is said to be a PIVP
(Polynomial Initial Value Problem) function if there exists a system of the form y 0 = p(y),
where p is a (vector of) polynomial, with f (t) = y1 (t) for all t, where y1 denotes first
component of the vector y defined in Rd . We need in our proof to extend this concept to
talk about multivariable functions. In [6], we introduced the following class, which can be
seen as extensions of [13].
I Definition 5 (Generable function). Let d, e ∈ N, I be an open and connected subset of
Rd and f : I → Re . We say that f is generable if and only if there exists an integer n > e,
a n × d matrix p consisting of polynomials with coefficients in R, x0 ∈ Rd , y0 ∈ Rn and
y : I → Rn satisfying for all x ∈ I:
y(x0 ) = y0 and Jy (x) = p(y(x))
I y satisfies a polynomial differential equation3 ,
f (x) = (y1 (x), . . . , ye (x))
I the components of f are components of y.
This class strictly generalizes functions generated by polynomial ODEs. Indeed, in the
special case of d = 1 (the domain of the function has dimension 1), the above definition is
equivalent to saying that y 0 = p(y) for some polynomial p. The interested reader can read
more about this in [6].
For the purpose of this paper, the reader only needs to know that the class of generable
functions enjoys many stability properties that make it easy to create new functions from
basic operations. Informally, one can add, subtract, multiply, divide and compose them at
will, the only requirement is that the domain of definition must always be connected. In
particular, the class of generable functions contains some common mathematical functions:
(multivariate) polynomials,
trigonometric functions: sin, cos, tan, etc,
exponential and logarithm: exp, ln,
hyperbolic trigonometric functions: sinh, cosh, tanh.
Two famous examples of functions that are not in this class are the ζ and Γ, we refer the
reader to [6] and [13] for more information.
A nontrivial fact is that generable functions are always analytic. This property is wellknown in the one-dimensional case but is less obvious in higher dimensions, see [6] for more
details. Moreover, generable functions satisfy the following crucial properties.

3

Jy denotes the Jacobian matrix of y.

CVIT 2016

23:8

A Universal Ordinary Differential Equation

I Lemma 6 (Closure properties of generable functions). Let f :⊆ Rd → Rn and g :⊆ Re → Rm
be generable functions. Then f + g, f − g, f g, fg and f ◦ g are generable4 .
I Lemma 7 (Generable functions are closed under ODE). Let d ∈ N, J ⊆ R an interval,
f :⊆ Rd → Rd generable, t0 ∈ J and y0 ∈ dom f . Assume there exists y : J → dom f
satisfying
y(t0 ) = y0

y 0 (t) = f (y(t))

for all t ∈ J, then y is generable (and unique).
In fact, generable functions satisfy the stronger (albeit more obscure) theorem
I Theorem 8 (Generable functions are closed under ODE). Let d, n ∈ N, Ω ⊆ Rd , t0 ∈ R,
(Jα )α∈Ω a family of open intervals containing t0 and G : Ω → Rn , F :⊆ Rd → Rd generable.
Assume that X = {(α, t) : α ∈ Ω, t ∈ Jα } is an open connected set and that there exists
f : X → dom F satisfying
f (α, t0 ) = G(α)

∂f
∂t (α, t)

= F (f (α, t))

for all α ∈ Ω and t ∈ Jα . Then f is generable (and unique).

3.2

Helper functions and constructions

We mentioned earlier that a number of common mathematical functions are generable.
However, for our purpose, we will need less common functions that one can consider to be
programming gadgets. One such operation is rounding (computing the nearest integer). Note
that, by construction, generable functions are analytic and in particular must be continuous.
It is thus clear that we cannot build a perfect rounding function and in particular we have to
compromise on two aspects:
we cannot round numbers arbitrarily close to n + 12 for n ∈ Z: thus the function takes a
parameter λ to control the size of the “zone” around n + 12 where the function does not
round properly,
we cannot round without error: thus the function takes a parameters µ that controls how
good the approximation must be.
I Lemma 9 (Round, [6]). There exists a generable function round such that for any n ∈ Z,
x ∈ R, λ >
 2 and µ > 0:

if x ∈ n − 12 , n + 12 then | round(x,
µ, λ) − n| 6 21 ,

1
1
1
1
if x ∈ n − 2 + λ , n + 2 − λ then | round(x, µ, λ) − n| 6 e−µ .
The other very useful operation is the analog equivalent of a discrete assignment, done in
a periodic manner. More precisely, we consider a particular class of ODEs
y 0 (t) = pereach(t, φ(t), y(t), g(t))
adapted from the constructions of [7].
This equation alternates between two behaviors, for all n ∈ N.
During Jn = [n, n + 12 ], it performs y(t) → g where mint∈Jn g(t) 6 g 6 maxt∈Jn g(t).
So in particular, if g(t) is almost constant over this time interval, then it is essentially
y(t) → g. Then φ controls how good the convergence is: the error is of the order of e−φ .

4

With the obvious dimensional condition associated with each operation.

O. Bournez and A. Pouly

23:9

During Jn0 = [n + 12 , n + 1], the systems tries to keep y constant, ie y 0 ≈ 0. More precisely,
the system enforces that |y 0 (t)| 6 e−φ(t) .
I Theorem 10 (Periodic reach). There exists a generable function pereach : R2>0 × R2 → R
such that for any I = [n, n + 1] with n ∈ N, y0 ∈ R, φ, ψ ∈ C 0 (I, R>0 ) and g ∈ C 0 (I, R), the
unique solution to
y 0 (t) = ψ(t) pereach(t, φ(t), y(t), g(t))

y(n) = y0 ,

exists over I.
If there exists ḡ ∈ 
R and η ∈ R>0 such
− ḡ| 6 η for all t ∈ [n, n + 12 ], then
 that |g(t)
Rt
Rt
|y(t) − ḡ| 6 η + exp − n ψ(u)φ(u)du whenever n ψ(u)φ(u)du > 1 for all t ∈ [n, n + 12 ],
and |y(t) − ḡ| 6 max(η, |y(n) − ḡ|) for all t ∈ [n, n + 12 ] without condition.
Rt
For all t ∈ [n + 12 , n], |y(t) − y(n + 12 )| 6 n+ 1 ψ(u) exp (−φ(u)) du.
2
 R

t
In particular, the first item implies that y(t) > minu∈[n,t] g(t) − exp − n φ(u)du whenever

Rt
φ(u)du > 1 for all t ∈ [n, n + 21 ], and y(t) > min y(n), minu∈[n,t] g(t) .
n

4

Generating fast growing functions

Our construction crucially relies on our ability to build functions of arbitrary growth. At
the end of this section, we obtain a function fastgen with a straightforward specification:
for any infinite sequence a0 , a1 , . . . of positive numbers, we can find a suitable α ∈ R such
that fastgen(α, n) > an for all n ∈ N. Furthermore, we can ensure that fastgen(α, ·) is
increasing. Notice, and this is the key point, that the definition of fastgen is independent of
the sequence a: a single generable function (and thus differential system) can have arbitrary
growth by simply tweaking its initial value.
Our construction builds on the following lemma proved by [1], based on an example
1
of [2]. The proof essentially relies on the function 2−cos(x)−cos(αx)
which is generable and
well-defined for all positive x if α is irrational. By carefully chosing α, we can make cos(x)
and cos(αx) simultaneously arbitrary close to 1.
I Lemma 11 ([1]). There exists a positive nondecreasing generable function g and an absolute
constant c > 0 such that for any increasing sequence a ∈ NN with an > 2 for all n, there exists
α ∈ R such that g(α, ·) is defined over [1, ∞) and for any n ∈ N and t > 2πbn , g(α, t) > can
Qn−1
where bn = k=0 ak .
Essentially, this lemma proves that there exists a function g such that for any n ∈ N,
g(α, a0 a1 · · · an−1 ) > an . Note that this is not quite what we are aiming for: the function g is
indeed > an but at times a0 a1 · · · an−1 instead of n. Since a0 a1 · · · an−1 is a very big number,
we need to “accelerate” g so that it reaches this values faster. This is a chicken-and-egg
problem because to accelerate g, we need to build a fast growing function. We now try to
explain how to solve this problem. Consider the following sequence:
x0 = a 0 ,

xn+1 = xn g(xn ).

Then observe that
x1 = x0 g(x0 ) = a0 g(a0 ) > a0 a1 ,

x2 = x1 g(x1 ) > a0 a1 g(a0 a1 ) > a0 a1 a2 ,

...

It is not hard to see that xn > a0 a1 · · · an > an . We then use our generable gadget of
Section 3.2 to simulate this discrete sequence with a differential equation. Intuitively, we

CVIT 2016

23:10

A Universal Ordinary Differential Equation

build a differential equation such that the solution y satisfies y(n) ≈ xn . More precisely,
we use two variables y and z such that over [n, n + 1/2], z 0 ≈ 0 and y(t) → zg(z) and over
[n+1/2, n+1], y 0 ≈ 0 and z(t) → y. Then if y(n) ≈ z(n) ≈ xn then y(n+1) ≈ z(n+1) ≈ xn+1 .
I Theorem 12. There exists Γ ⊆ R and a positive generable function fastgen : Γ × R>0 → R
such that for any x ∈ RN
>0 , there exists α ∈ Γ such that for any n ∈ N and t ∈ R>0 ,
fastgen(α, t) > xn

if t > n.

Furthermore, fastgen(α, ·) is nondecreasing.

5

Generating a sequence of dyadic rationals

A major part of the proof requires to build a function to approximate arbitrary numbers
over intervals [n, n + 1]. Ideally we would like to build a function that gives x0 over [0, 1], x1
over [1, 2], etc. Before we get there, we solve a somewhat simpler problem by making a few
assumptions:
we only try to approximate dyadic numbers, i.e. numbers of the form m2−p , and
furthermore we only approximate with error 2−p−3 ,
if a dyadic number has size p, meaning that it can be written as m2−p but not m0 2−p+1
then it will take a time interval of p units to approximate: [k, k + p] instead of [k, k + 1],
the function will only approximate the dyadics over intervals [k, k + 12 ] and not [k, k + 1].
This processus is illustrated in Figure 2: given a sequence d0 , d1 , . . . of dyadics, there is
a corresponding sequence a0 , a1 , . . . of times such that the function approximate dk over
[ak , ak + 12 ] within error 2−pk where pk is the size of dk . The theorem contains an explicit
formula for ak that depends on some absolute constant δ.

d0

d1

d2
d3

a0

a1

a2

a3

t

Figure 2 Graph of dygen for d0 = 2−1 , d1 = 2−3 + 2−1 , d2 = 2−5 + 2−2 and d3 = 2−4 (other
values ignored) assuming that δ = 9. We get that a0 = 0, a1 = 10, a2 = 22, a3 = 36.

S
Let Dp = {m2−p : m ∈ {0, 1, . . . , 2p − 1}} and D = n∈N Dp denote the set of dyadic
rationals in [0, 1). For any q ∈ D, we define its size by L(q) = min {p ∈ N : q ∈ Dp }.
I Theorem 13. There exists δ ∈ N>0 , Γ ⊆ R2 and a generable function dygen : Γ×R>0 → R
such that for any dyadic sequence q ∈ DN , there exists (α, β) ∈ Γ such that for any n ∈ N,
| dygen(α, β, t) − qn | 6 2−L(qn )−3
where an =

Pn−1

k=0 (L(qk )

for any t ∈ [an , an + 21 ]

+ δ). Furthermore, | dygen(α, β, t)| 6 1 for all α, β and t.

O. Bournez and A. Pouly

6

23:11

Generating a sequences of bits

We saw in the previous section how to generate a dyadic generator. Unfortunately, we saw
that it generates dyadic dn at times an , whereas we would like to get dn at time n for our
approximation. Our approach is to build a signal generator that will be high exactly at times
an . Each the signal will be high, the system will copy the value of the dyadic generator to a
variable and wait until the next signal. Since the signal is binary, we only need to generate a
sequence of bits. Note that this theorem has a different flavour from the dyadic generator: it
generates a more restrictive set of values (bits) but does so much better because we have
better control of the timing and we can approximate the bits with arbitrary precision.
I Remark. Although it is possible to define bitgen using dygen, it does not, in fact, gives a
shorter proof but definitely gives a more complicated function.
I Theorem 14. There exists Γ ⊆ R and a generable function bitgen : Γ × R2>0 → R such
N
that for any bit sequence b ∈ {0, 1} , there exists αb ∈ Γ such that for any µ ∈ R>0 , n ∈ N
1
and t ∈ [n, n + 2 ],
| bitgen(αb , µ, t) − bn | 6 e−µ .
Furthermore, | bitgen(α, µ, t)| 6 1 for all α, µ and t.

7

Generating an almost piecewise constant function

We have already explained the main intuition of this section in previous sections. Using the
dyadic generator and the bit generator as a signal, we can construct a system that “samples”
the dyadic at the right time and then holds this value still until the next dyadic. In essence,
we just described an almost piecewise constant function. This function still has a limitation:
its rate of change is small so it can only approximate slowly changing functions.
I Theorem 15. There exists an absolute constant δ ∈ N, p ∈ N, Γ ⊆ Rp and a generable
function pwcgen : Γ × R>0 → R such that for any dyadic sequence q ∈ DN then there exists
α ∈ Γ such that for any n ∈ N,
| pwcgen(α, t) − qn | 6 2−L(qn )

for any t ∈ [an + 21 , an+1 ]

and5


pwcgen(α, t) ∈ pwcgen(α, an ), pwcgen(α, an + 12 )
where an =

8

Pn−1

k=0 (δ

for any t ∈ [an , an + 21 ]

+ L(qk )).

Proof of the main theorem

The proof works in several steps. First we show that using an almost constant function, we
can approximate functions that are bounded and change very slowly. We then relax all these
constraints until we get to the general case. In the following, we only consider total functions
over R. See Remark on page 6 for more details.
5

With the convention that [a, b] = [min(a, b), max(a, b)].

CVIT 2016

23:12

A Universal Ordinary Differential Equation

I Definition 16 (Universality). Let I ⊆ R and C ⊆ C 0 (I) × C 0 (I, R>0 ). We say that the
universality property holds for C if there exists d ∈ N and a generable function u such that
for any (f, ε) ∈ C, there exists α ∈ Rd such that
|u(α, t) − f (t)| 6 ε(t)

for any t ∈ dom(f ).

I Lemma 17. There exists a constant c > 0 such that the universality property holds for all
(f, ε) on R>0 such that for all t ∈ R>0 :
ε is decreasing and − log2 ε(t) 6 c0 + t for some constant c0 ,
f (t) ∈ [0, 1],
|f (t) − f (t0 )| 6 cε(t + 1) for all t0 ∈ [t, t + 1].
Proof Sketch. This is essentially a application of pwcgen with a small twist. Indeed the
bound on f guarantees that dyadic rationals are enough. The bound on the rate of change of
f guarantees that a single dyadic can provide an approximation for a long enough time. And
the bound on ε guarantees that we do not need too many digits for the approximations. J
I Lemma 18. The universality property holds for all (f, ε) on R>0 such that f and ε are
differentiable, ε is decreasing and f (t) ∈ [0, 1] for all t ∈ R>0 .
Proof Sketch. Consider F = f ◦ h−1 and E = ε ◦ h−1 where h is a fast-growing function
like fastgen. Then the faster h grows, the slower E and F change and thus we can apply
Lemma 17 to (F, E). We recover an approximation of f from the approximation of F . J
I Lemma 19. The universality property holds for all (f, ε) on R>0 such that f is differentiable
and ε is decreasing.
Proof Sketch. Consider F = 12 + fh and ε = fh where h is a fast-growing function like
fastgen. By taking h big enough, we can ensure that F (t) ∈ [0, 1] and apply Lemma 18 to
(F, E). We then recover an approximation of f from the approximation of F .
J
I Lemma 20. The universality property holds for all continuous (f, ε) on R>0 .
Proof Sketch. Observe that the set of differential functions is dense in the set of continuous
functions and apply Lemma 19.
J
I Lemma 21. The universality property holds for all continuous (f, ε) on R.
Proof Sketch. Let f + be the approximating of f over R>0 , using Lemma 20. Then we
extend and modify f + to R in such a way that the approximation is still good over R>0 but
the function almost vanishes over (−∞, 0]. We then do the same to t 7→ f (−t) − f + (−t) and
sum the two functions.
J
We can now show the main theorem.
Proof of Theorem 3. Lemma 21 gives a generable function u. There exists α such that
|u(α, t) − f (t)| 6 ε(t).
And since u is generable, t 7→ u(α, t) satisfies a PIVP.

J

O. Bournez and A. Pouly

23:13

References
1

2

3
4
5

6

7

8
9
10

11
12
13
14
15
16

17

Steven B Bank. Some results on analytic and meromorphic solutions of algebraic
differential equations. Advances in Mathematics, 15(1):41 – 62, 1975. URL: http:
//www.sciencedirect.com/science/article/pii/0001870875901243, doi:http://dx.
doi.org/10.1016/0001-8708(75)90124-3.
N. M. Basu, S. N. Bose, and T. Vijayaraghavan. A simple example for a theorem of
vijayaraghavan. Journal of the London Mathematical Society, s1-12(4):250–252, 1937.
URL: http://jlms.oxfordjournals.org/content/s1-12/4/250.short, doi:10.1112/
jlms/s1-12.48.250.
Emile Borel. Mémoire sur les séries divergentes. Annales Scientifiques de l’Ecole Normale
Supérieure, 16:9–136, 1899.
Michael Boshernitzan. Universal formulae and universal differential equations. Annals of
mathematics, 124(2):273–291, 1986.
Olivier Bournez, Manuel L. Campagnolo, Daniel S. Graça, and Emmanuel Hainry. Polynomial differential equations compute all real computable functions on computable compact
intervals. Journal of Complexity, 23(3):317–335, June 2007. URL: http://dx.doi.org/
10.1016/j.jco.2006.12.005.
Olivier Bournez, Daniel S. Graça, and Amaury Pouly. On the functions generated by the
general purpose analog computer. CoRR, abs/1602.00546, 2016. URL: http://arxiv.org/
abs/1602.00546.
Olivier Bournez, Daniel S. Graça, and Amaury Pouly. Polynomial Time corresponds
to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length. The
General Purpose Analog Computer and Computable Analysis are two efficiently equivalent models of computations. In 43rd International Colloquium on Automata, Languages,
and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs,
pages 109:1–109:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL:
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6244.
Keith Briggs. Another universal differential equation. arXiv preprint math/0211142, 2002.
V. Bush. The differential analyzer. A new machine for solving differential equations. J.
Franklin Inst., 212:447–488, 1931.
D. C. Carothers, G. E. Parker, J. S. Sochacki, and P. G. Warne. Some properties of solutions
to polynomial systems of differential equations. Electron. J. Diff. Eqns., 2005(40), April
2005.
Etienne Couturier and Nicolas Jacquet. Construction of a universal ordinary differential
equation c∞ of order 3. arXiv preprint arXiv:1610.09148, 2016.
Richard J Duffin. Rubel’s universal differential equation. Proceedings of the National
Academy of Sciences, 78(8):4661–4662, 1981.
D. S. Graça, J. Buescu, and M. L. Campagnolo. Computational bounds on polynomial
differential equations. Appl. Math. Comput., 215(4):1375–1385, 2009.
D. S. Graça, M. L. Campagnolo, and J. Buescu. Computability with polynomial differential
equations. Adv. Appl. Math., 40(3):330–349, 2008.
Daniel S. Graça and José Félix Costa. Analog computers and recursive functions over the
reals. Journal of Complexity, 19(5):644–664, 2003.
G. H. Hardy. Some results concerning the behaviour at infinity of a real and continuous
solution of an algebraic differential equation of the first order. Proceedings of the London
Mathematical Society, 2(1):451–468, 1912.
R.J Lipton and K. W. Regan.
The amazing zeta code.
Post on Blog
"Gödel’s Lost Letter and P=NP", https://rjlipton.wordpress.com/2012/12/04/
the-amazing-zeta-code/, December 4, 2012.

CVIT 2016

23:14

A Universal Ordinary Differential Equation

18
19
20
21

M. B. Pour-El. Abstract computability and its relations to the general purpose analog
computer. Trans. Amer. Math. Soc., 199:1–28, 1974.
L. A. Rubel. A universal differential equation. Bulletin of the American Mathematical
Society, 4(3):345–349, May 1981.
C. E. Shannon. Mathematical theory of the differential analyser. Journal of Mathematics
and Physics MIT, 20:337–354, 1941.
T Vijayaraghavan. Sur la croissance des fonctions définies par les équations différentielles.
CR Acad. Sci. Paris, 194:827–829, 1932.

O. Bournez and A. Pouly

A

23:15

Proofs from Section 3.1 (Generable functions)

Note that Lemma 7 is a corrolary of Theorem 8.
Proof of Theorem 8. For ease of notation in this proof, we now
R t omitR tvariables α and t when
it is clear. By default, all integrals are taken over time, i.e. 0 g = 0 g(α, u)du.
We first show that we can assume that F is a polynomial vector. Since F is generable, by
Definition 5 there exists d ∈ N, p ∈ Rd [Rd ], x0 ∈ Rn , y0 ∈ Rd and y : dom F → Rd such that
y(x0 ) = y0 , Jy (x) = p(y(x)) and F (x) = (y1 (x), . . . , yn (x)) for all x ∈ dom F . Introduce the
function
g(α, t) = y(f (α, t))
for all (α, t) ∈ X. Then for all i ∈ {1, . . . , n},
∂f
∂t

= F (f ) = (y1 (f ), . . . , yn (f ))T = (g1 , . . . , gn )T .

Furthermore,
g(α, t0 ) = y(f (α, t0 )) = y(G(α))
and
∂g
∂t

T
T
= Jy (f ) ∂f
∂t = p(y(f ))(g1 , . . . , gn ) = p(g)(g1 , . . . , gn ) .

Thus the system is of the form
f (α, t0 )= G(α)

∂f
∂t =

(g1 , . . . , gn )T ,

g(α, t0 )= y(G(α))

∂g
∂t =

p(g)(g1 , . . . , gn )T

which is indeed of the form
∂z
∂t

z(α, t0 ) = H(α),

= P (z)

(3)

for some polynomial P and generable H.
We will now show that we can assume that P in (3) has degree 2 and only contains
quadratic terms. Let k be the degree of P , i.e. the largest degree that appears in any of the
polynomials P1 , . . . , Pn . We introduce the variables
ui1 ,...,in = z1i1 · · · znin
where at least one ij > 0 and all ij 6 k. It is then clear that
z(α, t0 ) = α,

∂z
∂t

= Bu

for some matrix B and where u designates the vector of all ui1 ,...,in . Furthermore,
ui1 ,...,in (α, t0 ) = H1 (α)i1 · · · Hn (α)in ,

∂ui1 ,...,in
∂t

=

n
X

k
ui1 ,...,ik −1,...,in ∂z
∂t

k=1,ik >0

where the right-hand side is quadratic because we can subtitute Bu (a linear term) for ∂z
∂t .
The obtained system is thus quadratic, but still includes some linear term (Bu). We can get
rid of them by introducing a constant variable
c=1

CVIT 2016

23:16

A Universal Ordinary Differential Equation

so that
c(α, t0 ) = 1,

∂c
∂t

= 0,

and
∂z
∂t

z(α, t0 ) = α,

= cBu.

The obtained system now of the form
∂x
∂t

x(α, t0 ) = G(α),

= Q(x)

(4)

where G is generable and Q is a polynomial vector with only quadratic terms.
We now show that we can assume that G(α) = α i.e. the identify function. Define
Γ = {G(α) : α ∈ Ω} and for any β ∈ Γ, let Kβ = ∪α∈G−1 ({β}) Jα . The intuition is that if
G(α) = G(α0 ) for α =
6 α0 then z(α, t) = z(α0 , t) so the interval of life is the in fact the union
of both. Consider z the solution to
w(β, t0 ) = β,

∂w
∂t

= Q(w)

(5)

for all β ∈ Γ and t ∈ Kβ . We know the solution exists because w(β, t) = x(α, t) for any α
such that G(α) = β and t ∈ Jα . In particular, x(α, t) = w(G(α), t), so we only need to show
that w is generable to conclude for x. The problem is that Γ is not necessarily open. We
know that Γ is connected since Ω is connected and G is continuous (since it is analytic). But
by standard results on differential equations, if the solution to (5) exists for some β then there
exists a neighbourhood Nβ of β such that the solution still exists over Kβ . Let ∆ = ∪β∈Γ Nβ :
since Γ is connected, there exists an open connected set Γ̃ such that Γ ⊆ Γ̃ ⊆ ∆. Thus we
can consider (5) for all β ∈ Γ̃. Thus x is generable if w is generable.
We can now assume that we are in the case where
f (α, t0 ) = α,

∂f
∂t

= p(f )

for all α ∈ Ω an open connected set, and t ∈ Jα an open interval, and where p is a polynomial
vector with only quadratic terms. Since the system is autonomous, we will also assume that
t0 = 0 without any loss of generality. Since p only has quadratic monomials, we have that
X
pi (x) =
aik` xk x` .
(6)
k6`

We will need to introduce some notation for multidimensional differential calculus:
 ∂p1
 ∂f1
∂p1 
∂f1 
· · · ∂x
· · · ∂α
∂x1
∂α1
n
n

 ..
..  ,
..  .
∂f
..
.
.
Jp (x) =  ...
=
 .
.
.
. 
. 
∂α
∂pn
∂pn
∂αn
∂αn
·
·
·
·
·
·
∂x1
∂xn
∂x1
∂xn
h i
∂pi
∂f
∂fi
In other words, [Jp (x)]ij = ∂x
and ∂α
= ∂α
. We can now move on the proof. Recall
j
j
ij

that we have
∂f
∂t

= p(f ).

(7)

We introduce the new variables6
g=

6

∂f
∂α

g is matrix of variables, i.e. n2 variables that we interpret as a matrix.

(8)

O. Bournez and A. Pouly

23:17

so that
∂f
∂α

= g.

(9)

It follows from (7) that
 
 
∂g
∂f
∂f
∂
∂
=
∂t = ∂t ∂α = ∂α
∂t

∂
∂α

∂f
(p(f )) = Jp (f ) ∂α
= Jp (f )g

(10)

and thus7
t

Z


Jp (f ) .

g = exp

(11)

0

Using our assumption (6) on p, we get that
X
∂pi
∂
=
aik` ∂x
(xk x` )
∂xj
j
k6`

=

X

aikj xk + 2aijj xj +

k<j

=

X

X

aij` x`

j<`

bijk xk

(12)

k

for some coefficients bijk . Introduce the matrices


b1j1 · · · b1jn

.. 
..
Bj =  ...
.
. 
bnj1 · · · bnjn
i.e. [Bj ]ik = bijk . Then (12) becomes
X
∂pi
[Bj ]ik xk
∂xj =
k

= [Bj x]i
∂p
∂xj

= Bj x

Jp (x) = B1 x · · ·

Bn x



Jp (x) = Bx

(13)

where

B = B1

···


Bn .

(14)

It follows from (11) and (13) that

Z t

∂g
∂
exp
Jp (f )
∂αj = ∂αj
0
Z t

Z t

∂
= ∂αj
Jp (f ) exp
Jp (f )
0
0

Z t
∂
=
(J
(f
))
g
p
∂αj
0

7

We use the matrix exponential, and the integral applies componentwise to the matrix Jp (f )g.

CVIT 2016

23:18

A Universal Ordinary Differential Equation

Z

t



∂
∂αj (Bf )

=
0



Z

t

B

=

0

=

∂f
∂αj

g


g

 Z t 
B
g g.

(15)

0

We introduce new variables
Z t
g
w=

(16)

0

so that (15) becomes
∂g
∂αj

= Bwg

(17)

or equivalently
∂gi
∂αj

= Bi wg

(18)

It is clear that
∂w
∂t

=g

(19)

and finally
Z t
∂gi
∂wi
=
∂α
∂α
0
Z t
=
Bi wg
0
Z t
= Bi
w ∂w
∂t

using (16)
using (18)
using (19)

0

= 12 Bi w2

since w(α, 0) = 0.

To summarize we have
f (α, 0)= α,

∂f
∂t =

p(f ),

g(α, 0)= In ,

∂g
∂t =

Jp (f )g,

∂g
∂αj =

∂w
∂t =

g,

∂wi
1
2
∂α = 2 Bi w .

w(α, 0)= 0,

∂f
∂α =

g,
Bwg,

This shows that (f, g, w) is generable since every partial derivative is a polynomial in the
other variables, and we can fix an initial condition by taking one particular α ∈ Ω.
J

B

Proofs from Section 3.2 (Helper functions and constructions)

I Lemma 22. For any t ∈ R, | tanh(t) − sgn(t)| 6 e−|t| .
I Lemma 23 (Reach, [6]). There exists a generable function reach such that for any φ ∈
C 0 (R>0 ), g ∈ C 0 (R) and y0 ∈ R, the unique solution to
y(0) = y0 ,

y 0 (t) = φ(t) reach(g(t) − y(t))

O. Bournez and A. Pouly

23:19

exists over R>0 . Furthermore, for any I = [a, b] ⊆ [0, +∞), if there exists ḡ ∈ R and η ∈ R>0
such that |g(t) − ḡ| 6 η for all t ∈ I, then for all t ∈ I,
 Z t

|y(t) − ḡ| 6 η + exp −
φ(u)du

Z

a

t

φ(u)du > 1.

whenever
a

Furthermore, for all t ∈ I,
|y(t) − ḡ| 6 max(η, |y(a) − ḡ|).
I Lemma 24 (Periodic integral-low). There exists a generable function pil : R>0 × R → R
such that:
pil(µ, ·) is 1-periodic, for any µ ∈ R>0 ,
R 1/2
pil(µ(t), t)dt > 1 for any µ ∈ C 0 (R>0 ),
0


| pil(µ, t)| 6 e−µ for any µ ∈ R>0 and t ∈ 12 , 1 .
Proof. For any t ∈ R and µ ∈ R>0 , let
pil(µ, t) = A 1 + tanh 2(sin(2πt) − 12 )(A + µ)



.

where A = 3. Clearly pil is generable and 1-periodic in t. Let µ ∈ R>0 and t ∈ [ 12 , 1], then
sin(2πt) 6 0
2(sin(2πt) −
| tanh(2(sin(2πt) −
A| tanh(2(sin(2πt) −

1
2 )(A
1
2 )(A

1
2 )(A

+ µ) 6 −A − µ

+ µ)) − (−1)| 6 e−A−µ

using Lemma 22

−A−µ

+ µ)) − (−1)| 6 Ae

| pil(µ, t)| 6 e−µ .

Let µ ∈ C 0 (R>0 ) and t ∈ [0, 21 ]. Observe that pil(µ(t), t) > 0 and, furthermore, if t ∈ [ 18 , 38 ]
then
√
2
sin(2πt) >
2
√
2(sin(2πt) − 12 )(A + µ(t)) > 2 − 1
since A + µ(t) > 1
√
1
tanh(2(sin(2πt) − 21 )(A + µ(t))) > tanh( 2 − 1) >
3
pil(µ(t), t) > 43 A.
It follows that
Z
0

1
2

3
8

Z
pil(µ(t), t)dt >

1
8


pil(µ(t), t)dt >

3 1
−
8 8



4
A
A>
> 1.
3
3
J

Proof Sketch of Theorem 10. Take pereach(t, φ, y, g) = pil(t, φ+r2 )r where r = φ reach(g−
y) where these functions are defined in appendix.
J

CVIT 2016

23:20

A Universal Ordinary Differential Equation

C

Proofs from Section 4 (Generating fast growing functions)

C.1

Proof of Lemma 11

In this section, we sketch the proof of Lemma 11, following the presentation from [1].
For any α ∈ R and t > 0, let
f (α, t) =

1
.
2 − cos(t) − cos(αt)

Since sin and cos are generable, it follows that f is generable because it has a connected domain
of definition. Indeed, f (α, t) is well-defined except on X = {(α, 2kπ) : α ∈ Q, k ∈ N, kα ∈ N}
which is a totally disconnected set in R2 . Let
αa =

∞
X

b−1
n

where bn =

n=1

n−1
Y

ak

k=0

which is well-defined if an is a strictly increasing sequence. Indeed, it implies that bn > (n−1)!
P∞ 1
and αa 6 n=0 n!
= e. One can easily show by contradiction that αa must be irrational.
Also define
Z t
g(α, t) =
f (α, u)du
1

which generable. Let n ∈ N, define δn =
ε = 2πbn − t ∈ [0, 2πδn ] and observe that

P∞

bn
k=n+1 bk .

Let t ∈ [2π(bn − δn ), 2πbn ], write

1 − cos(t) = 1 − cos(t − 2πbn ) = 1 − cos(ε) 6 ε2 6 4π 2 δn2 .
Furthermore, and note that
1 − cos(αt) = 1 − cos(2παbn − ε)
= 1 − cos 2π

n
X

bn
bk

+ 2π

k=0

= 1 − cos 2π

∞
X

∞
X

!
bn
bk

−ε

k=n+1

!
bn
bk

−ε

since

bn
bk

∈ N for k 6 n

k=n+1

= 1 − cos (2πδn − ε)
2

6 (2πδn − ε)
6 (2πδn )

2

since 1 − cos(x) 6 x2
since ε 6 2πδn .

It follows that
f (αa , t) = (1 − cos(t) + 1 − cos(αt))−1 > (4π 2 δn2 + 4π 2 δn2 )−1 >

1
2 .
8π 2 δn

Thus
Z

2πbn

g(αa , 2πbn ) =

f (αa , t)dt
1

Z

2πbn

f (αa , t)dt

>
2π(bn −δn )

since f is positive

O. Bournez and A. Pouly

2πbn

Z
>

2π(bn −δn )
δn
2
8π 2 δn

=

23:21

=

1
2 dt
8π 2 δn

1
8π 2 δn .

But note that
∞
X

δn =
=

bn
bk

k=n+1
a−1
n
1 − a−1
n

∞
X

6

an−k
n

since

bn
bk

= (an · · · ak−1 )−1

k=n+1

6 2a−1
n

since an > 2.

It then easily follows that
g(αa , 2πbn ) >

an
16π 2

and the result follows from the fact that g is nondecreasing.

C.2

Proof of Theorem 12

Let δ = 4. Apply Lemma 11 to get g and c. Let a ∈ NN be an increasing sequence such that
an > xn , then there exists αx ∈ R such that for all n ∈ N,
g(αx , t) > can

(20)

Qn−1
for all t > 2πbn where bn = k=0 ak . Consider the following system of differential equations,
for φ = 2,


 0
y(0) = δ + 2π
y (t) = pereach t, φ, y(t), δ + 1c z(t)g(αx , z(t))
,
.
z(0) = δ + 2π
z 0 (t) = pereach (t, φ, z(t), 1 + y(t))
Apply Theorem 10 to show that y and z exist over R>0 . We will show the following result
by induction on n ∈ N:
min(y(n), z(n)) > δ + 2πbn .

(21)

The result is trivial for n = 0 since y(0) = z(0) = δ + 2π = δ + 2πb0 > 1 + 2πb0 . Let n ∈ N
and assume that (21) holds for n. Apply Theorem 10 to z to get that for any t ∈ [n, n + 12 ],
Z

t

|z(t) − z(n)| 6

Z
exp (−φ) du 6

n

1
n+ 2

n

exp (−φ) du 6 12 e−φ 6 1.

In particular, it follows that for any t ∈ [n, n + 12 ],
z(t) > z(n) − 1 > 2πbn
g(αx , z(t)) > can

using (20)

z(t)g(αx , z(t)) > 2πbn can

since z(t) > 2πbn
since bn+1 = bn an

= 2πcbn+1
δ+

1
c z(t)g(αx , z(t))

R n+ 1

2

> δ + 2πbn+1 .
φ
2

> 1. Apply Theorem 10 to y using the above inequality to get that


Z n+ 1
2
y(n + 12 ) > δ + 2πbn+1 − exp 
φdu > δ + 2πbn+1 − e−1 > δ − 1 + 2πbn+1

Note that

n

φdu =

since z(n) > 1 + 2πbn

n

CVIT 2016

23:22

A Universal Ordinary Differential Equation

and for any t ∈ [n, n + 12 ],
y(t) > min(y(n), δ + 2πbn+1 ) > min(1 + 2πbn , δ + 2πbn+1 ) > 1 + 2πbn ,

(22)

and for any t ∈ [n + 21 , n + 1],
|y(t) − y(n + 12 )| 6

Z

t

1
n+ 2

e−φ du 6

e−φ
2

6 1.

(23)

Thus y(t) > y(n + 12 ) − e−1 > δ − 2 − 2πbn+1 for any t ∈ [n + 12 , n + 1]. Note that
R n+1
φ
1 φdu = 2 > 1 and apply Theorem 10 to z using the above inequality to get that
n+ 2

Z
z(n + 1) >

min

1
u∈[n+ 2 ,n+1]

y(u) − exp

n+1

1
n+ 2

!
φdu

> δ − 2 + 2πbn+1 − e−1 > δ − 3 + 2πbn+1 .

And since δ − 3 > 1, we have shown that y(n + 1) and z(n + 1) are greater than 1 + 2πbn+1 .
Furthermore, (22) and (23) prove that for any t ∈ [n, n + 1],
y(t) > min(1 + 2πbn , δ − 2 + 2πbn+1 ) > 1 + 2πbn .
We can thus let fastgen(α, t) = y(1 + t) and get the result since 1 + 2πbn+1 > an . Finally,
(αx , t) 7→ y(t) is generable because pereach is generable. Indeed, we can move αx from a
parameter to an initial condition and then apply Theorem 8.

D

Proofs from Section 5 (Generating a sequence of dyadic rationals)

I Lemma 25. For any q ∈ Dp , there exists q 0 ∈ Dp+3 such that | sin(2q 0 π) − q| 6 2−p .
Furthermore, x 7→ sin(2πx) is 8-Lipschitz.
Proof. Let f (x) = sin(2πx) for x ∈ [0, 14 ]. Clearly f is surjective from [0, 14 ] to [0, 1] thus
there exists x0 ∈ [0, 14 ] such that f (x0 ) = q. Furthermore, since f 0 (x) = 2π cos(2πx) and
2π 6 8, f is 8-Lipschitz. Let q 0 = b2p+3 x0 c2−p−3 , then q 0 ∈ Dp+3 and |q 0 − x0 | 6 2−p−3 by
construction. Furthermore,
|f (q 0 ) − q| 6 |f (q 0 ) − f (x0 )| + |f (x0 ) − q| 6 8|q 0 − x0 | + 0 6 8 · 2−p−3 6 2−p .
J
Proof of Theorem 13. Let δ = 9. Consider the function

f (α, t) = sin 2απ2t
defined for any α, t ∈ R. Then f is generable because sin and exp are generable. For all
n ∈ N, note that qn ∈ DL(qn ) ⊆ DL(qn )+δ−3 and apply Lemma 25 to qn to get qn0 ∈ DL(qn )+δ
such that
| sin(2qn0 π) − qn | 6 2−L(qn )−δ+3 .

(24)

Now define
αq =

∞
X
k=0

qk0 2−ak

where ak =

k−1
X
`=0

(L(q` ) + δ).

O. Bournez and A. Pouly

23:23

It is not hard to see that αq is well-defined (i.e. the sum converges). Let n ∈ N, then
f (αq , an ) = sin(2παq 2an )
∞
X

= sin 2π

!
qk0 2−ak +an

k=0
n−1
X

= sin 2π

qk0 2−ak +an

+

2πqn0

∞
X

+ 2π

k=0

!
qk0 2−ak +an

.

k=n+1

But for any k 6 n − 1,
an − ak =

n−1
X

(L(q` ) + δ) > L(qk ) + δ

`=k

and since qk0 ∈ DL(qk )+δ and an − ak ∈ N, it follows that qk0 2−ak +an ∈ N. Consequently,
!
∞
X
0
0 −ak +an
f (αq , an ) = sin 2πqn + 2π
qk 2
= sin (2π(qn0 + u))
k=n+1

where u =

P∞

0 −ak +an
.
k=n+1 qk 2

ak − an =

k−1
X

But for any k > n + 1,

(L(q` ) + δ) > L(qn ) +

`=n

k−1
X

δ = L(qn ) + δ(k − n).

`=n

Consequently,
|u| 6

∞
X

|qk0 |2−ak +an

k=n+1

6

∞
X

−L(qn )−δ(k−n)

2

62

−L(qn )

k=n+1

∞
X

2−δk 6 2−L(qn )−δ+1 .

k=1

Since x 7→ sin(2πx) is 8-Lipschitz, it follows that
|f (αq , an ) − qn | = | sin (2π(qn0 + u)) − qn |
6 | sin (2π(qn0 + u)) − sin(2πqn0 )| + | sin(2qn0 π) − qn |
6 8|u| + 2−L(qn )−δ+3
68·2

−L(qn )−δ+1

−L(qn )−δ+5

62

+2

using (24)
−L(qn )−δ+3

.

(25)

Recall that round is the generable rounding function from Lemma 9, and fastgen the fast
growing function from Theorem 12. Let α, β, t ∈ R, if fastgen(β, t) exists then let
dygen(α, β, t) = f (α, r(β, t))
where

r(β, t) = round t − 41 , fastgen(β, t) ln 2, 4 .
Note that dygen is generable because f, round and fastgen are generable. Apply8 Theorem 12
to get βq ∈ R such that for any n ∈ N and t ∈ R>0 ,
fastgen(βq , t) > an + L(qn ) + δ
8

if t ∈ [an , an + 1).

Technically speaking, we apply it to the sequence xn = ak if n = ak + L(qn ) + δ, and xn = 0 otherwise.

CVIT 2016

23:24

A Universal Ordinary Differential Equation

Let n ∈ N and t ∈ [an , an + 12 ], then t −
can apply Lemma 9 and get that

1
4


∈ an −

1
2

+ λ1 , an +

1
2

−

1
λ



for λ = 4. Thus we

|r(βq , t) − an | 6 e− fastgen(βq ,t) ln 2 = 2− fastgen(βq ,t) 6 2−an −L(qn )−δ 6 1.

(26)

Observe that
∂f
∂t (αq , t)

= 2π|αq |2t | cos(2αq π2t )| 6 2π2t 6 2t+3 .

Thus for any t, t0 ∈ R,
0

|f (αq , t) − f (αq , t0 )| 6 23+max(t,t ) |t − t0 |.
It follows that for any n ∈ N and t ∈ [an , an + 12 ],
| dygen(αq , βq , t) − qn | = |f (αq , r(βq , t)) − qn |
6 |f (αq , r(βq , t)) − f (αq , an )| + |f (αq , an ) − qn |
6 23+max(an ,r(βq ,t)) |r(βq , t) − an | + 2−L(qn )−3
3+an +1 −L(qn )−an −δ

62

2

−L(qn )−δ+4

62

+2

+2

using (25)

−L(qn )−δ+5

using (26)

−L(qn )−δ+5

6 2−L(qn )−δ+6
6 2−L(qn )−3

since δ − 6 > 3.
J

E

Proofs froms Section 6 (Generating a sequences of bits)

E.1

Proof of Theorem 14

Consider the function
f (α, t) = sin 2πα4t +

4π
3



defined for any α, t ∈ R. Then f is generable because sin and exp are generable. For any
N
b ∈ {0, 1} , let
αb =

∞
X

2bk 4−k−1 .

k=0
N

Let b ∈ {0, 1} and n ∈ N, observe that
f (αb , n) = sin 2π

∞
X

!
−k−1 n

2bk 4

4 +

4π
3

k=0





 n−1
∞
X
 X
n−k−1
−1
= sin 
+2π2b
4
+
2π
2bk 4n−k−1 +
2π
2b
4
n
k

 k=0
k=n+1
|
{z
}
∈N

= sin πbn +

4π
3


+ε




4π 
3 



O. Bournez and A. Pouly

23:25

where
ε = 2π

∞
X

2bk 4n−k−1 = 4π

k=n+1

∞
X

bk 4−k−2 6 4π

k=0

It follows that if bn = 0 then πbn + 4π
3 +ε ∈
Thus
h
√ i
f (αb , n) ∈ −1, − 23 if bn = 0,

∞
X

π
.
3

−2

4−k−2 = 4π 4 3 =

k=0

 4π
3

,


5π
3

and if bn = 1 then πbn + 4π
3 +ε ∈

f (αb , n) ∈

h√

i

3
2 ,1

if bn = 1.

 7π
3


, 8π
3 .
(27)

Furthermore,
|αb | =

∞
X

2bk 4−k−1 6

2
4

∞
X

4−k 6 23 .

(28)

k=0

k=0



Let ε ∈ − 12 , 12 , then for any t ∈ R,
|f (αb , t + ε) − f (αb , t)| = sin 2παb 4t+ε +

4π
3 −
t+ε

= 2 cos(2παb (4t + 4



sin 2παb 4t +

)+

8π
3 ) sin

4π
3



2παb (4t+ε − 4t )



6 2| sin(2παb (4t+ε − 4t ))|
6 4π|αb ||4t+ε − 4t |
2
6 4π 4t |4ε − 1|
3
8π t
4 2ε
6
3
6 4t Bε

using (28)
using that |ε| 6

1
2

(29)

for some constant B > 0. Recall that round is the generable rounding function from Lemma 9.
Let α, t ∈ R, µ ∈ R>0 and define
g(α, t) = f (α, r(t)) where

r(t) = round(t − 41 , t ln 4 + ln B, 4).

1
Note again that
generable
f and round are
 g is
 because

 generable. Let n ∈ N and t ∈ [n, n+ 2 ],
1
1
3
1
1
1
1
then t− 4 ∈ n − 4 , n + 4 = n − 4 + λ , n + 2 − λ for λ = 4. Thus we can apply Lemma 9
and get that

|r(t) − n| 6 e−(n+1) ln 4+ln B =

4−n−1
B .

It follows using (29) that
|g(αb , t) − f (αb , n)| = |f (αb , r(t)) − f (αb , n)| 6 4t B 4

−n−1

B

= 14 .

√



− 14 > 12 , we conclude using (27) that for any t ∈ n, n + 21 ,




g(αb , t) ∈ −1, − 12 if bn = 0,
g(αb , t) ∈ 12 , 1 if bn = 1.

And since

3
2

(30)

Finally, let α, t ∈ R, µ ∈ R>0 and define
bitgen(α, µ t) =

1 + tanh(2µg(α, t))
.
2

Note
is generable because tanh and g are generable. Let µ ∈ R>0 , n ∈ N and
 that bitgen

t ∈ n, n + 12 . If bn = 0, then it follows from (30) that
g(αb , n) 6 − 21

CVIT 2016

23:26

A Universal Ordinary Differential Equation

| tanh(2µg(αb , n)) − sgn(2µg(αb , n))| 6 e−2µ|g(αb ,n)|
| tanh(2µg(αb , n)) + 1| 6 e

using Lemma 22

−µ

| bitgen(αb , µ, t) − bn | 6 21 e−µ 6 e−µ

since bn = 0.

Similarly, if bn = 1, then
g(αb , n) >

1
2
−2µ|g(αb ,n)|

| tanh(2µg(αb , n)) − sgn(2µg(αb , n))| 6 e

| tanh(2µg(αb , n)) − 1| 6 e−µ
| bitgen(αb , µ, t) − bn | 6 21 e−µ 6 e−µ

since bn = 1.

This proves the result.

F

Proofs from Section 7 (Generating an almost piecewise constant
function)

Proof of Theorem 15. Apply Theorem 13 to get δ ∈ N, dygen generable, and αq , βq such
that for any n ∈ N,
| dygen(αq , βq , t) − qn | 6 2−L(qn )−3
where an =
(
1
bn =
0

Pn−1

k=0 (L(qk )

for any t ∈ [an , an + 12 ]
N

+ δ). Let b ∈ {0, 1} be the bit sequence defined by

if n = ak for some k
otherwise

Apply Theorem 14 to get bitgen and γb such that for any µ ∈ R>0 , n ∈ N and t ∈ [n, n + 12 ],
| bitgen(γb , µ, t) − bn | 6 e−µ .
Let xn = L(qn ) + 3 and apply Theorem 12 to get λa and fastgen such that for any n ∈ N,
fastgen(λa , t) > xn

for all t ∈ [n, n + 1].

Consider the following system for all t ∈ R>0 :
y(0) = q0 ,

y 0 (t) = ψ(t)r(t),

r(t) = pereach(t, φ(t), y(t), g(t))

where
φ(t) = t + fastgen(λa , t),
g(t) = dygen(αq , βq , t),

ψ(t) = 2 bitgen(γb , φ(t) + R(t), t),
R(t) = 1 + r(t)2 .

We omitted the parameters α, β, γ, λ in the functions g and φ to make it more readable. It
is clear that g and φ are generable since bitgen, fastgen, dygen are generable. It follows
that (α, β, γ, λ, t) 7→ y(t) is also generable. Indeed, we can move α, β, γ, λ from parameters
to an initial condition and then apply Theorem 8.
We will show the result by induction. Let n ∈ N and assume that |y(an ) − qn | 6 2−xn .
Note that this is trivially satisfied for n = 0 since a0 = 0 and thus y(a0 ) = y(0) = q0 . We
will now analyze the behavior of y over [an , an+1 ] by making a case distinction between
[an , an + 1] and [an + 1, an+1 ]. Note that for all t, R(t) > |r(t)| > 0.

O. Bournez and A. Pouly

23:27

When t ∈ [an , an + 12 ], we have that
| bitgen(γb , µ, t) − ban | 6 e−µ
but ban = 1 by definition thus
bitgen(γb , φ(t) + R(t), t) > 1 − e−φ(t) >

1
2

since φ(t) > fastgen(λa , t) > 1. Furthermore,
φ(t) > fastgen(λa , t) > fastgen(λ, n) > xn > 2.
Thus ψ(t)φ(t) = 2 bitgen(γb , φ(t) + R(t), t)φ(t) > xn > 2. Furthermore,
|g(t) − qn | = | dygen(αq , βq , t) − qn | 6 2−xn .
Thus we can apply Theorem 10 to get that


Z an + 1
2
|y(an + 12 ) − qn | 6 2−xn + exp −
ψ(u)φ(u)du 6 2−xn + e−xn 6 2−xn +1 .
an

Furthermore, Theorem 10 also gives us that
|y(t) − qn | 6 min(2−xn , |y(an ) − qn |).
When t ∈ [an + k + 12 , an + k + 1] for an 6 an + k < an+1 , we have that
y 0 (t) = ψ(t) pereach(t, φ(t), y(t), g(t))
where |ψ(t)| 6 2 since | bitgen | 6 1 by Theorem 14 and
φ(t) > t + fastgen(λa , t) > t + fastgen(λ, n) > t + xn .
Thus by Theorem 10
|y(t) − y(an + k + 21 )| 6

Z

t

1
an +k+ 2

ψ(u) exp(−φ(u))du 6 12 2e−xn

Z

t

1
an +k+ 2

e−u du.

When t ∈ [an + k, an + k + 12 ] for an < an + k < an+1 , we have that
| bitgen(γb , µ, t) − ban +k | 6 e−µ
but ban +k = 0 by definition thus
| bitgen(γb , φ(t) + R(t), t)| 6 e−φ(t)−R(t) .
Furthermore,
φ(t) > t + fastgen(λa , t) > t + fastgen(λ, n) > t + xn .
Thus
|ψ(t)| = 2| bitgen(γb , φ(t) + R(t), t)| 6 2e−t−xn e−R(t) 6 2e−t−xn e−|r(t)| .

CVIT 2016

23:28

A Universal Ordinary Differential Equation

It follows that
y 0 (t) = ψ(t)r(t)
where
|ψ(t)r(t)| 6 2e−φ(t)−R(t) |r(t)| 6 2e−t−xn .
Consequently,
Z
|y(t) − y(an + k)| 6

1
an +k+ 2

|ψ(u)r(u)|du 6 e

−xn

an +k

Z

1
an +k+ 2

e−u du.

an +k

Putting everything together we get that for any t ∈ [an + 21 , an+1 ],
|y(t) − y(an + 12 )| 6 e−xn

Z

t

e−u du 6 e−xn

an +1

and thus for all t ∈ [an + 21 , an+1 ],
|y(t) − qn | 6 e−xn + |y(an + 12 ) − qn | 6 e−xn + 2−xn +1 6 2−xn +2 6 2−L(qn ) .

(31)

Also recall that for all t ∈ [an , an + 12 ],
|y(t) − qn | 6 min(2−xn , |y(an ) − qn |).

(32)

Applying Theorem 8, we get that the map Y (q0 , αq , βq , γq , t) = y(t) is generable.

G

J

Proofs from Section 8 (Proof of the main theorem)

G.1

Proof of Lemma 17

Let c = 18 . Apply Theorem 15 to get p, δ ∈ N and pwcgen. Let f and ε be as described in
the statement. For any n ∈ N, let qn ∈ D be such that
|f (n) − qn | 6 2−L(qn ) 6 cε(n + 1).
Since by assumption, − log2 ε(n + 1) 6 c0 + n + 1, we can always choose qn so that
L(qn ) = c0 + n + 1.
Then by Theorem 15, there exists αq ∈ Rp such that
| pwcgen(αq , t) − qn | 6 2−L(qn )

for any t ∈ [an + 12 , an+1 ]

and


pwcgen(αq , t) ∈ pwcgen(αq , an ), pwcgen(αq , an + 12 )

for any t ∈ [an , an + 21 ]

where
an =

n−1
X
k=0

(δ + L(qk )) =

n−1
X
k=0

(δ + c0 + n + 1) = n(δ + c0 + 1) + 21 n(n − 1).

(33)

O. Bournez and A. Pouly

23:29

Introduce the function
ξ(t) = t(δ + c0 + 1) + 21 t(t − 1)
so that an = ξ(n) and note that ξ is increasing and generable. Let t ∈ [ξ −1 (an + 12 ), ξ −1 (an+1 )],
since ξ is increasing, so is ξ −1 and
n = ξ −1 (an ) 6 ξ −1 (an + 12 ) 6 t 6 ξ −1 (an+1 ) = n + 1.
So in particular,
|f (n) − f (t)| 6 cε(n + 1)
by the assumption on f , since t ∈ [n, n + 1]. It follows that
| pwcgen(αq , ξ(t)) − f (t)| 6 | pwcgen(αq , ξ(t)) − qn |
+ |qn − f (n)| + |f (n) − f (t)|
6 2−L(qn ) + 2−L(qn ) + cε(n + 1)

since ξ(t) ∈ [an + 21 , an+1 ]

6 3cε(n + 1)
since ε is decreasing

6 3cε(t)
6 ε(t)

since 3c 6 1.

So in particular, in implies that for all n ∈ N,
| pwcgen(αq , an + 12 ) − f (ξ −1 (an + 12 ))| 6 3cε(n + 1)

(34)

and
| pwcgen(αq , an+1 ) − f (n + 1)| 6 3cε(n + 2).

(35)

Let t ∈ [ξ −1 (an+1 ), ξ −1 (an+1 + 12 )], it follows using (33) that there exists u ∈ [0, 1] such that
pwcgen(αq , ξ(t)) = u pwcgen(αq , an+1 ) + (1 − u) pwcgen(αq , an+1 + 12 ).
We also have that
n + 1 = ξ −1 (an+1 ) 6 t 6 ξ −1 (an+1 + 12 ) 6 ξ −1 (an+2 ) = n + 2.
Thus
| pwcgen(αq , ξ(t)) − f (t)| 6 u| pwcgen(αq , an+1 ) − f (t)|
+ (1 − u)| pwcgen(αq , an+1 + 12 ) − f (t)|
6 | pwcgen(αq , an+1 ) − f (n + 1)| + |f (n + 1) − f (t)|
+ | pwcgen(αq , an+1 + 12 ) − f (ξ −1 (an+1 + 12 ))|
+ |f (ξ −1 (an+1 + 12 )) − f (t)|
6 3cε(n + 2) + |f (n + 1) − f (t)|
+ 3cε(n + 2)
+ |f (ξ

−1

(an+1 +

using (34)
using (35)

1
2 ))

6 3cε(n + 2) + cε(n + 2)

− f (t)|
since t ∈ [n + 1, n + 2]

+ 3cε(n + 2)

CVIT 2016

23:30

A Universal Ordinary Differential Equation

since ξ −1 (an+1 + 12 ) ∈ [t, t + 1]

+ cε(t)
6 7cε(n + 2) + cε(t)

since ε decreasing

6 8cε(t)
6 ε(t)

since 8c 6 1.

Putting everything together, we can get that
| pwcgen(αq , ξ(t)) − f (t)| 6 ε(t)

for all t > ξ −1 (a0 + 21 ).

But note that ξ −1 (a0 + 12 ) 6 ξ −1 (a1 ) = 1 so we have that
| pwcgen(αq , ξ(t)) − f (t)| 6 ε(t)

for all t > 1

and note that (α, t) 7→ pwcgen(α, ξ(t)) is generable.
Note that this is not exactly the claimed result since it is only true for t > 1 instead of
t > 0 but this can remedied for with proper shifting. Indeed, consider the operator
(Sf )(t) = f (max(t − 1, 0)).
We claim that if (f, ε) satisfies the assumption of the Lemma, then so does (Sf, Sε) and
| pwcgen(α, ξ(t)) − (Sf )(t)| 6 (Sε)(t)

for all t > 1

| pwcgen(α, ξ(t)) − f (t − 1)| 6 ε(t − 1)

for all t > 1

| pwcgen(α, ξ(t + 1)) − f (t)| 6 ε(t)

for all t > 0.

G.2

Proof of Lemma 18

Apply Lemma 17 to get c > 0 and u generable. Let a ∈ NN be an increasing sequence, and
apply Theorem 12 to get αa . Recall that fastgen(αa , ·) is positive, thus we can let
t

Z
g(α, t) =

1 + fastgen(α, u)du,

hα (t) = g(α, t).

0

Clearly g is generable since fastgen is generable. Since fastgen is increasing, hα is increasing.
Furthermore,
Z

1+n

hαa (n + 1) >

Z

1+n

fastgen(αa , u)du >
n

fastgen(αa , n)du = fastgen(αa , n) > an .
n

Thus hαa (n) → +∞ as m → +∞. This implies that hαa is bijective from R>0 to R>0 . Note
−1
that since hαa is increasing then h−1
αa is also increasing. Also since hαa (t) > t then hαa (t) 6 t
for all t ∈ R>0 . Let f, ε be as described in the statement. For any ξ ∈ R>0 , let
F (ξ) = f (h−1
αa (ξ)),

E(ξ) = ε(h−1
αa (ξ)).

Then for any t ∈ R>0 ,
0
0 −1
F 0 (hαa (t)) = (h−1
αa ) (hαa (t))f (hαa (hαa (t)))

=

0
1
h0αa (t) f (t)

=

0
1
1+fastgen(αa ,t) f (t).

since h0 (h−1 )0 ◦ h = 1

O. Bournez and A. Pouly

23:31

−1
0
Also note that since h0αa (t) = 1 + fastgen(αa , t) > 1, then (h−1
αa ) (t) 6 1 and thus hαa is
0
0
0
1-Lipschitz. Let ξ ∈ R>0 and ξ ∈ [ξ, ξ + 1]. Write ξ = hαa (t) and ξ = hαa (t ), then
|F (ξ)−F (ξ 0 )|
E(ξ+1)

6

|ξ−ξ 0 | maxu∈[ξ,ξ0 ] |F 0 (ξ)|
E(ξ+1)

6

maxu∈[t,t0 ] |F 0 (hαa (u))|
E(ξ+1)

since |ξ − ξ 0 | 6 1

|f 0 (u)|
u∈[t,t ] E(ξ+1)(1+fastgen(αa ,u))

= max0
6

maxu∈[t,t+1] |f 0 (u)|
ε(h−1
αa (hαa (t)+1))(1+fastgen(αa ,t))

since fastgen is increasing.

−1
−1
but since h−1
αa is 1-Lipschitz and increasing, hαa (hαa (t) + 1) 6 hαa (hαa (t)) + 1 = t + 1,

6

maxu∈[t,t+1] |f 0 (u)|
ε(t+1)(1+fastgen(αa ,t))

since ε is decreasing

0

6

maxu∈[t,t+1] |f (u)|
ε(t+1)(1+fastgen(αa ,btc))

since fastgen is decreasing

0

6

maxu∈[t,t+1] |f (u)|
ε(t+1)(1+abtc )) .

Note that both f 0 and ε do not depend on a. Thus by choosing the sequence a large enough,
we can make the above quantity arbitrarily small, and thus small that c for all t ∈ R>0 .
Similarly,
0
0 −1
E 0 (hαa (t)) = (h−1
αa ) (hαa (t))ε (hαa (hαa (t)))

=

0
1
h0αa (t) ε (t)

=

0
1
1+fastgen(αa ,t) ε (t).

Thus
ξ

E 0 (e)
de − 21 log2 E(0)
0 E(e)
Z ξ
−E 0 (e)
de
= − 12 log2 ε(0) + ln12
E(e)
0
−E 0 (e)
6 − 12 log2 ε(0) + lnξ 2 sup
e∈[0,ξ] E(e)

− log2 E(ξ) = − ln12

Z

6 − 21 log2 ε(0) +

ξ
ln 2

6 − 12 log2 ε(0) +

ξ
ln 2

−E 0 (hαa (t))
E(hαa (t))
t∈[0,h−1
α (ξ)]
sup

a

−ε0 (t)
ε(t)(1 + fastgen(αa , t))
t∈[0,h−1
α (ξ)]
sup

a

log2 ε(0) +

ξ
ln 2

−ε0 (t)
t∈[0,ξ] ε(t)(1 + fastgen(αa , t))

6 − 21 log2 ε(0) +

ξ
ln 2

−ε0 (t)
.
t∈[0,ξ] ε(t)(1 + abtc )

6

− 12

sup

using h−1
αa (ξ) 6 ξ

sup

Note that both ε0 and ε do not depend on a. Thus by choosing the sequence a large enough,
we can make the quantity in the sup arbitrarily small, thus smaller than ln 2 for all t ∈ R>0 ,
yielding
− log2 E(ξ) 6 c0 + ξ

CVIT 2016

23:32

A Universal Ordinary Differential Equation

for some constant c0 . Thus we can apply Lemma 17 to (F, E) and get βFp such that
|u(βF , ξ) − F (ξ)| 6 E(ξ)

for all ξ ∈ R>0 .

For any α, β, t, let
ū(α, β, t) = u(β, g(α, t)).
Clearly ū is generable because u and g are generable. Then for any t ∈ R>0 , recall that
g(αa , t) = hαa (t) and thus
|ū(αa , βF , t) − f (t)| = |u(β, hαa (t)) − F (hαa (t))| 6 E(hαa (t)) = ε(t).

G.3

Proof of Lemma 19

Apply Lemma 18 to get p ∈ N and u generable. Let a ∈ NN be an increasing sequence, and
apply Theorem 12 to get αa . Recall that fastgen(αa , ·) is positive and increasing. Let f, ε be
as described in the statement. For any t ∈ R>0 , let
F (t) =

1
2

+

f (t)
1+fastgen(αa ,t) ,

E(t) =

ε(t)
1+fastgen(αa ,t) .

Then for any n ∈ N and t ∈ [n, n + 1], we have that
|F (t) − 12 | =

f (t)
1+fastgen(αa ,t)

6

|f (t)|
1+an .

Thus we can choose an = 2 maxu∈[t,t+1] |f (u)| and get that |F (t) − 12 | 6 21 for all t ∈ R>0 ,
and thus F (t) ∈ [0, 1]. Furthermore, F is differentiable and E is decreasing because ε is
decreasing and fastgen increasing. Apply Lemma 18 to (F, ε) to get βF ∈ Rp such that
|u(βF , t) − F (t)| 6 E(t)

for all t ∈ R>0 .

For any α, β, t, let
ū(α, β, t) = (1 + fastgen(α, t))(u(β, t) − 12 ).
Clearly ū is generable because u and fastgen are generable. Then for any t ∈ R>0 ,


f (t)
|ū(αa , βF , t) − f (t)| = (1 + fastgen(αa , t)) u(β, hαa (t)) − 12 − 1+fastgen(α
,t)
a
= (1 + fastgen(αa , t))| (u(β, hαa (t)) − F (t))|
6 (1 + fastgen(αa , t))E(t)
6 ε(t).

G.4

Proof of Lemma 20

Apply Lemma 19 to get p ∈ N and u generable. Let f ∈ C 0 (R>0 , R) and ε ∈ C 0 (R>0 , R>0 ).
Then there exists f˜ ∈ C 1 (R>0 , R) and a decreasing ε̃ ∈ C 0 (R>0 , R>0 ) such that
|f˜(t) − f (t)| 6 ε̃(t) 6

ε(t)
2 .

We can then apply Lemma 19 to (f˜, ε̃) to get αf˜ ∈ Rp such that
|u(αf˜, t) − f˜(t)| 6 ε̃(t)

for all t ∈ R>0 .

But then for any t ∈ R>0 ,
|u(αf˜, t) − f (t)| 6 |u(αf˜, t) − f˜(t)| + |f˜(t) − f (t)|
6 ε̃(t) + ε̃(t)
6 ε(t).

O. Bournez and A. Pouly

G.5

23:33

Proof of Lemma 21

I Lemma 26. There exists a generable function u such that for all f ∈ C 0 (R>0 , R), ε ∈
C 0 (R, R>0 ) and δ > 0, there exists α such that
|u(α, t) − f (t)| 6 ε(t) for all t > 0,
|u(α, t)| 6 |f (−t)| + ε(t) for all t ∈ [−δ, 0],
|u(α, t)| 6 ε(t) for all t 6 −δ.
p
√
Proof. Apply Lemma 20 to get u. Note that t 7→ f ( t), t 7→ ε( (t)) and max are continuous,
so there exists α such that
√
√
√
|u(α, t) − f ( t)| 6 21 min(ε( t), ε(− t))
for all t > 0.
For any α, t define
U(α, β, t) = s(t)u(α, t2 ),

s(t) =

1
2

+

1
2

tanh(A(t)( 2δ + t)),

A(t) = fastgen(β, t).

Let an be a sequence such that for all n ∈ N,
!
an >

2
δ

sup

|f (t)| +

t∈[n,n+1]

sup

− log ε(t) .

t∈[−n−1,n+1]

Then there exists βa such that for all n ∈ N,
fastgen(β, t) > an

for all t > n.

Let t > 0, then
A(t) = fastgen(β, t)
> abtc
!
>
>
|1 −

( 2δ + t)A(t)
tanh(( 2δ + t)A(t))|

2
δ
2
δ

sup

|f (u)| +

u∈[btc,dte]

sup

− log ε(u)

u∈[−dte,dte]

(|f (t)| − log ε(t))

> |f (t)| − log ε(t)
6 e−|f (t)|+log ε(t)

|1 − s(t)| 6

ε(t) −|f (t)|
.
2 e

It follows that
|f (t) − U(α, β, t)| 6 |f (t) − u(α, t2 )| + |u(α, t2 )(1 − s(t))|
6 12 ε(t) + |u(α, t2 )||1 − s(t)|
6 21 ε(t) + |u(α, t2 )||1 − s(t)|
−|f (t)|
6 21 ε(t) + (|f (t)| + 12 ε(t)) ε(t)
2 e

6 ε(t)

using e−x x 6 1.

Let t ∈ [−δ, 0], then |s(t)| 6 1 thus
|U(α, β, t)| 6 |u(α, t2 )| 6 |f (−t)| + ε(t).
Let t 6 −δ, then with a similarly argument as above
|s(t)| 6

ε(t) −|f (−t)|
.
2 e

CVIT 2016

23:34

A Universal Ordinary Differential Equation

It follows that
−|f (−t)|
|U(α, β, t)| 6 |u(α, t2 )||s(t)| 6 (|f (−t)| + ε(t)) ε(t)
6 ε(t).
2 e

J
Proof of Lemma 21. Let c = 14 . Apply Lemma 26 to get u. Then there exists α such that
|u(α, t) − f (t)| 6 cε(t) for all t > 0,
|u(α, t)| 6 |f (−t)| + cε(t) for all t ∈ [−1, 0],
|u(α, t)| 6 cε(t) for all t 6 −1.
For all t ∈ R, let
g(t) = f (−t) − u(α, −t).
Since this is a continuous function, we can apply the lemma again to get α0 such that
|u(α0 , t) − g(t)| 6 cε(t) for all t > 0,
|u(α0 , t)| 6 |g(−t)| + cε(t) for all t ∈ [−1, 0],
|u(α0 , t)| 6 cε(t) for all t 6 −1.
For all α, α0 , t let
U(α, α0 , t) = u(α, u) + u(α0 , −t).
We claim that U satisfies the theorem:
If t > 1 then −t 6 −1 thus
|U(α, α0 , t) − f (t)| 6 |u(α, t) − f (t)| + |u(α0 , −t)| 6 cε(t) + cε(t) 6 ε(t).
If 0 6 t 6 1 then −1 6 −t 6 0 thus
|U(α, α0 , t) − f (t)| 6 |u(α, t) − f (t)| + |u(α0 , −t)|
6 cε(t) + |g(−t)| + cε(t)
6 cε(t) + |g(−t)| + cε(t)
6 cε(t) + |f (t) − u(α, t)| + cε(t)
6 3cε(t) 6 ε(t).
If t 6 0 then −t > 0 and thus
|U(α, α0 , t) − f (t)| = |u(α0 , t) + u(α, t) − f (t)|
= |u(α0 , −t) − g(−t)|
6 cε(t).
J

G.6

Proof of Theorem 3

Apply Lemma 21 to get an integer p and a generable function u. By definition of u, there
exists an integer d, a polynomial matrix q, an initial condition α0 , t0 , y0 and y : dom u → Rd
such that
y(α0 , t0 ) = y0 and Jy (α, t) = q(y(α, t)) for all (α, t) ∈ dom y,
y1 (α, t) = u(α, t) for all (α, t) ∈ dom y.

O. Bournez and A. Pouly

23:35

Let α ∈ R and for any t ∈ R let
zα (t) = y(α, t).
Then notice that
zα0 (t) = Jy (α, t)(0, · · · , 0, 1)T = q(y(α, t))(0, · · · , 0, 1)T = p(zα (t))
where p is a polynomial that does not depend on α. Thus if we consider the system
z(0) = y(α, 0),

z 0 (t) = p(z(t))

for some α such that (α, t) ∈ dom u for all t ∈ R, then it is clear that zα is the unique solution
and it satisfies the universality property.

CVIT 2016

