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''^''a''''x''₀ 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 β ≥ α. p.281 The ''critical exponent'' for ''w'' is the

supremum In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...

of the α for which ''w'' has α-powers,Berstel et al (2009) p.126 or equivalently the infimum of the α for which ''w'' is α-power-free.

Definition

\mathbf

is a word (possibly infinite), then the ''critical exponent'' of

\mathbf

is defined to be :

E(\mathbf) = \sup \

where

\mathbb^ = \

. p.282

Examples

* The critical exponent of the Fibonacci word is (5 + )/2 ≈ 3.618. p. 37 * 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 An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...

of degree at most the size of the alphabet. p.280

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.

Notes

References