Infinite sequence avoiding a countable set of words

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?

• Is your set of words decidable? – Maxime Lucas Mar 6 '15 at 13:59
• 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! – Derek Holt Mar 6 '15 at 14:32
• It is easy to avoid some infinite sets of words. It is impossible to avoid others. – Douglas Zare Mar 6 '15 at 14:59
• 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. – Elisabeth Fink Mar 6 '15 at 15:13

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)$.

• 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. – Elisabeth Fink Mar 7 '15 at 7:35
• 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$. – Jeremy Rickard Mar 7 '15 at 9:15
• I guess I must have completely misinterpreted the question, which does not mention subwords at all. – Derek Holt Mar 7 '15 at 9:25
• 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. – Douglas Zare Mar 7 '15 at 9:27
• @JeremyRickard, indeed, thank you. Fixed. – Fedor Petrov Mar 7 '15 at 11:57