5
$\begingroup$

As an application in group theory, I would need an infinite sequence over a finite alphabet, that avoids a sequence of words $w_i$, where the length of $w_i$ is such that $l(w_i) > 10^8 l(w_{i-1})$.

I have found several results about avoiding patterns, but here I would really just need to avoid the words themselves.

Do there exist results along these lines?

$\endgroup$
  • $\begingroup$ Is your set of words decidable? $\endgroup$ – Maxime Lucas Mar 6 '15 at 13:59
  • 3
    $\begingroup$ I don't think there is enough information available to enable a sensible answer to this question. All you can do is to run through the words in something like length-lexicographical orde rand check each word in turn for membership of the forbidden list. If, for example, you knew that the forbidden words formed a regular set, then you could do much better! $\endgroup$ – Derek Holt Mar 6 '15 at 14:32
  • 1
    $\begingroup$ It is easy to avoid some infinite sets of words. It is impossible to avoid others. $\endgroup$ – Douglas Zare Mar 6 '15 at 14:59
  • $\begingroup$ Thanks for your remarks, I have now edited the question. I of course didn't mean all words of length at least $10^8$. However, apart from that I have no information about them. $\endgroup$ – Elisabeth Fink Mar 6 '15 at 15:13
8
$\begingroup$

I am not sure that it is exactly what you need, but the following is true:

For an alhabet with $q\geq 4$ letters and a sequence of forbidden words with lengths $n_1<n_2<\dots$ there exists an infinite word without forbidden subwords (where subword of a word W is a segment of consecutive letters in W, like "hab" is a subword of "alphabet".)

Proof. Choose $c$ like $c=2$ and prove that for the number $f(n)$ of permitted words of length $n$ (i.e. words without forbidden subwords) we have $f(n)\geq cf(n-1)$.

Induction in $n$. Base $n=1$ holds ($f(0)=1$, $f(1)\geq q-1$).

We have $f(n)\geq qf(n-1)-\sum_i f(n-n_i)$ (take any permitted word with $n-1$ letter and add arbitrary letter. If new word is not permitted, then it ends by some forbidden subword.) By induction purpose we have $f(n-i)\leq c^{1-n}f(n-1)$, thus $f(n)\geq (q-\sum c^{1-n_i})f(n-1)\geq cf(n-1)$ as desired.

Now we have arbitrarily long permitted words. It follows that there exists an infinite permitted word (proof: choose letters $x_1,x_2,\dots,x_n$ so that word $x_1\dots x_n$ has arbitrarily long permitted continuations. We may always proceed.)

Above argument works for $q=2$ and $q=3$ under stronger assumptions on $(n_i)$.

$\endgroup$
  • $\begingroup$ Many thanks for this Fedor! This is very helpful. I might have to adapt it a little bit for my case, but it shows what I suspected, that it's possible. $\endgroup$ – Elisabeth Fink Mar 7 '15 at 7:35
  • 3
    $\begingroup$ For general $n_1<n_2<\dots$ I think you need $q\geq 4$ so that $q-\sum c^{1-n_i}$ is guaranteed to be at least $c$. With a three letter alphabet $\{a,b,c\}$ the forbidden words $\{c,ba,aaa,bbbb\}$ don't allow an infinite word. Though if $n_2>10^8$ then the argument works for a three letter alphabet with $c=3/2$. $\endgroup$ – Jeremy Rickard Mar 7 '15 at 9:15
  • $\begingroup$ I guess I must have completely misinterpreted the question, which does not mention subwords at all. $\endgroup$ – Derek Holt Mar 7 '15 at 9:25
  • $\begingroup$ On a binary alphabet $\lbrace 0,1 \rbrace$, you can block infinite words by prohibiting $\lbrace 0, 1^m \rbrace$ or by $\lbrace 01, 0^m, 1^n \rbrace$. If the shortest prohibited word is $00$ or has length at least $3$ you can reduce to the case of a larger alphabet. $\endgroup$ – Douglas Zare Mar 7 '15 at 9:27
  • $\begingroup$ @JeremyRickard, indeed, thank you. Fixed. $\endgroup$ – Fedor Petrov Mar 7 '15 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.