3
$\begingroup$

From here.

This particular item deals with excluding strings that have a consecutive repeated sequence. That is, ab*b*a and abcab*ab*c both have doubles whereas abcabacba doesn't. When working in base $2$, the number of sequences is easily seen to be finite.

0
1

00
01
10
11

010
011
100
101

0100
0101
1010
1011

They also mention that base $10$ is known to be infinite. In addition, base $3$ seems to be infinite, as evidenced by this exponentially-growing pattern.

My question is: how can you prove that the number of repetition-free sequences is infinite for base $b \ge 3$?

  • 2
    If you can prove it is infinite for base $b$, then it is infinite for any base $b'\geq b$. Now look up Thue's sequence. (It may be called something else, but Thue gave an infinite squarefree word in three letters).2012-02-14
  • 0
    P.S. The more common term is "squarefree words", not "repetition-less digit strings". That might also help with internet searches.2012-02-14
  • 0
    You mean the Thue-Morse sequence? But that's in binary...2012-02-14
  • 1
    No, I mean the sequence that Thue produced for an alphabet with three letters. E.g., [Wikipedia's entry on "Squarefree word"](http://en.wikipedia.org/wiki/Squarefree_word).2012-02-14
  • 0
    Arturo means what Arturo says.2012-02-14
  • 0
    @Arturo: Ah, neat! Thanks!2012-02-14

2 Answers 2

8

This paper gives a very nice elementary presentation of the Thue-Morse sequence and in particular of the result that there is an infinite square-free sequence over an alphabet of three letters.

7

Thue proved that any alphabet on three or more letters contains an infinite squarefree word. An example due to Leech (A problem on strings of beads, Math. Gazette 41 (1957) 277– 278):

On the alphabet that contains $a$, $b$, and $c$, define $w_1$ to be a word beginning with $a$ (say, $w_1=a$).

Given $w_n$, define $w_{n+1}$ by replacing each occurrence of $a$ in $w_n$ by $abcbacbcabcba$; every occurrence of $b$ in $w_n$ by $bcacbacabcacb$; and every occurrence of $c$ by $cabacbabcabac$.

Then $w_n$ converges to an infinite squarefree word, which begins $$abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb\ldots$$