Periodic sequences on finite alphabet

Question

Let $\Sigma=\{A,B,C\}$ be an alphabet, and let $\Sigma^{\mathbb{N}}$ be the set of infinite sequences on $\Sigma$ (ie $ABCBCCCBABC...$). By outside conditions, I have several subsequences that are disallowed, namely $AA, BB, CC, ABAB, ACAC, BABA, BCBC, CACA, CBCB, ACB, BAC, CBA$, and I wish to show that all $\sigma\in\Sigma^{\mathbb{N}}$ are eventually periodic. I'd like to know if there are any results on this subject or any suggestions of ways to proceed on a proof.

Previous attempts: My original thought was that I could create a counterexample by making blocks of length 3 to represent 0 and 1 and then to create some sort of irrational decimal with these (say $\pi$ in binary, for example). I went through the allowable combinations and found that this was impossible. Doing this again for larger blocks seems possible, but I'd like to find some general results on this problem.

(Apologies for the tags, I can't quite figure out what good ones are for this question.)

Answer 1

Building on Gerry Myerson's answer...

The set of forbidden subsequences is stable under the substitutions given by the 3-cycle $\tau=(ACB)$. In other words, if $X_1X_2\ldots X_k$ is forbidden, then so is $\tau(X_1)\tau(X_2)\ldots\tau(X_k)$. Hence those 5 remaining cases compress to 1: two of them are in the orbit of the initial sequence $AC$ handled by Gerry, and the remaining three form another orbit.

Let's pick the initial sequence $AB$ from that other orbit. It cannot continue with $B$. If the third letter were $A$, then there would be no legal alternatives for the fourth, so the sequence must begin $ABC$. Here the last pair $BC=\tau^2(A)\tau^2(B)$, so the same argument (apply $\tau^2$ to the previous one) forces the next letter to be $\tau^2(C)=A$, and on it goes cyclically: the only alternative for the next letter is gotten from the previous one by applying $\tau^2$. As $\tau$ is of order 3, we get the repeating cycle of length 3.

Answer 2

I can see a brute-force approach to (trying to) prove it. Assume your infinite sequence starts AC. The next term must be A, so ACA. The next term must be B, so ACAB. Now it starts to get tricky. It seems the 5th term can be A or C, but if you use A then there's no valid 6th term, so in fact the 5th term must be C, so ACABC. The 6th term could be A or B, but if it's B there's no valid 7th term, so ACABCA. The 7th term could be B or C, but if it's C there's no valid 8th term, so ACABCAB. Now we're back to where we were after 4 terms, so we must repeat CAB forever hereafter.

So that takes care of sequences starting AC. You've got 8 other cases to try (well, 5, since AA, BB, and CC are non-starters).

Answer 3

Using Gerry Myerson's idea of brute-forcing it, I wrote a (Python) program to do exactly that. What I found is that you are actually correct; all infinite sequences are periodic. Only if you allow finite sequences do you get non-periodic sequences, but in all cases, it's the very last character that breaks the periodicity. Also, the periodicity is always of the form "...ABCABCABC...". Hopefully that will be enough for someone else to give a more abstract proof.

And, for the curious, here is my code:

def do(l, s, d, a, infin = 1):

    win = []

    if len(s) > l:
        for i in xrange(1, len(s)/2):
            if s[-i:] == s[-i*2:-i] or (infin and i<len(s)/2 and s[-i-1:-1] == s[-i*2-1:-i-1]):
                return []
        return [s]

    for k in a:

        s2 = s + k
        nope = 0

        for j in d:
            if len(s2) >= len(j) and s2[-len(j):] == j:
                nope = 1

        if nope == 0:
            win.extend(do(l, s2, d, a, infin))

    return win

def run(length, infin, start = "", disallowed="AA,BB,CC,ABAB,ACAC,BABA,BCBC,CACA,CBCB,ACB,BAC,CBA", add="A,B,C"):
    d = disallowed.split(",")
    a = add.split(",")
    win = []
    for i in a:
        s = start+i
        win.extend(do(length, s, d, a, infin))
    return win

length sets the cut-off point for how far to look and setting infin to $0$ effectively makes it check infinite sequences.

Answer 4

Here's a marginally less brute-force approach that provides a somewhat different viewpoint. Given a valid infinite sequence, it's clear that each of $A$, $B$, $C$ occurs infinitely often. We check that the distance between any two consecutive occurrences of $A$ is at most $3$ (where the distance is computed coordinate-wise, so for example the distance between the $A$s in $ABCBAB$ is $4$). If the distance between two consecutive $A$s is $4$, then since $BB$ and $CC$ are disallowed, your configuration must be one of $ABCBA$ and $ACBCA$, neither of which is valid. If the distance between two consecutive $A$s is greater than $4$, then between them must occur one of $BB$, $CC$, $BCBC$, and $CBCB$, so that's no good either.

By symmetry, the distance between any two consecutive $A$s, $B$s, or $C$s is at most $3$. But after each letter has occurred at least once, this distance cannot be $2$ (or obviously $1$). If the distance between two $A$s is $2$, then there's some unique character between them (say $B$). But then the distance between the $C$ before this configuration and the $C$ after it is at least $4$, which we know to be impossible.

Thus, past a certain point the distance between any two consecutive occurrences of the same character is exactly $3$, making the sequence eventually periodic.

Answer 5

It is seen that the restrictions are cyclically-invariant, so it's better to specify the sequence of symbols $\{A,B,C\}$ using some "delta coding": say, $\{-, =, +\}$ where $+$ means "change to the symbol to the right" (cyclically) ($A \to B$, $B \to C$, $C \to A$), $=$ means "repeat same symbol", $-$ means "symbol to the left". This (together with the first symbol) fully specifies any sequence. For example, instead of $ABBCBAC$ we would write $A+=+--$

Actually the first three disallowed subsequences (AA, BB, CC) implicitly disallow the $=$ symbol (repetitions are forbidden), so we can restrict ourselves to $\{- +\}$, or $\{0,1\}$.

The rest of restrictions disallow the following subsequences:

$ ABAB, BCBC, CACA \equiv 101$

$ ACAC, BABA, CBCB \equiv 010$

$ CBA, BAC, ACB \equiv 00$

So we are left with the much simpler problem of building a sequence of $\{0,1\}$ with the subsequences $00, 010, 101$ disallowed. It's easy to see that the only allowed infinite sequences are:

$11111 \cdots$ and $011111 \cdots$

So that, after the first two symbols, the sequence will repeat cyclically "to the right" ( ....ABCABCABC...)

Specifically the only possible infinite sequences are

ABCABCABC....   (A111111....)

BCABCABC....    (B111111....)

CABCABC....     (C111111....)

ACABCABC....    (A0111111....)

BABCABCABC....  (B0111111....)

CBCABCABC....   (C0111111....)