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.
|
|
|
|