Repetitions in sequences

Two of the fundamental questions in the area of combinatorics on words are the following: Is there an infinite sequence of letters over a binary alphabet that contains no cubes, i.e., no word repeating consecutively three times? Is there an infinite sequence over a ternary alphabet that contains no squares, i.e., no word repeating consecutively two times?

Both of these questions were affirmatively answered by Axel Thue in the beginning of the 20th century. It is clear that some repetitions have to occur in any infinite sequence over a finite alphabet. The maximum repetition rate in a sequence is captured by the notion of the critical exponent. The critical exponent of any sequence is greater than 1, and it is natural to ask what is the smallest possible critical exponent for a given class of sequences. For example, the sequences in Thue's answers must have their critical exponents at most 3 and at most 2, respectively. In fact, the sequence answering the second question has the critical exponent equal to 2, and it is known as the Thue-Morse sequence.

In this talk, we first introduce the required notions and explain how to compute the critical exponent for certain classes of sequences. After that, we will present our recent results concerning the minimal critical exponent. This talk is based on joint works with Ľ. Dvořáková, E. Pelantová, A. M. Shur, J. Currie, P. Ochem, N. Rampersad, and J. Shallit.