Article Contents
Article Contents

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

• * Corresponding author: Marian Gidea
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.

Mathematics Subject Classification: Primary: 37C25, 37B10, 37C50; Secondary: 55M20, 05A99.

 Citation:

• Figure 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$

Figure 2.  Sperner labeling of a simplicial decomposition, and a completely labeled triangle in the simplicial decomposition

Figure 3.  Examples of simplicial decomposition of polytopes and of labelings; refer to Example 1

Figure 4.  A 2D window correctly aligned with itself under some map, and the corresponding labeling of $[0, 1]^2$ according to Condition O

Figure 5.  Coarse decomposition of $C$ and transformation into a polytope $\widetilde C$

Figure 6.  A 3D window correctly aligned with itself under some map, and a cubical decomposition satisfying Condition P; refer to Example 3

Figure 7.  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$

Figure 8.  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

Figure 9.  Approximate period-$7$ orbit

•  [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.

Figures(9)

• on this site

/