Document Open Access Logo

A Universal Ordinary Differential Equation

Authors Olivier Bournez, Amaury Pouly



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.116.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Olivier Bournez
Amaury Pouly

Cite AsGet BibTex

Olivier Bournez and Amaury Pouly. A Universal Ordinary Differential Equation. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 116:1-116:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.116

Abstract

An astonishing fact was established by Lee A. Rubel (1981): there exists a fixed non-trivial fourth-order polynomial differential algebraic equation (DAE) such that for any positive continuous function phi on the reals, and for any positive continuous function epsilon(t), it has a C^infinity solution with | y(t) - phi(t) | < epsilon(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. In particular, the proofs heavily rely on the fact that constructed DAE does not have unique solutions for a given initial data. 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 phi 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 phi and epsilon(t) there exists some initial condition that yields a solution that is epsilon-close to phi 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 ithas a sufficient dimension).
Keywords
  • Ordinary Differential Equations
  • Universal Differential Equations
  • Analog Models of Computation
  • Continuous-Time Models of Computation
  • Computabilit

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Steven B. Bank. Some results on analytic and meromorphic solutions of algebraic differential equations. Advances in Mathematics, 15(1):41 - 62, 1975. URL: http://dx.doi.org/10.1016/0001-8708(75)90124-3.
  2. 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://dx.doi.org/10.1112/jlms/s1-12.48.250.
  3. Emile Borel. Mémoire sur les séries divergentes. Annales Scientifiques de l'Ecole Normale Supérieure, 16:9-136, 1899. Google Scholar
  4. Michael Boshernitzan. Universal formulae and universal differential equations. Annals of mathematics, 124(2):273-291, 1986. Google Scholar
  5. 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.
  6. 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.
  7. 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://dx.doi.org/10.4230/LIPIcs.ICALP.2016.109.
  8. Keith Briggs. Another universal differential equation. arXiv preprint math/0211142, 2002. Google Scholar
  9. V. Bush. The differential analyzer. A new machine for solving differential equations. J. Franklin Inst., 212:447-488, 1931. Google Scholar
  10. 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. Google Scholar
  11. Etienne Couturier and Nicolas Jacquet. Construction of a universal ordinary differential equation 𝒸^∞ of order 3. arXiv preprint arXiv:1610.09148, 2016. Google Scholar
  12. Richard J. Duffin. Rubel’s universal differential equation. Proceedings of the National Academy of Sciences, 78(8):4661-4662, 1981. Google Scholar
  13. 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. Google Scholar
  14. D. S. Graça, J. Buescu, and M. L. Campagnolo. Computational bounds on polynomial differential equations. Appl. Math. Comput., 215(4):1375-1385, 2009. Google Scholar
  15. D. S. Graça, M. L. Campagnolo, and J. Buescu. Computability with polynomial differential equations. Adv. Appl. Math., 40(3):330-349, 2008. Google Scholar
  16. 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. Google Scholar
  17. 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.
  18. M. B. Pour-El. Abstract computability and its relations to the general purpose analog computer. Trans. Amer. Math. Soc., 199:1-28, 1974. Google Scholar
  19. L. A. Rubel. A universal differential equation. Bulletin of the American Mathematical Society, 4(3):345-349, May 1981. Google Scholar
  20. C. E. Shannon. Mathematical theory of the differential analyser. Journal of Mathematics and Physics MIT, 20:337-354, 1941. Google Scholar
  21. T. Vijayaraghavan. Sur la croissance des fonctions définies par les équations différentielles. CR Acad. Sci. Paris, 194:827-829, 1932. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail