🚀 go-pugleaf

Open Problems in Pattern Avoidance


INTRODUCTION


What makes a mathematical area interesting? The area should contain a 
range of open problems: some very concrete and approachable, others "bigger". 
These days it might help for the area to tie in with chaos and fractals. 
Finally, it couldn't hurt for someone to offer cash for solutions to problems 
in the area.

Consider the study of words avoiding patterns. A WORD is a finite sequence 
of elements of some finite set S. We call the set S an ALPHABET, the elements 
of S LETTERS. The set of all words over S is written S*. We take a naive 
view of words as strings of symbols; thus the concatenation of two words 
w and v, written wv, is simply the string consisting of the letters of 
w followed by the letters of v. The empty word, denoted e, is the word 
with no letters in it. The LENGTH of a word w, denoted len(w), is the 
number of letters in w. For example, u=abcdcda is a word over the alphabet 
S={a, b, c, d, e}, and len(u)=7.

Let S and T be alphabets. A SUBSTITUTION h:S*-->T* is a function generated 
by its values on S. That is, suppose w in S*, w=w1 w2 ... wn with wi in 
S, i=1, ..., n. Then h(w)=h(w1)h(w2)...h(wn). We do not allow h(wi)=e 
for any i. As an example, we could give a substitution h:{1, 2, 3}*-->{1, 
2, 3}* by h(1)=123, h(2)=13, h(3)=2. In this case, h(123)=h(1)h(2)h(3)=123132. 
An OMEGA-WORD over S is a countably infinite sequence of letters of S.

A word w over an alphabet S is NON-REPETITIVE (or square-free) if no two 
adjacent blocks in w are identical. For example, the word v=abcacb is 
non-repetitive. On the other hand, the word u=abcbcd is repetitive, since 
bc occurs next to itself in u. Early in this century the Norwegian number 
theorist Axel Thue showed that arbitrarily long non-repetitive words can 
be formed using only three letters [20]. By Konig's infinity lemma, this 
means that there is a non-repetitive omega-word over S={1, 2, 3}. This 
result has been rediscovered and republished a dozen times or more. One 
reason for this sequence of rediscoveries is that non-repetitive sequences 
have been used to construct counter-examples in many areas of mathematics: 
ergodic theory, formal language theory, universal algebra and group theory, 
for example [11, 12, 6, 15].

We say that a non-repetitive word over S AVOIDS xx. Such a word cannot 
be written ah(xx)b where a, b in S* and h:{x}*-->S* is a substitution. 
Thue also showed that arbitrarily long CUBE-FREE words on two letters 
exist [20]. Such words avoid xxx in the sense that they cannot be written 
ah(xxx)b. The infinite cube-free word discovered by Thue is referred to 
as the Morse-Thue sequence, and is an important example in symbolic dynamics 
[15]. Symbolic dynamics is a key tool for studying chaotic dynamics.

Before posing our problems, we need a bit more background. Let w and p 
be words. We say that w CONTAINS pattern p if we can write w=ah(p)b for 
words a and b, and some substitution h. Otherwise, we say that w AVOIDS 
p. Let a pattern p be fixed. Let S be an alphabet with k letters. If there 
are arbitrarily long words over S avoiding p, we say that p is AVOIDABLE 
ON S. Clearly, only the number k of letters in S is significant here, 
so we also say that p is AVOIDABLE OB k LETTERS.

For example, xx is avoidable on 3 letters. If for some k, p is avoidable 
on k letters, we say that p is AVOIDABLE. Otherwise, p is UNAVOIDABLE. 
For example, xyx is unavoidable. According to a pretty result of Zimin 
[21], a pattern p on n letters is avoidable if and only if Zn avoids p, 
where Zn is the word on {1, 2, ..., n} defined by Z1=1, Zn=Z(n-1) n Z(n-1), 
n>1. However, no method is known to determine the smallest alphabet on 
which p is avoidable [2, 3]. In [2], a word U-delta is given which is 
avoidable on 4 letters, but not on 3. Perhaps all avoidable words are 
avoidable on 4 letters.

A word w is STRONGLY NON-REPETITIVE if no two adjacent blocks in w are 
permutations of each other. For example, u=512341231416 is  not  strongly 
non-repetitive since the adjacent blocks 12341 and 23141 are permutations 
of each other. Let p be a word over an alphabet S, p=p1 p2 ... pn, pi 
in S, i=1...n. Say that a word w STRONGLY AVOIDS p if we cannot write 
w=a q1 q2 ... qn b where a, b are words, the qi are non-empty words, and 
qi is a permutation of qj whenever pi=pj. Thus a word is strongly non-repetitive 
if and only if it strongly avoids xx. We define what it means for a pattern 
p to be STRONGLY AVOIDABLE (ON k LETTERS) in the obvious way.

It is known that xx is strongly avoidable on 5 letters, but not on 3 letters 
[16]. Whether xx is strongly avoidable on 4 letters has long been open. 
On the other hand, the smallest alphabet on which xxx can be strongly 
avoided is the 3 letter alphabet and the smallest alphabet on which xxxx 
can be strongly avoided is the 4 letter alphabet [10].

Let a=a1 a2 a3 ... and b=b1 b2 b3 ... be omega-words over some alphabet 
S, with ai, bi in S. Define the distance between a and b to be r(a, b)=1/(k+1) 
where k=min{i: ai, bi differ}. Thus the longer a and b go on agreeing, 
the closer together a and b are. Let L be the set of non-repetitive omega-words 
over S={1, 2, 3}. With respect to the metric r, L has no isolated points; 
for any non-repetitive omega-word a over S, we can find distinct non-repetitive 
omega-words over S agreeing with a to as many places as desired . [17, 
18, 19]  It follows that L is a PERFECT SET.

CONCRETE PROBLEMS

 1. Is there a pattern w which is avoidable on 5 letters but not on 4 
letters? [2]

 2. Can xx be strongly avoided on 4 letters? [5, 10, 13, 16]

 3. Let L be the set of non-repetitive words over the 3 letter alphabet 
{1, 2, 3}. It 
is known that c(n), the number of words of L of length n, grows exponentially 
[4]. Give an exact enumeration for L. For the solution to this problem 
I offer US$100.

 4. Is the set of cube-free omega-words over a 2-letter alphabet perfect?

"BIGGER" PROBLEMS

 1. Is there an algorithm which decides, given a pattern p and a natural 
number k, whether p is avoidable on k letters? [3] If so, give such an 
algorithm. I offer US$100 for the solution to this problem.

 2. Is there an algorithm which decides, given a pattern p, whether p 
is strongly avoidable on SOME fixed alphabet? If so, give such an algorithm. 
Again, US$100 to the solver of this problem.

 3. Is there an algorithm which decides, given a pattern p and a natural 
number k, whether p is strongly avoidable on k letters? If so, give such 
an algorithm. I offer US$500 for the solution to this problem! Note that 
concrete problem 2 above is not necessarily a sub-problem of this problem.

 4. For US$100, decide the following conjecture: If pattern p is avoidable 
on S, then the set of omega-words on S avoiding p is perfect.

 5. For US$100, decide the following conjecture: If the smallest alphabet 
on which p is avoidable is {1, 2, ..., k}, then there exists a natural 
number m, and substitutions f:{1, 2, ..., m}*--> {1, 2, ..., k}* and g:{1, 
2, ..., m}*-->{1, 2, ..., m}* such that f(g^n(1)) avoids p.

REFERENCES

[1] S. ARSHON, Demonstration de l'existence des suites asymetriques infinies, 
Mat. Sb., 2 (44) (1937), 769-779.
[2] K. A. BAKER, G. F. MCNULTY AND W. TAYLOR, Growth problems for avoidable 
words, preprint.
[3] D. BEAN, A. EHRENFEUCHT AND G. MCNULTY, Avoidable Patterns in Strings 
of Symbols, Pacific J. Math. 85 (1979), 261-294.
[4] J. BRINKHUIS, Non-repetitive sequences on three symbols, Quart. J. 
Math. Oxford (2) 34 (1983), 145-149.
[5] T. C. BROWN, Is there a sequence on four symbols in which no two adjacent 
segments are permutations of each other?, Amer. Math. Monthly 78 (1971), 
886-888.
[6] S. BURRIS AND E. NELSON, Embedding the dual of    in the lattice of 
equational classes of semigroups, Algebra Universalis, 1 (1971), 248-253.
[7] J. D. CURRIE, Non-repetitive walks in graphs and digraphs, Ph. D. 
thesis, University of Calgary, Alberta, Canada (1987).
[8] J. D. CURRIE, Which graphs allow infinite non-repetitive walks? Disc. 
Math. 87 (1991), 249-260.
[9] J. D. CURRIE, Subwords of non-repetitive words, J. Comb. Th. Ser. 
A, to appear.
[10] F. M. DEKKING, Strongly non-repetitive sequences and progression-free 
sets, J. Comb. Th., Ser. A 27 (1979) 181-185.
[11] A. DEL JUNCO, A transformation with simple spectrum which is not 
rank one,  Canadian J. Math.  29 (1977) 655-663.
[12] A. EHRENFEUCHT AND G. ROZENBURG, On the separating power of EOL systems, 
RAIRO Informatique 17 (1983) 13-22.
[13] P. ERDOS, Some unsolved problems, Magyar Tud. Akad. Mat. Kutato Int. 
Kozl. 6 (1961), 221-254.
[14] M. MORSE AND G. A. HEDLUND, Symbolic dynamics I and II, Amer. J. 
Math. 60 (1938) 815866 and 62 (1940) 142
[15] P. S. NOVIKOV AND S. I. ADJAN, Infinite periodic groups I, II, III, 
Math. U.S.S.R. Izv. 2 (1968) I: 209-236, II: 241-479, III: 665-685.
[16] P. A. B. PLEASANTS, Non-repetitive sequences, Proc. Camb. Phil. Soc., 
68 (1970) 267-274.
[17] R. O. SHELTON AND R. P. SONI, Aperiodic words on three symbols, J. 
reine agnew. Math. 321 (1981), 195-209.
[18] R. O. SHELTON AND R. P. SONI, Aperiodic words on three symbols II, 
J. reine agnew. Math. 327 (1981), 1-11.
[19] R. O. SHELTON AND R. P. SONI, Aperiodic words on three symbols III, 
J. reine agnew. Math. 330 (1981), 44-52.
[20] A. THUE, Uber unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. 
Mat. Nat. Kl. Christiana (1912) 1-67.
[21] A. ZIMIN, Blocking sets of terms, Mat. Sb. 119 (161) (1982); Math. 
USSR Sbornik 47 (1984) 353-364.