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 = xax0 where x0 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.[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]

## Contents

* 1 Definition
* 2 Examples
* 3 Properties
* 4 Repetition threshold
* 5 See also
* 6 Notes
* 7 References

## Definition

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

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

where [math]\displaystyle{ \mathbb{Q}^{\geq 1} = \\{ q \in \mathbb{Q} : q \geq 1 \\} }[/math].[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. ↑ 2.0 2.1 Berstel et al (2009) p.126
3. ↑ 3.0 3.1 3.2 3.3 3.4 (Krieger 2006) p.280
4. ↑ (Krieger 2006) p.282
5. ↑ 5.0 5.1 (Allouche Shallit) 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.
* Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. https://www.ams.org/bookpages/crmm-27.
* Krieger, Dalia (2006). "On critical exponents in fixed points of non-erasing morphisms". in Ibarra, Oscar H.; Dang, Zhe. Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006. Lecture Notes in Computer Science. 4036. Springer-Verlag. pp. 280–291. ISBN 3-540-35428-X.
* 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. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9.
* Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Critical exponent of a word. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Critical_exponent_of_a_word&oldid=3207183"