Critical exponent of a word explained

In mathematics and computer science, the critical exponent of a finite or infinite sequence of symbols over a finite alphabet describes the largest number of times a contiguous subsequence can be repeated. For example, the critical exponent of "Mississippi" is 7/3, as it contains the string "ississi", which is of length 7 and period 3.

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 for any β ≥ α.^[1]

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

Definition

If

w is a word (possibly infinite), then the critical exponent of w is defined to beE( w ) = \sup \{ r \in Q ^{\geq} : w containsan r -power \} where Q ^{\geq} = \{ q \in Q : q \geq 1 \} .^[3]

Examples

• The critical exponent of the Fibonacci word is (5 + )/2 ≈ 3.618.^[4]
• 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 either infinite or an algebraic number of degree at most the size of the alphabet.^[5]

Repetition threshold

The repetition threshold of an alphabet A of n letters is the minimum critical exponent of infinite words over A: clearly this value RT(n) depends only on n. For n=2, any binary word of length four has a factor of exponent 2, and since the critical exponent of the Thue–Morse sequence is 2, the repetition threshold for binary alphabets is RT(2) = 2. It is known that RT(3) = 7/4, RT(4) = 7/5 and that for n≥5 we have RT(n) ≥ n/(n-1). It is conjectured that the latter is the true value, and this has been established for 5 ≤ n ≤ 14 and for n ≥ 33.^{[2] [4]}

See also

• Critical exponent of a physical system

References

• Book: Allouche . Jean-Paul . Shallit . Jeffrey . Jeffrey Shallit . 978-0-521-82332-6 . . Automatic Sequences: Theory, Applications, Generalizations . 2003 . 1086.11015 .
• Book: Berstel . Jean . Lauve . Aaron . Reutenauer . Christophe . Saliola . Franco V. . Combinatorics on words. Christoffel words and repetitions in words . CRM Monograph Series . 27 . Providence, RI . . 2009 . 978-0-8218-4480-9 . 1161.68043 .
• Book: Krieger, Dalia . Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006 . 4036 . Lecture Notes in Computer Science . Oscar H. . Ibarra . Zhe . Dang . . 2006 . 3-540-35428-X . On critical exponents in fixed points of non-erasing morphisms . 280–291 . 1227.68074 .
• D. . Krieger . J. . Shallit . Every real number greater than one is a critical exponent . Theor. Comput. Sci. . 381 . 2007 . 1–3 . 177–182 . 10.1016/j.tcs.2007.04.037 . free .
• Book: Lothaire, M. . M. Lothaire

. M. Lothaire . Algebraic combinatorics on words . With preface by Jean Berstel and Dominique Perrin . Reprint of the 2002 hardback . Encyclopedia of Mathematics and Its Applications . 90. Cambridge University Press . 2011 . 978-0-521-18071-9 . 1221.68183 .

• Book: Pytheas Fogg, N. . Berthé, Valérie. Valérie Berthé. Ferenczi, Sébastien. Mauduit, Christian. Siegel, A. . Substitutions in dynamics, arithmetics and combinatorics . Lecture Notes in Mathematics . 1794 . Berlin . . 2002 . 3-540-44141-7 . 1014.11015 .

Notes and References

1. p.281
2. Berstel et al (2009) p.126
3. p.282
4. p. 37
5. p.280