Thue-Morse sequence and p-adic topology for the free monoid

✍ Scribed by J. Berstel; M. Crochemore; J.E. Pin

• Publisher: Elsevier Science
• Year: 1989
• Tongue: English
• Weight: 525 KB
• Volume: 76
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(89)90302-6

✦ Synopsis

Given two words u and v, the binomial coefficient (t) 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 r(a) = ab and z(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 or equal to n, the binomial coefficient (":I) is congruent to 0 modp. In fact f (p, n) = 2"p1+ L'ogpnJ for p # 2 and f (2, n) = 2k if F,_, S n < Fk, where Fk denotes the kth Fibonacci number. It follows that, for each prime number p, there exists a sequence of left factors oft of increasing length, the limit of which is the empty word in the p-adic topology of the free monoid.