# Modeling Reality

*A surprising theorem about differential equations*

Composite of src1, src2. |

Olivier Bournez and Amaury Pouly have proved an interesting theorem about modeling physical systems. They presented their paper at ICALP 2017 last month in Warsaw.

Today Ken and I wish to explain their theorem and its possible connections to complexity theory.

Of course as theorists we are most interested in discrete systems and rarely if ever mess with differential equations. I do recall, with some awe, that when I started my career at Yale the numerical analysts were experts at ODEs: that’s ordinary differential equations for the rest of us. An ODE is an equation that involves functions of one independent variable and its derivatives. A famous one is Isaac Newton’s second law of motion:

They used their ability to guess solutions to discrete recurrence systems. I do not believe there is an exact meta-theorem connecting discrete recurrences with ODEs but at the heuristic level they were able to just look at a recurrence and say *I believe the solution is * And they were usually right.

Let’s get back to what Bournez and Pouly (BP) have proved.

## The Old Result

Let’s first state what BP proved and then discuss their result. Their result is an extension of a 1981 theorem of Lee Rubel, which Bournez and Pouly call “an astonishing fact.” Rubel proved there is a differential equation that is “universal” in the sense expressed by his theorem statement:

Theorem 1There exists a fourth order differential algebraic equation (DAE)where is a polynomial in four variables and integer coefficients such that for any continuous function and any there is a smooth solution to (*) such that for all real ,

Rubel actually proved more: the theorem allows to be any continuous positive function: so the error between the solution and can decay off as tends to plus or minus infinity. He also exhibited specific polynomials . If we rename the differentials to variables , respectively, then Rubel’s simplest one is:

Boulez and Pouly note that simpler ones were found by others, including two whole families by Richard Duffin and one in a neat paper by Keith Briggs where one can take any :

Note that all three have the same “differential monomials” and approach each other as one chooses higher, as is most obvious on multiplying by .

## The New Result

The theorem may be astonishing but according to BP is also a bit disappointing. They say:

As we said, Rubel’s proof can be seen as an indication that (fourth-order) polynomial implicit DAE is too loose a 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 little sense to try to fit a differential model because a single equation can model everything with arbitrary precision.

They cite two more deficiencies of all these results:

First, … the proofs heavily rely on the fact that constructed DAE does not have unique solutions for a given initial data. … Rubel’s DAE never has a unique solution, even with a countable number of [initial] conditions of the form . 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.

This leads into what BP proved (their emphasis):

Theorem 2There exists afixedpolynomial in variables, for some , so that for any continuous and any there exist so that there is a uniqueanalyticfunction so that

- The function is a solution in the sense that
- For all real ,
.

As with Rubel’s result they actually prove the stronger form where can be any continuous positive function so that the error between the solution and can decay off just like before.

## ODEs As Models

BP’s theorem differs from Rubel’s in that their solution is unique and analytic. This has several ramifications. For one it makes the proof harder, since gluing functions together as Rubel did fails for analytic function. The proof uses some programming tricks instead. One ingredient is that the function

can be modulated for any irrational to bring both and arbitrarily close to multiples of without the denominator vanishing. That is, they can make the fraction grow fast while retaining analyticity. Émile Borel once conjectured that solutions to -variable ODEs that are defined on all of must have growth bounded by a stack of exponentials. This conjecture was refuted even for , and BP were able to apply the refutation.

Second, their theorem cuts down the extreme multiplicity of solutions all the way to one. In real life we expect that the equation given the initial conditions uniquely forces the total behavior of the solution. As they quote, Rubel’s paper had even given as open “whether we can require in our theorem that the solution that approximates to be the unique solution for its initial data.”

Their result can be viewed both as a positive result and a negative one. On the one hand they show that ODEs are very powerful and can model almost any reasonable computation. You can think of this as showing the power of *analog computation*. On the other hand, they show that models based on ODEs may likewise be too powerful. They too may be so powerful that they are not really useful.

One weakness is that their polynomial is not so simple. They outline how their construction can be effectivized to give somewhere north of 300. Possibly it can be tightened much further. They point out an analogy with the kind of universality shown for the Riemann zeta function by Sergei Voronin, citing one of our two posts on it for reference. The zeta function is analytic but cannot be a solution to any polynomial ODE (nor DAE). We can try to motivate the task of improving and by noting how a minimum universal ODE is a natural and fixed version of a minimum universal program.

## Open Problems

What are some further implications of the new result for modeling nature? Is there some way we can stratify differentially simulatable systems according to some (concrete) measure of their computational complexity?

The universality of fixed ODEs reminds me a little of the old result of Pour-El and Richards which showed that there are computable ODEs (in the Turing/Bishop sense) that have only uncomputable solutions. Of course this is very far from the analytic case discussed here.

I like how when experts overuse the word ‘possible’ all the time it is accepted.

Here’s a related project —

☞ DATA