Thue sequence and p-adic
topology of the free monoid
Jean Berstel, Maxime Crochemore et Jean-Éric Pin
Résumé : Etant donné deux mots u et
v, le coefficient binomial Binom(u,v) est le nombre de
façons d'écrire v comme sous-mot (au sens de
sous-suite) de u. La suite de Thue-Morse est le mot infini t =
abbabaab... obtenu en itérant le morphisme g(a) = ab et
g(b) = ba. On montre que, pour tout nombre premier p, et pour
tout entier positif n, il existe un entier m = f(p,n), tel
que, pour tout mot non vide v de longueur inférieure ou
égale à n, le coefficient binomial
Binom(t[m],v) est congruent à 0 modulo p. En
fait f(p,n) = 2np1+ [logp n]
pour p ≠ 2 et f(2,n) = 2k si
Fk-1 ≤ n < Fk, où Fk
designe le k-ième nombre de Fibonacci. Il en résulte
que, pour chaque nombre premier p, il existe une suite de facteurs
gauches de t de longueur croissante, dont la limite est le mot vide
dans la topologie p-adique du monoïde libre.
Abstract : Given two words u and v, the binomial
coefficient Binom(u,v) is the number of ways v appears as a
subword (or subsequence) of u. The Thue-Morse sequence is the
infinite word t = abbabaab... obtained by iteration of the morphism
g(a) = ab and g(b) = ba. We show that, for every prime
p, and every positive integer n, there exists an integer m
= f(p,n), such that, for every non-empty word v of length less
than of equal to n, the binomial coefficient Binom(t[m],v) is
congruent to 0 modulo p. In fact f(p,n) =
2np1+ [logp n] for p ≠
2 and f(2,n) = 2k if Fk-1 ≤ n <
Fk, where Fk denotes the k-th
Fibonacci number. It follows that, for each prime number p, there
exists a sequence of left factors of t of increasing length, the
limit of which is the empty word in the p-adic topology of the free
monoid.