May 5, 2008
"Combinatorics on words and Fraenkel's conjecture"
Laurent Vuillon
Universite de Savoie, France
This lecture gives a link between a problem of covering the integers and combinatorics on words in order to investigate the Fraenkel's conjecture. This conjecture was first introduced in number theory and has remained unsolved for more than 30 years. It states that for a fixed k > 2, there is only one way to cover Z by k Beatty sequences with pairwise distinct frequencies. The prob- lem can be translated to combinatorics on words: for a k-letter alphabet, there is only one balanced sequence (up to letter permutation) that has different letter frequencies, which is called s sequence and is denoted by (F r_k )^omega where F r_k = F r_{k-1} k F r_{k-1}, with F r_3 = 1213121. The conjecture is verified for k = 3, 4, 5, 6 according to the work of Altman, Gaujal, Hordijk and Tijdeman. In this talk, we present a survey of this problem and show the conjecture in a special case.