# American Institute of Mathematical Sciences

• Previous Article
Diverging period and vanishing dissipation: Families of periodic sinks in the quasi-conservative case
• DCDS Home
• This Issue
• Next Article
On polyhedral control synthesis for dynamical discrete-time systems under uncertainties and state constraints
December 2018, 38(12): 6123-6148. doi: 10.3934/dcds.2018264

## Combinatorial approach to detection of fixed points, periodic orbits, and symbolic dynamics

 Yeshiva University, Department of Mathematical Sciences, New York, NY 10016, USA

* Corresponding author: Marian Gidea

Received  July 2017 Revised  January 2018 Published  September 2018

Fund Project: Research of M.G. and Y.S. was partially supported by NSF grant DMS-0635607, NSF grant DMS-1700154, and by the Alfred P. Sloan Foundation grant G-2016-7320

We present a combinatorial approach to rigorously show the existence of fixed points, periodic orbits, and symbolic dynamics in discrete-time dynamical systems, as well as to find numerical approximations of such objects. Our approach relies on the method of 'correctly aligned windows'. We subdivide 'windows' into cubical complexes, and we assign to the vertices of the cubes labels determined by the dynamics. In this way, we encode the information on the dynamics into combinatorial structure. We use a version of Sperner's Lemma to infer that, if the labeling satisfies certain conditions, then there exist fixed points/periodic orbits/orbits with prescribed itineraries. The method developed here does not require the computation of algebraic topology-type invariants, as only combinatorial information is needed; our arguments are elementary.

Citation: Marian Gidea, Yitzchak Shmalo. Combinatorial approach to detection of fixed points, periodic orbits, and symbolic dynamics. Discrete & Continuous Dynamical Systems - A, 2018, 38 (12) : 6123-6148. doi: 10.3934/dcds.2018264
##### References:
 [1] E. L. Allgower and K. Georg, Introduction to Numerical Continuation Methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2003. doi: 10.1137/1.9780898719154. [2] G. Arioli and H. Koch, Integration of dissipative partial differential equations: A case study, SIAM Journal on Applied Dynamical Systems, 9 (2010), 1119-1133. doi: 10.1137/10078298X. [3] R. Barrio, M. A. Martínez, S. Serrano and D. Wilczak, When chaos meets hyperchaos: 4D Rössler model, Physics Letters A, 379 (2015), 2300-2305. doi: 10.1016/j.physleta.2015.07.035. [4] B. M. Bekker and N. Yu. Netsvetaev, Generalized Sperner lemma and subdivisions into simplices of equal volume, Journal of Mathematical Sciences, 91 (1998), 3492-3498. doi: 10.1007/BF02434927. [5] K. Burns and M. Gidea, Differential Geometry and Topology: With a View to Dynamical Systems, Studies in Advanced Mathematics. Taylor & Francis, 2005. [6] M. J. Capiński and P. Roldán, Existence of a Center Manifold in a Practical Domain around L1 in the Restricted Three-Body Problem, SIAM Journal on Applied Dynamical Systems, 11 (2012), 285-318. doi: 10.1137/100810381. [7] M. J. Capiński and P. Zgliczyński, Cone conditions and covering relations for topologically normally hyperbolic invariant manifolds, Discrete and Continuous Dynamical Systems (DCDS-A), 30 (2011), 641-670. doi: 10.3934/dcds.2011.30.641. [8] C. Conley, Low energy transit orbits in the restricted three-body problem, SIAM Journal of Applied Mathematics, 16 (1968), 732-746. doi: 10.1137/0116060. [9] R. Easton, Orbit structure near trajectories biasymptotic to invariant tori, In R. Devaney and Z. Nitecki, editors, Classical Mechanics and Dynamical Systems, Marcel Dekker, 70 (1981), 55–67. [10] R. Easton and R. McGehee, Homoclinic phenomena for orbits doubly asymptotic to an invariant three-sphere, Indiana Univ. Math. J., 28 (1979), 211-240. doi: 10.1512/iumj.1979.28.28015. [11] Z. Galias and P. Zgliczyński, Computer assisted proof of chaos in the Lorenz equations, Physica D: Nonlinear Phenomena, 115 (1998), 165-188. doi: 10.1016/S0167-2789(97)00233-9. [12] M. Gidea, The Conley index and countable decompositions of invariant sets, Banach Center Publications, 47 (1999), 91-108. [13] T. Kaczynski, K. Mischaikow and M. Mrozek, Computing homology, Homology Homotopy Appl., 5 (2003), 233-256. doi: 10.4310/HHA.2003.v5.n2.a8. [14] A. Katok and B. Hasselblatt, Introduction to the Modern Theory of Dynamical Systems, Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511809187. [15] W. Krämer, Computer-assisted proofs and symbolic computations, Serdica Journal of Computing, 4 (2010), 73p-84p. [16] J. A. De Loera, E. Peterson and F. E. Su, A polytopal generalization of Sperner's lemma, Journal of Combinatorial Theory, Series A, 100 (2002), 1-26. doi: 10.1006/jcta.2002.3274. [17] A. Ruiz-Herrera and P. J. Torres, Periodic solutions and chaotic dynamics in forced impact oscillators, SIAM Journal on Applied Dynamical Systems, 12 (2013), 383-414. doi: 10.1137/120880902. [18] E. Sperner, Neuer beweis für die invarianz der dimensionszahl und des gebietes, Abh. Math. Sem. Univ. Hamburg, 6 (1928), 265-272. doi: 10.1007/BF02940617. [19] R. P. Stanley, Enumerative Combinatorics: Volume 1, Cambridge University Press, New York, NY, USA, 2nd edition, 2011. [20] D. Wilczak and P. Zgliczyński, Heteroclinic connections between periodic orbits in planar restricted circular three-body problem? a computer assisted proof, Communications in Mathematical Physics, 234 (2003), 37-75. doi: 10.1007/s00220-002-0709-0. [21] L. A Wolsey, Cubical Sperner lemmas as applications of generalized complementary pivoting, Journal of Combinatorial Theory, Series A, 23 (1977), 78-87. doi: 10.1016/0097-3165(77)90081-4. [22] X.-S. Yang, H. Li and Y. Huang, A planar topological horseshoe theory with applications to computer verifications of chaos, Journal of Physics A: Mathematical and General, 38 (2005), 4175-4185. doi: 10.1088/0305-4470/38/19/008. [23] P. Zgliczyński and M. Gidea, Covering relations for multidimensional dynamical systems, J. Differential Equations, 202 (2004), 32-58. doi: 10.1016/j.jde.2004.03.013. [24] P. Zgliczyński, Computer assisted proof of chaos in the Rössler equations and in the Hénon map, Nonlinearity, 10 (1997), 243. [25] G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995 doi: 10.1007/978-1-4613-8431-1.

show all references

##### References:
 [1] E. L. Allgower and K. Georg, Introduction to Numerical Continuation Methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2003. doi: 10.1137/1.9780898719154. [2] G. Arioli and H. Koch, Integration of dissipative partial differential equations: A case study, SIAM Journal on Applied Dynamical Systems, 9 (2010), 1119-1133. doi: 10.1137/10078298X. [3] R. Barrio, M. A. Martínez, S. Serrano and D. Wilczak, When chaos meets hyperchaos: 4D Rössler model, Physics Letters A, 379 (2015), 2300-2305. doi: 10.1016/j.physleta.2015.07.035. [4] B. M. Bekker and N. Yu. Netsvetaev, Generalized Sperner lemma and subdivisions into simplices of equal volume, Journal of Mathematical Sciences, 91 (1998), 3492-3498. doi: 10.1007/BF02434927. [5] K. Burns and M. Gidea, Differential Geometry and Topology: With a View to Dynamical Systems, Studies in Advanced Mathematics. Taylor & Francis, 2005. [6] M. J. Capiński and P. Roldán, Existence of a Center Manifold in a Practical Domain around L1 in the Restricted Three-Body Problem, SIAM Journal on Applied Dynamical Systems, 11 (2012), 285-318. doi: 10.1137/100810381. [7] M. J. Capiński and P. Zgliczyński, Cone conditions and covering relations for topologically normally hyperbolic invariant manifolds, Discrete and Continuous Dynamical Systems (DCDS-A), 30 (2011), 641-670. doi: 10.3934/dcds.2011.30.641. [8] C. Conley, Low energy transit orbits in the restricted three-body problem, SIAM Journal of Applied Mathematics, 16 (1968), 732-746. doi: 10.1137/0116060. [9] R. Easton, Orbit structure near trajectories biasymptotic to invariant tori, In R. Devaney and Z. Nitecki, editors, Classical Mechanics and Dynamical Systems, Marcel Dekker, 70 (1981), 55–67. [10] R. Easton and R. McGehee, Homoclinic phenomena for orbits doubly asymptotic to an invariant three-sphere, Indiana Univ. Math. J., 28 (1979), 211-240. doi: 10.1512/iumj.1979.28.28015. [11] Z. Galias and P. Zgliczyński, Computer assisted proof of chaos in the Lorenz equations, Physica D: Nonlinear Phenomena, 115 (1998), 165-188. doi: 10.1016/S0167-2789(97)00233-9. [12] M. Gidea, The Conley index and countable decompositions of invariant sets, Banach Center Publications, 47 (1999), 91-108. [13] T. Kaczynski, K. Mischaikow and M. Mrozek, Computing homology, Homology Homotopy Appl., 5 (2003), 233-256. doi: 10.4310/HHA.2003.v5.n2.a8. [14] A. Katok and B. Hasselblatt, Introduction to the Modern Theory of Dynamical Systems, Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511809187. [15] W. Krämer, Computer-assisted proofs and symbolic computations, Serdica Journal of Computing, 4 (2010), 73p-84p. [16] J. A. De Loera, E. Peterson and F. E. Su, A polytopal generalization of Sperner's lemma, Journal of Combinatorial Theory, Series A, 100 (2002), 1-26. doi: 10.1006/jcta.2002.3274. [17] A. Ruiz-Herrera and P. J. Torres, Periodic solutions and chaotic dynamics in forced impact oscillators, SIAM Journal on Applied Dynamical Systems, 12 (2013), 383-414. doi: 10.1137/120880902. [18] E. Sperner, Neuer beweis für die invarianz der dimensionszahl und des gebietes, Abh. Math. Sem. Univ. Hamburg, 6 (1928), 265-272. doi: 10.1007/BF02940617. [19] R. P. Stanley, Enumerative Combinatorics: Volume 1, Cambridge University Press, New York, NY, USA, 2nd edition, 2011. [20] D. Wilczak and P. Zgliczyński, Heteroclinic connections between periodic orbits in planar restricted circular three-body problem? a computer assisted proof, Communications in Mathematical Physics, 234 (2003), 37-75. doi: 10.1007/s00220-002-0709-0. [21] L. A Wolsey, Cubical Sperner lemmas as applications of generalized complementary pivoting, Journal of Combinatorial Theory, Series A, 23 (1977), 78-87. doi: 10.1016/0097-3165(77)90081-4. [22] X.-S. Yang, H. Li and Y. Huang, A planar topological horseshoe theory with applications to computer verifications of chaos, Journal of Physics A: Mathematical and General, 38 (2005), 4175-4185. doi: 10.1088/0305-4470/38/19/008. [23] P. Zgliczyński and M. Gidea, Covering relations for multidimensional dynamical systems, J. Differential Equations, 202 (2004), 32-58. doi: 10.1016/j.jde.2004.03.013. [24] P. Zgliczyński, Computer assisted proof of chaos in the Rössler equations and in the Hénon map, Nonlinearity, 10 (1997), 243. [25] G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995 doi: 10.1007/978-1-4613-8431-1.
A sequence of correctly aligned windows. The first window $D_1$ in the sequence has marked its exit and entry set; $D_1$ is correctly aligned with $D_2$ under $f$, and $D_2$ is correctly aligned with $D_3$ under $f$
Sperner labeling of a simplicial decomposition, and a completely labeled triangle in the simplicial decomposition
Examples of simplicial decomposition of polytopes and of labelings; refer to Example 1
A 2D window correctly aligned with itself under some map, and the corresponding labeling of $[0, 1]^2$ according to Condition O
Coarse decomposition of $C$ and transformation into a polytope $\widetilde C$
A 3D window correctly aligned with itself under some map, and a cubical decomposition satisfying Condition P; refer to Example 3
A periodic sequence of correctly aligned windows $D_1, D_2, D_3$, where $D_1$ is correctly aligned with $D_2$, $D_2$ is correctly aligned with $D_3$, and $D_3$ is correctly aligned with $D_1$
Top: The square $D_0$ and its image under $f^7(D_0)$, showing that $D_0$ is correctly aligned with itself under $f^7$ (top). Middle: $D_0$ is sub-divided into smaller squares of side $10^{-7}$, whose vertices are labeled. Zooming in, a completely labeled sub-square $D_1$ is shown. Bottom: The square $D_1$ is sub-divided into smaller squares of side $10^{-10}$, whose vertices are labeled. Zooming in, a completely labeled sub-square $D_2$ is shown
Approximate period-$7$ orbit
 [1] Panos K. Palamides, Alex P. Palamides. Singular boundary value problems, via Sperner's lemma. Conference Publications, 2007, 2007 (Special) : 814-823. doi: 10.3934/proc.2007.2007.814 [2] Juan Campos, Rafael Ortega. Location of fixed points and periodic solutions in the plane. Discrete & Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 517-523. doi: 10.3934/dcdsb.2008.9.517 [3] Anna Cima, Armengol Gasull, Víctor Mañosa. Parrondo's dynamic paradox for the stability of non-hyperbolic fixed points. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 889-904. doi: 10.3934/dcds.2018038 [4] Raoul-Martin Memmesheimer, Marc Timme. Stable and unstable periodic orbits in complex networks of spiking neurons with delays. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1555-1588. doi: 10.3934/dcds.2010.28.1555 [5] Paula Kemp. Fixed points and complete lattices. Conference Publications, 2007, 2007 (Special) : 568-572. doi: 10.3934/proc.2007.2007.568 [6] John Franks, Michael Handel, Kamlesh Parwani. Fixed points of Abelian actions. Journal of Modern Dynamics, 2007, 1 (3) : 443-464. doi: 10.3934/jmd.2007.1.443 [7] Viktor L. Ginzburg, Başak Z. Gürel. On the generic existence of periodic orbits in Hamiltonian dynamics. Journal of Modern Dynamics, 2009, 3 (4) : 595-610. doi: 10.3934/jmd.2009.3.595 [8] Dario Bambusi, Simone Paleari. Families of periodic orbits for some PDE’s in higher dimensions. Communications on Pure & Applied Analysis, 2002, 1 (2) : 269-279. doi: 10.3934/cpaa.2002.1.269 [9] Steven T. Piantadosi. Symbolic dynamics on free groups. Discrete & Continuous Dynamical Systems - A, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725 [10] Alexey A. Petrov, Sergei Yu. Pilyugin. Shadowing near nonhyperbolic fixed points. Discrete & Continuous Dynamical Systems - A, 2014, 34 (9) : 3761-3772. doi: 10.3934/dcds.2014.34.3761 [11] Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. [12] Jim Wiseman. Symbolic dynamics from signed matrices. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 621-638. doi: 10.3934/dcds.2004.11.621 [13] George Osipenko, Stephen Campbell. Applied symbolic dynamics: attractors and filtrations. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 43-60. doi: 10.3934/dcds.1999.5.43 [14] Michael Hochman. A note on universality in multidimensional symbolic dynamics. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 301-314. doi: 10.3934/dcdss.2009.2.301 [15] Paolo Perfetti. An infinite-dimensional extension of a Poincaré's result concerning the continuation of periodic orbits. Discrete & Continuous Dynamical Systems - A, 1997, 3 (3) : 401-418. doi: 10.3934/dcds.1997.3.401 [16] Chao Wang, Dingbian Qian, Qihuai Liu. Impact oscillators of Hill's type with indefinite weight: Periodic and chaotic dynamics. Discrete & Continuous Dynamical Systems - A, 2016, 36 (4) : 2305-2328. doi: 10.3934/dcds.2016.36.2305 [17] K. H. Kim, F. W. Roush and J. B. Wagoner. Inert actions on periodic points. Electronic Research Announcements, 1997, 3: 55-62. [18] Charles Pugh, Michael Shub. Periodic points on the $2$-sphere. Discrete & Continuous Dynamical Systems - A, 2014, 34 (3) : 1171-1182. doi: 10.3934/dcds.2014.34.1171 [19] Jose S. Cánovas, Tönu Puu, Manuel Ruiz Marín. Detecting chaos in a duopoly model via symbolic dynamics. Discrete & Continuous Dynamical Systems - B, 2010, 13 (2) : 269-278. doi: 10.3934/dcdsb.2010.13.269 [20] Nicola Soave, Susanna Terracini. Symbolic dynamics for the $N$-centre problem at negative energies. Discrete & Continuous Dynamical Systems - A, 2012, 32 (9) : 3245-3301. doi: 10.3934/dcds.2012.32.3245

2017 Impact Factor: 1.179