NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/sci/math/research/407

Text File | 1992-08-17 | 9.9 KB | 192 lines

Newsgroups: sci.math.research
Path: sparky!uunet!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!usenet
From: [e-mail]
Subject: CASH PROBLEMS
Nntp-Posting-Host: uwpg02.uwinnipeg.ca
Message-ID: <[e-mail]>
Sender: Daniel Grayson <[e-mail]>
X-Submissions-To: [e-mail]
Organization: University of Winnipeg
X-Administrivia-To: [e-mail]
Approved: Daniel Grayson <[e-mail]>
Date: Mon, 17 Aug 1992 17:15:04 GMT
Lines: 177

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.