Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
My intuition is actually that periodicity is not forced, but that's all it is; intuition, not a proof. –  El'endia Starman Jul 15 '11 at 6:11
    
Yes, it certainly seems like there's enough freedom here to wrangle some counterexample. If so, then there's probably some other limitation in the problem that gave me this coding that I've overlooked. No matter what happens, I'd love to hear about general results in this area. –  Jadmrial Jul 15 '11 at 6:13
    
I had the same intuition, but then I tried to find a counterexample, and wound up with the fragment of a proof I posted as an answer. –  Gerry Myerson Jul 15 '11 at 6:20
    
Combinatorics on words would be a good buzzword. Several people at our department work in the area. I don't know if it would make a good tag given that there is relatively little traffic that would fit under this umbrella. I did add the (combinatorics) tag. –  Jyrki Lahtonen Jul 15 '11 at 6:47
add comment

5 Answers 5

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
2  
Because of the built in cyclic symmetry $A\mapsto B\mapsto C\mapsto\ $ one only has to try the two initial segments $AC$ and $AB$. –  Christian Blatter Jul 15 '11 at 8:03
add comment

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.

share|improve this answer
    
You mean accurate and not, necessarily, abstract. –  AD. Jul 15 '11 at 7:07
    
@AD: What do you mean by "accurate"? –  El'endia Starman Jul 15 '11 at 7:10
    
Well maybe your code is a proof. Why don't you add that? (By accurate I mean that you can not refer to output of a program as a "proof") –  AD. Jul 15 '11 at 7:15
    
Okay I'll add the program. Here's hoping the white-space transfers correctly... –  El'endia Starman Jul 15 '11 at 7:16
    
Just to notify...@AD. –  El'endia Starman Jul 15 '11 at 7:26
add comment

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.

share|improve this answer
add comment

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....)
share|improve this answer
    
Thanks, this seems like a very nice way to go about it. –  Jadmrial Jul 16 '11 at 18:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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