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: |
Figure 8.
Top: The square
[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.![]() ![]() ![]() |