Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



On a group theoretic generalization of the Morse-Hedlund theorem

Authors: Émilie Charlier, Svetlana Puzynina and Luca Q. Zamboni
Journal: Proc. Amer. Math. Soc. 145 (2017), 3381-3394
MSC (2010): Primary 37B10
Published electronically: January 31, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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.
  • [2] Jean-Paul Allouche, The number of factors in a paperfolding sequence, Bull. Austral. Math. Soc. 46 (1992), no. 1, 23-32. MR 1170439,
  • [3] 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,
  • [4] Jean Berstel and Aldo de Luca, Sturmian words, Lyndon words and trees, Theoret. Comput. Sci. 178 (1997), no. 1-2, 171-203. MR 1453849,
  • [5] 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,
  • [6] Jean-Pierre Borel and Christophe Reutenauer, On Christoffel classes, Theor. Inform. Appl. 40 (2006), no. 1, 15-27. MR 2197281,
  • [7] 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,
  • [8] Ethan M. Coven and G. A. Hedlund, Sequences with minimal block growth, Math. Systems Theory 7 (1973), 138-153. MR 0322838
  • [9] Van Cyr and Bryna Kra, Complexity of short rectangles and periodicity. Part A, European J. Combin. 52 (2016), 146-173. MR 3425972,
  • [10] Aldo de Luca, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci. 183 (1997), no. 1, 45-82. MR 1468450,
  • [11] Aldo de Luca and Filippo Mignosi, Some combinatorial properties of Sturmian words, Theoret. Comput. Sci. 136 (1994), no. 2, 361-385. MR 1311214,
  • [12] Fabien Durand and Michel Rigo, Multidimensional extension of the Morse-Hedlund theorem, European J. Combin. 34 (2013), no. 2, 391-409. MR 2994406,
  • [13] A. Ehrenfeucht, K. P. Lee, and G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without interactions, Theor. Comput. Sci. 1 (1975), no. 1, 59-75. MR 0388861
  • [14] Michael Hoffman, An invariant of finite abelian groups, Amer. Math. Monthly 94 (1987), no. 7, 664-666. MR 935854,
  • [15] Oliver Jenkinson, Optimization and majorization of invariant measures, Electron. Res. Announc. Amer. Math. Soc. 13 (2007), 1-12. MR 2285761,
  • [16] Oliver Jenkinson, Balanced words and majorization, Discrete Math. Algorithms Appl. 1 (2009), no. 4, 463-483. MR 2725729,
  • [17] 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,
  • [18] Oliver Jenkinson and Luca Q. Zamboni, Characterisations of balanced words via orderings, Theoret. Comput. Sci. 310 (2004), no. 1-3, 247-271. MR 2020344,
  • [19] 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,
  • [20] M. Lothaire, Algebraic combinatorics on words, 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. Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002. MR 1905123
  • [21] Marston Morse and Gustav A. Hedlund, Symbolic dynamics, Amer. J. Math. 60 (1938), no. 4, 815-866. MR 1507944,
  • [22] Marston Morse and Gustav A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940), 1-42. MR 0000745
  • [23] Igor Pak and Amanda Redlich, Long cycles in $ abc$-permutations, Funct. Anal. Other Math. 2 (2008), no. 1, 87-92. MR 2466089,
  • [24] 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,
  • [25] 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,
  • [26] A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat-Nat. Kl. 7 (1906), 1-22.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 37B10

Retrieve articles in all journals with MSC (2010): 37B10

Additional Information

Émilie Charlier
Affiliation: Département de Mathématique, Université de Liège, 4000 Liège, Belgium

Svetlana Puzynina
Affiliation: LIP, ENS de Lyon, Université de Lyon, 69007 Lyon, France – and – Sobolev Institute of Mathematics, 630090 Novosibirsk, Russia

Luca Q. Zamboni
Affiliation: Institut Camille Jordan, Université Lyon 1, 69622 Villeurbanne Cedex, France

Keywords: Symbolic dynamics, complexity, Sturmian words, discrete interval exchange transformations
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
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society