Symbolic dynamics and representations

Berthé, Valérie

Journées Nationales de Calcul Formel. 16 – 20 Janvier 2017, Les cours du CIRM, no. 1 (2017), Exposé no. 1, 16 p.

The object of study of symbolic dynamics are discrete dynamical systems made of infinite sequences of symbols, with the shift acting on them. They come as codings of trajectories of points in a dynamical system according to a given partition. They are used as discretization tools for analyzing such trajectories, but they also occur in a natural way in arithmetics for instance. We first will recall basic definitions concerning symbolic dynamics and illustrate them with transformations like beta-numeration and continued fractions. We then focus on orbits that are relevant in computer science, namely finite and periodic ones, together by alluding to numerical issues for the computation of orbits.

[1] B. Adamczewski, Balances for fixed points of primitive substitutions, Theoret. Comput. Sci. 307 (2003), 47–75. | DOI | MR | Zbl

[2] B. Adamczewski, Symbolic discrepancy and self-similar dynamics, Ann. Inst. Fourier (Grenoble) 54 (2004), 2201–2234. | DOI | MR | Zbl

[3] J.-P. Allouche and J. O. Shallit, Automatic sequences: Theory and Applications, Cambridge University Press, 2002. | DOI

[4] M. Baake, U. Grimm, Aperiodic order. Vol. 1. A mathematical invitation, Encyclopedia of Mathematics and its Applications 149, Cambridge University Press, 2013. | DOI

[5] V. Baladi, B. Vallée. Euclidean algorithms are Gaussian, J. Number Theory 110 (2005), 331–386. | DOI | MR | Zbl

[6] L. Barreira, I. Godofredo, Partial quotients of continued fractions and $\beta$-expansions, Nonlinearity 21 (2008), 2211–2219. | DOI | MR | Zbl

[7] M.-P. Béal and D. Perrin, Symbolic dynamics and finite automata, in Handbook of formal languages, Vol. 2, Springer, Berlin, 1997. | DOI

[8] T. Bedford, M. Keane and C. Series (eds), Ergodic theory, symbolic dynamics, and hyperbolic spaces, The Clarendon Press Oxford University Press, New York, 1991.

[9] V. Berthé, Sequences of low complexity: automatic and Sturmian sequences, in Topics in symbolic dynamics and applications, F. Blanchard, A. Nogueira and A. Maas (eds), London Mathematical Society Lecture Note Series vol. 279, Cambridge University Press, 2000. | DOI | Zbl

[10] V. Berthé, Numeration and discrete dynamical systems, Computing 94 (2012), 369–387. | DOI | MR | Zbl

[11] V. Berthé, Fréquences des facteurs des suites sturmiennes, Theoret. Comput. Sci. 165 (1996), 295–309. | DOI | Zbl

[12] V. Berthé, V. Delecroix, Beyond substitutive dynamical systems: $S$-adic expansions, RIMS Lecture note ‘Kokyuroku Bessatu’ B46 (2014), 81–123. | Zbl

[13] V. Berthé, H. Nakada, On continued fraction expansions in positive characteristic: equivalence relations and some metric properties, Expositiones Mathematicae18 (2000), 257–284. | MR | Zbl

[14] V. Berthé, M. Rigo (Eds), Combinatorics, Automata and Number Theory, Encyclopedia Math. Appl. 135, Cambridge Univ. Press, Cambridge, 2010. | DOI | Zbl

[15] V. Berthé, M. Rigo (Eds), Combinatorics, Words and Symbolic dynamics, Encyclopedia Math. Appl. 159, Cambridge University Press (2016). | DOI | Zbl

[16] V. Berthé, L. Lhote, B. Vallée, A probabilistic analysis of the plain multiple gcd algorithm, Journal of Symbolic Computation 74 (2016), 425–474. | DOI | MR | Zbl

[17] V. Berthé, L. Lhote, B. Vallée, Analysis of the Brun Gcd Algorithm, ISSAC 2016, ACM 2016, 87-94. | DOI | Zbl

[18] P. Billingsley, Ergodic theory and information, John Wiley & Sons Inc., New York, 1965. | DOI | Zbl

[19] F. Blanchard, A. Nogueira and A. Maas (eds), Topics in symbolic dynamics and applications, Cambridge University Press, 2000. London Mathematical Society Lecture Note Series, Vol. 279. | DOI | MR

[20] B. Bollobás, Random graphs, 2nd edn (Cambridge Studies in Advanced Mathematics), Cambridge University Press, 2001. | Zbl

[21] W. Bosma, K. Dajani, and C. Kraaikamp, Entropy quotients and correct digits in number-theoretic expansions, Dynamics & stochastics, IMS Lecture Notes Monogr. Ser., 48 (2006), 176–188. | DOI | MR | Zbl

[22] V. E. Brimkov, D. Coeurjolly, and R. Klette, Digital planarity - a review, Discrete Applied Mathematics 155 (2007), 468–495. | DOI | MR | Zbl

[23] J. Buzzi, https://jbuzzi.wordpress.com/2013/10/18/les-surfaces-a-courbures-opposees-et-leurs-lignes-geodesiques-jacques-hadamard-1898/.

[24] G. H. Choe, Computational ergodic theory, Algorithms and Computation in Mathematics, 13, Springer-Verlag, Berlin, 2005. | DOI | MR | Zbl

[25] R. M. Corless, Continued fractions and chaos, Amer. Math. Monthly 99 (1992), 203–215. | DOI | MR | Zbl

[26] R. M. Corless, What good are numerical simulations of chaotic dynamical systems?, Comput. Math. Appl. 28 (1994), 107–121. | DOI | MR | Zbl

[27] R. M. Corless, G. W. Frank, and J. G. Monroe, Chaos and continued fractions, Phys. D 46 (1990), 241–253. | DOI | MR | Zbl

[28] I. P. Cornfeld, S. V. Fomin and Y. G. Sinaĭ, Ergodic theory, Springer-Verlag, New York, 1982. | Zbl

[29] E. M. Coven and G. A. Hedlund, Sequences with minimal block growth, Math. Systems Theory 7 (1973), 138–153. | DOI | MR | Zbl

[30] K. Dajani, A. Fieldsteel, Equipartition of interval partitions and an application to number theory, Proc. Amer. Math. Soc. 129 (2001), 3453–3460 | DOI | MR | Zbl

[31] K. Dajani and C. Kraaikamp. Ergodic Theory of Numbers, The Math. Association of America, 2002. | DOI | Zbl

[32] R. L. Devaney, An introduction to chaotic dynamical systems, Addison-Wesley Studies in Nonlinearity, Redwood City, CA, 1989. | DOI | Zbl

[33] Th. Fernique, Generation and recognition of digital planes using multi-dimensional continued fractions, Pattern Recognition 42 (2009), 2229–2238. | DOI | Zbl

[34] P. Flajolet, A. M. Odlyzko, Random Mapping Statistics, EUROCRYPT’89, Lecture Notes Comput. Sci. 434 (1990), 329–354. | DOI | MR | Zbl

[35] P. Flajolet, B. Vallée, Continued fractions, comparison algorithms, and fine structure constants, CMS Conf. Proc., 27, 53–82, Amer. Math. Soc., Providence, RI, 2000. | MR | Zbl

[36] P. Flajolet, B. Vallée, Continued fraction algorithms, functional operators, and structure constants, Theoret. Comput. Sci., 194 (1998), 1–34. | DOI | MR | Zbl

[37] N. Pytheas Fogg. Substitutions in dynamics, arithmetics and combinatorics, volume 1794 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. | DOI | MR | Zbl

[38] Ch. Frougny. Numeration systems, volume 90 of Encyclopedia of Mathematics and its Applications, chapter 7, pages 230–268. Cambridge University Press, 2002. | DOI

[39] Ch. Frougny, J. Sakarovitch, Number representation and finite automata, volume 135 of Encyclopedia of Mathematics and its Applications, chapter 2, Cambridge University Press, 2010, 34–107. | DOI | Zbl

[40] P. Góra, A. Boyarsky, Why computers like Lebesgue measure, Comput. Math. Appl. 16 (1988), 321–329. | DOI | MR | Zbl

[41] P. Góra, Paweł, A. Boyarsky, I. Md. Shafiqul and W. Bahsoun, Absolutely continuous invariant measures that cannot be observed experimentally, SIAM J. Appl. Dyn. Syst., 5 (2006), 84–90. | DOI | MR | Zbl

[42] P.-A. Guihéneuf, Gare aux erreurs d’arrondi! http://images.math.cnrs.fr/Gare-aux-erreurs-d-arrondi.html

[43] P.-A. Guihéneuf, Dynamical properties of spatial discretizations of a generic homeomorphism, Ergodic Theory Dynam. Systems 35 (2015), 1474–1523. | DOI | MR | Zbl

[44] J. Hadamard, Les surfaces à courbures opposées et leurs lignes géodésiques, Journal de Mathématiques pures et appliquées $5$ème série, tome $4$ (1898), 27–74. | Zbl

[45] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford Science Publications, 1979. | Zbl

[46] A. Katok and B. Hasselblatt, Introduction to the modern theory of dynamical systems, Cambridge University Press, Cambridge, 1995. | DOI | Zbl

[47] H. Kesten On a conjecture of Erdös and Szüsz related to uniform distribution mod $1$, Acta Arith. 12 (1966), 193–212. | DOI | Zbl

[48] J. Kellendonk, D. Lenz, J. Savinien, Mathematics of aperiodic order, Progr. Math., 309, Birkhäuser/Springer, Basel, 2015. | DOI | Zbl

[49] A. Y. Khintchine, Continued fractions, Translated by Peter Wynn, P. Noordhoff Ltd., Groningen, 1963. | DOI | Zbl

[50] B. P. Kitchens, Symbolic dynamics. One-sided, two-sided and countable state Markov shifts, Universitext. Springer-Verlag, Berlin, 1998. | Zbl

[51] D. E Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, Addison-Wesley, 1998. | Zbl

[52] R. Klette and A. Rosenfeld. Digital straightness-a review. Discrete Applied Mathematics 139 (2004), 197–230. | DOI | MR | Zbl

[53] B. Li, J. Wu, Beta-expansion and continued fraction expansion over formal Laurent series, Finite Fields Appl. 14 (2008), 635–647. | DOI | MR | Zbl

[54] B. Li, J. Wu, Beta-expansion and continued fraction expansion, J. Math. Anal. Appl.339 (2008), 1322–1331. | DOI | MR | Zbl

[55] D. Lind, B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. | DOI | Zbl

[56] G. Lochs, Vergleich der Genauigkeit von Dezimalbruch und Kettenbruch, Abh. Math. Sem. Univ. Hamburg 27 (1964), 142–144. | DOI | MR | Zbl

[57] G. Lochs, Die ersten $968$ Kettenbruchnenner von $\pi$, Monatsh. Math. 67 (1963), 311–316. | DOI | MR | Zbl

[58] L. Lhote, B. Vallée, Gaussian laws for the main parameters of the Euclid algorithms, Algorithmica, 50 (2008), 497–554. | DOI | MR | Zbl

[59] M. Lothaire, Combinatorics on words, Cambridge University Press, Cambridge, 1997. Second ed. | DOI | Zbl

[60] M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2002. | DOI | Zbl

[61] T. Miernowski, Discrétisations des homéomorphismes du cercle, Ergodic Theory Dynam. Systems 26 (2006), 1867–1903. | DOI | Zbl

[62] H. M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc. 22 (1921), 84–100. | DOI | MR | Zbl

[63] M. Morse, G. A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938), 815–866. | DOI | MR | Zbl

[64] M. Morse, G. A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940), 1–42. | DOI | MR | Zbl

[65] H. Niederreiter, Continued fractions for formal power series, pseudorandom numbers, and linear complexity, Contributions to general algebra, 5 , 221–233, Hölder-Pichler-Tempsky, Vienna (1987).

[66] H. Niederreiter, Low-discrepancy sequences and non-Archimedean Diophantine approximations, Studia. Sci. Math. Hungar. 30 (1995), 111–122. | MR | Zbl

[67] H. Niederreiter, Sequences with almost perfect linear complexity profile, in “Advances in Cryptology: Proc. EUROCRYPT’87” , Springer, Berlin (1988), 37–51 | DOI | Zbl

[68] W. Parry, and M. Pollicott, Zeta functions and the periodic orbit structure of hyperbolic dynamics, Astérisque 187–188 (1990). | Numdam | Zbl

[69] K. Petersen, Ergodic theory, Cambridge University Press, Cambridge, 1989. | Zbl

[70] S. Y. Pilyugin, Shadowing in dynamical systems, Lecture Notes in Mathematics 1706, Berlin, Springer-Verlag, 1999. | DOI | MR | Zbl

[71] M. Pollicott, Distribution of closed geodesics on the modular surface and quadratic irrationals, Bull. Soc. Math. France 114 (1986), 431–446. | DOI | MR | Zbl

[72] M. Queffélec, Substitution Dynamical Systems. Spectral Analysis, Lecture Notes in Math. 1294, Springer-Verlag (2010). | DOI | MR | Zbl

[73] A. Rényi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar.8 (1957), 477–493. | DOI | MR | Zbl

[74] N. Sidorov, Arithmetic dynamics, in S. Bezuglyi et al., editor, Topics in dynamics and ergodic theory, volume 310 of Lond. Math. Soc. Lect. Note Ser., pages 145–189. Cambridge University Press, 2003. | DOI | MR | Zbl

[75] A. Thue, Selected mathematical papers, Universitetsforlaget, Oslo, 1977. | Zbl

[76] B. Vallée, Euclidean dynamics, Discrete Contin. Dyn. Syst. 15 (2006), 281–352. | DOI | MR | Zbl

[77] I. Fagnot, L. Vuillon, Generalized balances in Sturmian words, Discrete Appl. Math. 121 (2002), 83–101. | DOI | MR | Zbl

[78] P. Walters, An introduction to ergodic theory, Springer-Verlag, New York, 1982. | DOI | Zbl