## Computing the exact number of periodic orbits for planar flows

HTML articles powered by AMS MathViewer

- by Daniel S. Graça and Ning Zhong PDF
- Trans. Amer. Math. Soc.
**375**(2022), 5491-5538 Request permission

## Abstract:

In this paper, we consider the problem of determining the*exact*number of periodic orbits for polynomial planar flows. This problem is a variant of Hilbert’s 16th problem. Using a natural definition of computability, we show that the problem is noncomputable on the one hand and, on the other hand, computable uniformly on the set of all structurally stable systems defined on the unit disk. We also prove that there is a family of polynomial planar systems which does not have a computable sharp upper bound on the number of its periodic orbits.

## References

- Kendall E. Atkinson,
*An introduction to numerical analysis*, 2nd ed., John Wiley & Sons, Inc., New York, 1989. MR**1007135** - S. Banach and S. Mazur,
*Sur les fonctions calculables*, Ann. Soc. Pol. Math.**16**(1937). - Garrett Birkhoff and Gian-Carlo Rota,
*Ordinary differential equations*, 4th ed., John Wiley & Sons, Inc., New York, 1989. MR**972977** - Olivier Bournez, Daniel S. Graça, and Amaury Pouly,
*On the complexity of solving initial value problems*, ISSAC 2012—Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2012, pp. 115–121. MR**3206294**, DOI 10.1145/2442829.2442849 - Vasco Brattka, Peter Hertling, and Klaus Weihrauch,
*A tutorial on computable analysis*, New computational paradigms, Springer, New York, 2008, pp. 425–491. MR**2762094**, DOI 10.1007/978-0-387-68546-5_{1}8 - Mark Braverman,
*Hyperbolic Julia sets are poly-time computable*, Proceedings of the 6th Workshop on Computability and Complexity in Analysis (CCA 2004), Electron. Notes Theor. Comput. Sci., vol. 120, Elsevier Sci. B. V., Amsterdam, 2005, pp. 17–30. MR**2207122**, DOI 10.1016/j.entcs.2004.06.031 - M. Braverman and M. Yampolsky,
*Non-computable Julia sets*, J. Amer. Math. Soc.**19**(2006), no. 3, 551–578. MR**2220099**, DOI 10.1090/S0894-0347-05-00516-3 - M. Braverman and M. Yampolsky,
*Computability of Julia sets*, Springer, 2009. - Pieter Collins and Daniel S. Graça,
*Effective computability of solutions of ordinary differential equations: the thousand monkeys approach*, Proceedings of the Fifth International Conference on Computability and Complexity in Analysis (CCA 2008), Electron. Notes Theor. Comput. Sci., vol. 221, Elsevier Sci. B. V., Amsterdam, 2008, pp. 103–114. MR**2873350**, DOI 10.1016/j.entcs.2008.12.010 - Pieter Collins and Daniel S. Graça,
*Effective computability of solutions of differential inclusions: the ten thousand monkeys approach*, J.UCS**15**(2009), no. 6, 1162–1185. MR**2534356** - Michael Dellnitz, Gary Froyland, and Oliver Junge,
*The algorithms behind GAIO-set oriented numerical methods for dynamical systems*, Ergodic theory, analysis, and efficient simulation of dynamical systems, Springer, Berlin, 2001, pp. 145–174, 805–807. MR**1850305** - D. S. Graça, C. Rojas, and N. Zhong,
*Computing geometric Lorenz attractors with arbitrary precision*, Trans. Amer. Math. Soc.**370**(2018), no. 4, 2955–2970. MR**3748590**, DOI 10.1090/tran/7228 - D. S. Graça and N. Zhong,
*Computability of differential equations*, Handbook of Computability and Complexity in Analysis (V. Brattka and P. Hertling, eds.), Springer International Publishing, Cham, 2021, pp. 71–99. - D. S. Graça, N. Zhong, and J. Buescu,
*Computability, noncomputability and undecidability of maximal intervals of IVPs*, Trans. Amer. Math. Soc.**361**(2009), no. 6, 2913–2927. MR**2485412**, DOI 10.1090/S0002-9947-09-04929-0 - Daniel S. Graça and Ning Zhong,
*The set of hyperbolic equilibria and of invertible zeros on the unit ball is computable*, Theoret. Comput. Sci.**895**(2021), 48–54. MR**4337874**, DOI 10.1016/j.tcs.2021.09.028 - Daniel S. Graça, Ning Zhong, and H. S. Dumas,
*The connection between computability of a nonlinear problem and its linearization: The Hartman-Grobman theorem revisited*, Theoret. Comput. Sci.**457**(2012), 101–110. MR**2961202**, DOI 10.1016/j.tcs.2012.07.013 - John Guckenheimer and Philip Holmes,
*Nonlinear oscillations, dynamical systems, and bifurcations of vector fields*, Applied Mathematical Sciences, vol. 42, Springer-Verlag, New York, 1983. MR**709768**, DOI 10.1007/978-1-4612-1140-2 - John H. Hubbard and Beverly H. West,
*Differential equations: a dynamical systems approach*, Texts in Applied Mathematics, vol. 18, Springer-Verlag, New York, 1995. Higher-dimensional systems. MR**1335451**, DOI 10.1007/978-1-4612-4192-8 - Yu. Ilyashenko,
*Centennial history of Hilbert’s 16th problem*, Bull. Amer. Math. Soc. (N.S.)**39**(2002), no. 3, 301–354. MR**1898209**, DOI 10.1090/S0273-0979-02-00946-1 - Akitoshi Kawamura,
*Lipschitz continuous ordinary differential equations are polynomial-space complete*, Comput. Complexity**19**(2010), no. 2, 305–332. MR**2652508**, DOI 10.1007/s00037-010-0286-0 - Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick, and Martin Ziegler,
*Computational complexity of smooth differential equations*, Log. Methods Comput. Sci.**10**(2014), no. 1, 1:6, 15. MR**3197099**, DOI 10.2168/LMCS-10(1:6)2014 - Ker-I Ko,
*Complexity theory of real functions*, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1991. MR**1137517**, DOI 10.1007/978-1-4684-6802-1 - Yuri V. Matiyasevich,
*Hilbert’s tenth problem*, Foundations of Computing Series, MIT Press, Cambridge, MA, 1993. Translated from the 1993 Russian original by the author; With a foreword by Martin Davis. MR**1244324** - S. Mazur,
*Computable analysis*, Rozprawy Mat.**33**(1963), 110. MR**153553** - Webb Miller,
*Recursive function theory and numerical analysis*, J. Comput. System Sci.**4**(1970), 465–472. MR**269503**, DOI 10.1016/S0022-0000(70)80043-5 - N. Müller and B. Moiske,
*Solving initial value problems in polynomial time*, Proceedings of the 22nd JAIIO - PANEL ’93, Part 2, 1993, pp. 283–293. - N. Th. Müller,
*Uniform computational complexity of Taylor series*, Automata, languages and programming (Karlsruhe, 1987) Lecture Notes in Comput. Sci., vol. 267, Springer, Berlin, 1987, pp. 435–444. MR**912727**, DOI 10.1007/3-540-18088-5_{3}7 - James R. Munkres,
*Topology*, Prentice Hall, Inc., Upper Saddle River, NJ, 2000. Second edition of [ MR0464128]. MR**3728284** - Piergiorgio Odifreddi,
*Classical recursion theory*, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR**982269** - M. M. Peixoto,
*On structural stability*, Ann. of Math. (2)**69**(1959), 199–222. MR**101951**, DOI 10.2307/1970100 - M. Peixoto,
*Structural stability on two-dimensional manifolds*, Topology**1**(1962), 101–121. - Lawrence Perko,
*Differential equations and dynamical systems*, 3rd ed., Texts in Applied Mathematics, vol. 7, Springer-Verlag, New York, 2001. MR**1801796**, DOI 10.1007/978-1-4613-0003-8 - Amaury Pouly and Daniel S. Graça,
*Computational complexity of solving polynomial differential equations over unbounded domains*, Theoret. Comput. Sci.**626**(2016), 67–82. MR**3476576**, DOI 10.1016/j.tcs.2016.02.002 - Marian B. Pour-El and J. Ian Richards,
*Computability in analysis and physics*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989. MR**1005942**, DOI 10.1007/978-3-662-21717-7 - Robert Rettinger,
*A fast algorithm for Julia sets of hyperbolic rational functions*, Proceedings of the 6th Workshop on Computability and Complexity in Analysis (CCA 2004), Electron. Notes Theor. Comput. Sci., vol. 120, Elsevier Sci. B. V., Amsterdam, 2005, pp. 145–157. MR**2207132**, DOI 10.1016/j.entcs.2004.06.041 - M. Sipser,
*Introduction to the theory of computation*, 3rd ed., Cengage Learning, 2012. - Warwick Tucker,
*Computing accurate Poincaré maps*, Phys. D**171**(2002), no. 3, 127–137. MR**1931138**, DOI 10.1016/S0167-2789(02)00603-6 - A. M. Turing,
*On Computable Numbers, with an Application to the Entscheidungsproblem*, Proc. London Math. Soc. (2)**42**(1936), no. 3, 230–265. MR**1577030**, DOI 10.1112/plms/s2-42.1.230 - Klaus Weihrauch,
*Computable analysis*, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR**1795407**, DOI 10.1007/978-3-642-56999-9 - Klaus Weihrauch and Ning Zhong,
*Computable analysis of the abstract Cauchy problem in a Banach space and its applications. I*, MLQ Math. Log. Q.**53**(2007), no. 4-5, 511–531. MR**2351947**, DOI 10.1002/malq.200710015 - Martin Ziegler and Vasco Brattka,
*Computability in linear algebra*, Theoret. Comput. Sci.**326**(2004), no. 1-3, 187–211. MR**2094248**, DOI 10.1016/j.tcs.2004.06.022

## Additional Information

**Daniel S. Graça**- Affiliation: Universidade do Algarve, C. Gambelas, 8005-139 Faro, Portugal, and Instituto de Telecomunicações, Portugal
- ORCID: 0000-0002-0330-833X
- Email: dgraca@ualg.pt
**Ning Zhong**- Affiliation: DMS, University of Cincinnati, Cincinnati, Ohio 45221-0025
- MR Author ID: 232808
- Email: zhongn@ucmail.uc.edu
- Received by editor(s): February 26, 2021
- Received by editor(s) in revised form: November 25, 2021, and December 11, 2021
- Published electronically: May 26, 2022
- Additional Notes: The first author was partially funded by FCT/MCTES through national funds and when applicable co-funded EU funds under the project UIDB/50008/2020. This project had received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 731143
- © Copyright 2022 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**375**(2022), 5491-5538 - MSC (2020): Primary 03D78; Secondary 34C07
- DOI: https://doi.org/10.1090/tran/8644
- MathSciNet review: 4469227