On a group theoretic generalization of the Morse-Hedlund theorem
HTML articles powered by AMS MathViewer
- by Émilie Charlier, Svetlana Puzynina and Luca Q. Zamboni PDF
- Proc. Amer. Math. Soc. 145 (2017), 3381-3394 Request permission
Abstract:
In this paper we give a broad unified framework via group actions for constructing complexity functions of infinite words $x=x_0x_1x_2\cdots \in \mathbb {A}^{\mathbb {N}}$ with values in a finite set $\mathbb {A}.$ Factor complexity, Abelian complexity and cyclic complexity are all particular cases of this general construction. We consider infinite sequences of permutation groups $\omega = (G_n)_{n\geq 1}$ with each $G_n \subseteq S_n.$ Associated with every such sequence is a complexity function $p_{\omega ,x}:\mathbb {N} \rightarrow \mathbb {N}$ which counts, for each length $n,$ the number of equivalence classes of factors of $x$ of length $n$ under the action of $G_n$ on $\mathbb {A}^n$ given by $g* (u_1u_2\cdots u_n)=u_{g^{-1}(1)}u_{g^{-1}(2)}\cdots u_{g^{-1}(n)}.$ Each choice of $\omega =(G_n)_{n\geq 1}$ defines a unique complexity function which reflects a different combinatorial property of a given infinite word. For instance, an infinite word $x$ has bounded Abelian complexity if and only if $x$ is $k$-balanced for some positive integer $k,$ while bounded cyclic complexity is equivalent to $x$ being ultimately periodic. A celebrated result of G.A. Hedlund and M. Morse states that every aperiodic infinite word $x\in \mathbb {A}^{\mathbb {N}}$ contains at least $n+1$ distinct factors of each length $n.$ Moreover $x\in \mathbb {A}^{\mathbb {N}}$ has exactly $n+1$ distinct factors of each length $n$ if and only if $x$ is a Sturmian word, i.e., binary, aperiodic and balanced. We prove that this characterisation of aperiodicity and Sturmian words extends to this general framework.References
- A. Aberkane and S. Brlek, Suites de même complexité que celle de Thue–Morse, in Actes des Journées Montoises d’informatique théorique, Montpellier, France, 2002, pp. 85–89.
- Jean-Paul Allouche, The number of factors in a paperfolding sequence, Bull. Austral. Math. Soc. 46 (1992), no. 1, 23–32. MR 1170439, DOI 10.1017/S0004972700011655
- Jean-Paul Allouche, Michael Baake, Julien Cassaigne, and David Damanik, Palindrome complexity, Theoret. Comput. Sci. 292 (2003), no. 1, 9–31. Selected papers in honor of Jean Berstel. MR 1964623, DOI 10.1016/S0304-3975(01)00212-2
- Jean Berstel and Aldo de Luca, Sturmian words, Lyndon words and trees, Theoret. Comput. Sci. 178 (1997), no. 1-2, 171–203. MR 1453849, DOI 10.1016/S0304-3975(96)00101-6
- Valérie Berthé, Aldo de Luca, and Christophe Reutenauer, On an involution of Christoffel words and Sturmian morphisms, European J. Combin. 29 (2008), no. 2, 535–553. MR 2388389, DOI 10.1016/j.ejc.2007.03.001
- Jean-Pierre Borel and Christophe Reutenauer, On Christoffel classes, Theor. Inform. Appl. 40 (2006), no. 1, 15–27. MR 2197281, DOI 10.1051/ita:2005038
- Julien Cassaigne, Gabriele Fici, Marinella Sciortino, and Luca Q. Zamboni, Cyclic complexity of words, J. Combin. Theory Ser. A 145 (2017), 36–56. MR 3551645, DOI 10.1016/j.jcta.2016.07.002
- Ethan M. Coven and G. A. Hedlund, Sequences with minimal block growth, Math. Systems Theory 7 (1973), 138–153. MR 322838, DOI 10.1007/BF01762232
- Van Cyr and Bryna Kra, Complexity of short rectangles and periodicity. part A, European J. Combin. 52 (2016), no. part A, 146–173. MR 3425972, DOI 10.1016/j.ejc.2015.10.003
- Aldo de Luca, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci. 183 (1997), no. 1, 45–82. MR 1468450, DOI 10.1016/S0304-3975(96)00310-6
- Aldo de Luca and Filippo Mignosi, Some combinatorial properties of Sturmian words, Theoret. Comput. Sci. 136 (1994), no. 2, 361–385. MR 1311214, DOI 10.1016/0304-3975(94)00035-H
- Fabien Durand and Michel Rigo, Multidimensional extension of the Morse-Hedlund theorem, European J. Combin. 34 (2013), no. 2, 391–409. MR 2994406, DOI 10.1016/j.ejc.2012.08.003
- A. Ehrenfeucht, K. P. Lee, and G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. Comput. Sci. 1 (1975), no. 1, 59–75. MR 388861, DOI 10.1016/0304-3975(75)90012-2
- Michael Hoffman, An invariant of finite abelian groups, Amer. Math. Monthly 94 (1987), no. 7, 664–666. MR 935854, DOI 10.2307/2322221
- Oliver Jenkinson, Optimization and majorization of invariant measures, Electron. Res. Announc. Amer. Math. Soc. 13 (2007), 1–12. MR 2285761, DOI 10.1090/S1079-6762-07-00170-9
- Oliver Jenkinson, Balanced words and majorization, Discrete Math. Algorithms Appl. 1 (2009), no. 4, 463–483. MR 2725729, DOI 10.1142/S179383090900035X
- Vasso Anagnostopoulou and Oliver Jenkinson, Which beta-shifts have a largest invariant measure?, J. Lond. Math. Soc. (2) 79 (2009), no. 2, 445–464. MR 2496523, DOI 10.1112/jlms/jdn070
- Oliver Jenkinson and Luca Q. Zamboni, Characterisations of balanced words via orderings, Theoret. Comput. Sci. 310 (2004), no. 1-3, 247–271. MR 2020344, DOI 10.1016/S0304-3975(03)00397-9
- Teturo Kamae and Luca Zamboni, Sequence entropy and the maximal pattern complexity of infinite words, Ergodic Theory Dynam. Systems 22 (2002), no. 4, 1191–1199. MR 1926282, DOI 10.1017/S0143385702000585
- M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002. A collective work by Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desarmenien, Volker Diekert, Tero Harju, Juhani Karhumaki and Wojciech Plandowski; With a preface by Berstel and Perrin. MR 1905123, DOI 10.1017/CBO9781107326019
- Marston Morse and Gustav A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938), no. 4, 815–866. MR 1507944, DOI 10.2307/2371264
- Marston Morse and Gustav A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940), 1–42. MR 745, DOI 10.2307/2371431
- Igor Pak and Amanda Redlich, Long cycles in $abc$-permutations, Funct. Anal. Other Math. 2 (2008), no. 1, 87–92. MR 2466089, DOI 10.1007/s11853-008-0017-0
- Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni, Abelian complexity of minimal subshifts, J. Lond. Math. Soc. (2) 83 (2011), no. 1, 79–95. MR 2763945, DOI 10.1112/jlms/jdq063
- J. W. Sander and R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices, Theoret. Comput. Sci. 270 (2002), no. 1-2, 857–863. MR 1871099, DOI 10.1016/S0304-3975(01)00281-X
- A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat-Nat. Kl. 7 (1906), 1–22.
Additional Information
- Émilie Charlier
- Affiliation: Département de Mathématique, Université de Liège, 4000 Liège, Belgium
- Email: echarlier@ulg.ac.be
- Svetlana Puzynina
- Affiliation: LIP, ENS de Lyon, Université de Lyon, 69007 Lyon, France – and – Sobolev Institute of Mathematics, 630090 Novosibirsk, Russia
- MR Author ID: 733916
- Email: s.puzynina@gmail.com
- Luca Q. Zamboni
- Affiliation: Institut Camille Jordan, Université Lyon 1, 69622 Villeurbanne Cedex, France
- MR Author ID: 289645
- Email: lupastis@gmail.com
- Received by editor(s): November 11, 2015
- Received by editor(s) in revised form: August 29, 2016
- Published electronically: January 31, 2017
- Additional Notes: The second author was supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program Investissements d’Avenir (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR)
- Communicated by: Nimish Shah
- © Copyright 2017 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 145 (2017), 3381-3394
- MSC (2010): Primary 37B10
- DOI: https://doi.org/10.1090/proc/13589
- MathSciNet review: 3652792