Critical exponent of a word

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. ^[3]

Definition

If ${\displaystyle \mathbf {w} }$ is a word (possibly infinite), then the critical exponent of ${\displaystyle \mathbf {w} }$ is defined to be

${\displaystyle E(\mathbf {w} )=\sup\{r\in \mathbb {Q} ^{\geq 1}:\mathbf {w} \,{\text{ contains an }}\,r{\text{-power}}\}}$

where ${\displaystyle \mathbb {Q} ^{\geq 1}=\{q\in \mathbb {Q} :q\geq 1\}}$. ^[4]

Examples

• The critical exponent of the Fibonacci word is (5 + √5)/2 ≈ 3.618. ^{[3] [5]}
• The critical exponent of the Thue–Morse sequence is 2. ^[3] 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. ^{[3] [6]}
• 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. ^[3]

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] [5]}

See also

• Critical exponent of a physical system

Notes

1. Krieger (2006) p.281
2. Berstel et al (2009) p.126
3. Krieger (2006) p.280
4. Krieger (2006) p.282
5. Allouche & Shallit (2003) p. 37
6. Krieger & Shallit (2007).

References

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN   978-0-521-82332-6. Zbl   1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN   978-0-8218-4480-9. Zbl   1161.68043.
• 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 (1–3): 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). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Berlin: Springer-Verlag. ISBN   3-540-44141-7. Zbl   1014.11015.