# Critical exponent of a word

2010 Mathematics Subject Classification: Primary: 68R15 [MSN][ZBL]

For a finite or infinite word 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 finite alphabet $A$ and $x$ is a finite word over $A$, then $x$ is said to occur in $w$ with exponent $\alpha$, for positive real $\alpha$, if there is a factor $y$ of $w$ with $y = x^a x_p$ where $x_p$ is a prefix of $x$, $a$ is the integer part of $\alpha$, and the length $|y| \ge \alpha |x|$|: we say that $y$ is an $\alpha$-power. The word $w$ is $\alpha$-power-free if it contains no factors which are $\alpha$-powers.

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

## Contents

#### Examples

• The critical exponent of the Fibonacci word is $\frac{5+\sqrt5}{2} = 3.618\ldots$.
• 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.

#### 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 \ge 5$ we have $RT(n) = 1 + 1/(n-1)$.

How to Cite This Entry:
Critical exponent of a word. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Critical_exponent_of_a_word&oldid=45741