Critical exponent of a word

In mathematics and computer science, the critical exponent of an infinite sequence of symbols from an alphabet describes how many times a subsequence can be repeated.

If w is an infinite word over the alphabet A and x is a finite word over A, then x is said to occur in w with exponent α, for positive real α, if there is a factor y of w with y = x^ax₀ where x₀ is a prefix of x, a is the integer part of α, and the length |y| ≥ α |x|: we say that y is an α-power. The word w is α-power-free if it contains no factors which are α-powers.

The critical exponent for w is the supremum of the α for which w has α-powers, or equivalently the infimum of the α for which w is α-power-free.

Examples

• The critical exponent of the Fibonacci word is (5 + √5)/2 ≈ 3.618.
• The critical exponent of the Thue–Morse sequence is 2. The word contains arbitrarily long squares, but in any factor xxb the letter b is not a prefix of x.

Properties

• The critical exponent can take any real value greater than 1.
• The critical exponent of a morphic word over a finite alphabet is an algebraic number of degree at most the size of the alphabet.

See also

• Critical exponent of a physical system

References

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Krieger, Dalia (2006). "On critical exponents in fixed points of non-erasing morphisms". In Ibarra, Oscar H.; Dang, Zhe (eds.). Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006. Lecture Notes in Computer Science. Vol. 4036. Springer-Verlag. pp. 280–291. ISBN 3-540-35428-X. Zbl 1227.68074.
• Krieger, D.; Shallit, J. (2007). "Every real number greater than one is a critical exponent". Theor. Comput. Sci. 381: 177–182. doi:10.1016/j.tcs.2007.04.037.
• Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
• Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.