What is the longest repetition-free string one can build with {0,1,2}?

This note constructs an infinite string S on {a,b,c} with no
repetitions (i.e. no cases of subwords ww).

HOW TO MAKE THE INFINITELY LONG STRING S:
Construct an infinite string in the alphabet {a,b,c} as follows:
Let s(1) = abcba, and let s(n+1) be the string obtained from s(n)
by replacing each a,b,c in s(n) by the following:
   a |--> abcba
   b |--> bcacb
   c |--> cabac.
Thus for example s(2) = abcba bcacb cabac bcacb abcba.
[The spaces are only for readability.]
Here is s(3), of length 125, written in 5 rows of 25:
     abcba bcacb cabac bcacb abcba
     bcacb cabac abcba cabac bcacb
     cabac abcba bcacb abcba cabac
     bcacb cabac abcba cabac bcacb
     abcba bcacb cabac bcacb abcba
Each s(n+1) ends up having s(n) as an initial segment.
The length of s(n) is 5^n.  Since s(n) is an initial segment
of s(n+1), it follows that one gets a string of infinite
length by iterating this process.  Let S denote this infinite string.

  WHY THE STRING S HAS NO REPETITIONS
Suppose the string ww occurs in the string S.  By construction S is
made up from the three words
    p = abcba
    q = bcacb
    r = cabac.
----> | Claim: we may assume w to be a word
      | made from the subwords p,q,r.
[begin proof of claim]
For suppose w is of the form
      w = x(t_1)(t_2)...(t_k)y
where each t_i is one of p,q,r and the strings x, y have length <= 4.
Then the supposed occurrence of ww becomes
 *    x(t_1)...(t_k)yx(t_1)...(t_k)y.
Thus yx must be one of p,q,r.  y is not null, else length (yx) < 5.
It is then clear that the final y on the end of * must be followed by
x [look at p,q,r; none have any initial segments (or final segments)
in common]
Thus we have the repetition
    (t_1)...(t_k)(yx)(t_1)...(t_k)(yx),
which allows us to reset w to w = (t_1)...(t_k)(xy) and have
a repetition ww where w is a string made of the words p,q,r as
required.
[end proof of claim]

The claim makes it clear that S has no repetitions:  If there are any
repetitions ww we may suppose that w is taken as small as possible.
By the claim we may then write w in the words p,q,r.  But then
replacing p,q,r by a,b,c respectively we have a repetition vv, where v
has 1/5 the length of w.  [the sequence S has the property that *any*
word in p,q,r which occurs in the string produces another word in the
string obtained by replacing p|->a, q|->b, r|->c ]

-- Dan Cass <dmc@sjfc.edu>

There must be a flaw in your proof of the claim.  If w = "cbab", then
ww appears starting at character 19 in your s(3).  Using your
terminology, ww = xpy, where x = "cb" and y = "b".  I assume that your
proof breaks down in part because you assume that you can separate the
t_i's into two groups (in *).  In the counter-example, there's only
one t_i: t_1 = p.

-- Lou D'Andria <lou@wri.com>

> If w = "cbab", then ww appears starting at character 19 in your s(3).
> Using your terminology, ww = xpy, where x = "cb" and y = "b".

Not quite.  p = abcba, not a.  The proof breaks down because in the
counterexample, k = 0 (not even 1), hence there is no mechanism to
align yx between the boundaries of two five-letter groups as Dan Cass
was depending on.

-- David A. Karr <karr@cs.cornell.edu>

Where a "repetition"--more usually called a "square"--is two nonempty
equal adjacent consecutive substrings.

dmc@sjfc.edu (Dan Cass) thought he had an example of an infinite
string, but Lou D'Andria <lou@wri.com> found his example was faulty.

I found a paper on squares in binary sequences by Aviezry S Fraenkel
and R Jamie Simpson in _The Electronic Journal of Combinatorics_,
Volume 2 (http://ejc.math.gatech.edu:8080/Journal/Volume_2).

It includes the statement:

  It has been shown many times that there exist infinite squarefree
  _ternary_ sequences.  See e.g., Thue (1912), Morse and Hedlund
  (1944), Hawkins and Mientka (1956), Leech (1957), Novikov and
  Adjan (1968), Pleasants (1970), Burris and Nelson (1971/72),
  del Junco (1977), Ehrenfeucht and Rozenberg (1983).  (Currie
  (1993) wrote: ``One reason for this sequence of rediscoveries is
  that nonrepetitive sequences have been used to construct
  counterexamples in many areas of mathematics: ergodic theory, formal
  language theory, universal algebra and group theory, for
  example...''.)  Actually, Thue (1912) showed more: there exists a
  doubly infinite squarefree ternary sequence which also avoids the 2
  triples $a_1a_3a_1$ and $a_2a_3 a_2$.  See Berstel (1992, \S4.2)
  for an exposition of the full result, and Berstel ($\ge$ 1995) for
  an English translation of Thue's papers.

The cited references are:

1.  J. Berstel (1992), Axel Thue's work on repetitions in words, in:
    _Series Formelles et Combinatoire Algebrique_ (P. Leroux and
    C. Reutenauer, eds.), Publ. du LACIM, Vol. 11, Universite de
    Quebec, a Montreal, pp. 65-80.
2.  J. Berstel ($\ge$ 1995), Axel Thue's papers on repetition in
    words: an English translation, Publ. du LACIM, Universite de
    Quebec, a Montreal.
3.  S. Burris and E. Nelson (1971/72), Embedding the dual of
    $\pi_{\infty}$ in the lattice of equational classes of semigroups,
    _Algebra Universalis_ 1, 248-153.
4.  J.D. Currie (1993), Open problems in pattern avoidance,
    _Amer. Math. Monthly_ 100, 790-793.
5.  A. del Junco (1977), A transformation with simple spectrum which
    is not rank one, _Canad. J. Math._ 29, 655-663.
6.  A. Ehrenfeucht and G. Rozenberg (1983), On the separating power of
    EOL systems, _RAIRO Inform. Theor._ 17, 13-22.
8.  D. Hawkins and W.E. Mientka (1956), On sequences which contain no
    repetitions, _Math. Student_ 24, 185-187.
12. J.A. Leech (1957), A problem on strings of beads, _Math.  Gaz._
    41, 277-278.
14. M. Morse and G.A. Hedlund (1944), Unending chess, symbolic
    dynamics and a problem in semigroups, _Duke Math. J._ 11, 1-7.
15. P.S. Novikov and S.I. Adjan (1968), Infinite periodic groups I,
    II, III, _Izv. Akad. Nauk. SSSR Ser. Mat._ 32, 212-244; 251-524;
    709-731.
16. P.A.B. Pleasants (1970), Non-repetitive sequences,
    _Proc. Cambridge Phil. Soc._ 68, 267-274.
19. A. Thue (1912), Uber die gegenseitige Lage gleicher Teile gewisser
    Zeichenreihen, _Norske Vid. Selsk. Skr., I. Mat.
    Nat. Kl. Christiania_ I, 1-67.

-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>  (April 1995)

[ Editor: so the answer to the question is that there is no longest
one: infinite squarefree strings on three symbols exist. ]

I did a little research and found that infinite 3-letter non-repetitive
sequences [containing no case of ww] have been known to exist since
the 1930's!  Apparently the first proof was by de Bruijn in the 30's,
then a later proof by Peltesohn and Sutherland.

There are (at least) three published proofs:
1. Morse and Hedlund (1944) "Unending Chess, symbolic dynamics and
    a problem in semigroups", Duke Math. J. 11, pp1-7.
2. Leech (1957) "A problem on strings of beads", Math. Gaz. 41,
    pp277-278.
3. Pleasants (1970) "Non-repetitive sequences", Proc. Camb. Phil. Soc
    68, pp267-274.

I haven't looked these up, but at least it makes me think the method I
used probably can be made to work using different word substitutions
for a,b,c than the short ones I tried.  The paper I do have by
Pleasants concerns the search for a 4-letter sequence which is strongly
non-repetitive in that no two adjacent words ww' are such that w' is a
permutation of w.  [i.e. a string like 123132 is not allowed, since the
132 is a permuted version of the 123.]

It seems M.R.Bird has found a 1,600 term strongly non-repetitive
sequence on 4 symbols.  He only had to alter back 25 terms or so while
constructing it (via a tree-search).  But no one has yet made an
explicit infinite 4-letter strongly non-repetitive string, or even
proved definitely that one exists.  At any rate Pleasants does give an
explicit 5-letter strongly non-repetitive infinite string.

-- Dan Cass <dmc@sjfc.edu>, April 1995

Let S[0]= (), the sequence of no terms

Let R[n] denote the sequence S[n], reversed, for all non-negative n.

Define S[n] as the concatenation of the following sequences:
 S[n-1] (1) R[n-1] (0) R[n-1] (2) S[n-1]

Then the sequences S[n] are all square-free and, for large enough n,
are of length greater than N for any given finite N.

S[1]=(1,0,2)
S[2]=(1,0,2, 1, 2,0,1, 0, 2,0,1, 2, 1,0,2)

These sequences are sequences of values of a function which can be
defined thus.  Say that a non-negative integer is "evil" if its binary
representation (with nothing to the right of the binary point) has an
even number of 1s and "odious" otherwise.  Define f on the positive
integers as follows:

f(n) = 1 if n-1 is evil and n is odious
       2 if n-1 is odious and n is evil
       0 otherwise

For example:
n                1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
n-1 odi. or evil e o o e o e e o o e  e  o  e  o  o  e
n odious or evil o o e o e e o o e e  o  e  o  o  e  o
f(n)             1 0 2 1 2 0 1 0 2 0  1  2  1  0  2  1

Then the sequence (f(1), f(2), ....) is square-free.  What is more,

for all i in {0,1,2}, lim(N->oo) |{non-negative integer n<N | f(n)=i}|/N
[Editor: "|...|/N", the proportion, is missing in the original] = 1/3.

We also have f(4n)=f(n).

The terms "odious" and "evil" are used with the above meanings in
Berlekamp, Conway and Guy's "Winning Ways".

-- Richard Sabey <rsa@swindon.gpsemi.com> (April 1995)