Computing the exact number of periodic orbits for planar flows

Graça, Daniel; Zhong, Ning

doi:10.1090/tran/8644

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