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$
4
  • $\begingroup$ Is your set of words decidable? $\endgroup$ Mar 6, 2015 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, 2015 at 14:32
  • 1
    $\begingroup$ It is easy to avoid some infinite sets of words. It is impossible to avoid others. $\endgroup$ Mar 6, 2015 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$ Mar 6, 2015 at 15:13

1 Answer 1

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$
6
  • $\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$ Mar 7, 2015 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$ Mar 7, 2015 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, 2015 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$ Mar 7, 2015 at 9:27
  • $\begingroup$ @JeremyRickard, indeed, thank you. Fixed. $\endgroup$ Mar 7, 2015 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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