an operation on binary strings - MathOverflow

an operation on binary strings

2012-01-03T18:48:25Z

Recently, as part of some joint research, Tom Roby was led to a curious operation on strings of L's and R's which he calls "bounce-reading": We start by reading the string at the left. When the symbol we have just read is an L, the next symbol we read is the leftmost unread symbol; but when the symbol we have just read is an R, the next symbol we read is the rightmost unread symbol. For instance, if our string of L's and R's is LLRRLRLR, we read the positions in the order 1,2,3,8,7,4,6,5, obtaining the bounce-reading LLRRLRRL.

It may be more natural to think of this as an action on circular words; when we read a letter, we delete it, close up the circle, and move either to the left or the right of the deletion-point.

Has this operation been studied before?

Answer by Benjamin Young for an operation on binary strings

2012-01-04T12:39:42Z

Well, it has now, since I just sank my morning into studying it. I sure am a sucker for a naive combinatorics problem. Here's what I know, or can conjecture:

The map you describe is a bijection on words of length $n$, because it's easy to write down its inverse. I've included python code below.
Let $B_L$ be the bounce-reading algorithm. Let $B_R$ be the bounce-reading algorithm with the following change: replace the phrase "we start by reading the string at the left" with "we start by reading the string at the right". Then $B_LB_R^{-1}(w)$ seems to shift $w$ cyclically by one letter. Sometimes the shift is the left, and sometimes to the right; which of these things happens depends on $w$ in a manner which I don't understand. I noticed this because the maximal orbit sizes of $B_LB_R^{-1}(w)$ for each $n$ seem to match the OEIS sequence https://oeis.org/A027375.
Let $S_n$ be the set of words $w$ of length $n$ for which $B_L(w) = B_R(w)$. Then the sequence ${|S_{n+1}| - |S_n|}$ seems to be the Fibonacci numbers, at least for $n\geq 2$. This probably means $S_n$ has some nice structure.

None of the other obvious statistics that describe this map are in the OEIS yet.

Here are naive python implementations of $B_L, B_R, B_L^{-1}, B_R^{-1}$ if you want to check these assertions.

def bounce_left(w):
    if len(w) == 1:
        return w
    leftchar = w[0]
    x = w[1:]
    if(leftchar == "L"):
        return leftchar + bounce_left(x)
    else:
        return leftchar + bounce_right(x)

def bounce_right(w):
    if len(w) == 1:
        return w
    last_index = len(w) - 1
    rightchar = w[last_index]
    x = w[:last_index]
    if(rightchar == "L"):
        return rightchar + bounce_left(x)
    else:
        return rightchar + bounce_right(x)


def unbounce(w):
    if w == "":
        return ""
    output = ""
    n = len(w) - 1
    for index in reversed(range(n)):
        if w[index] == "L":
            output = w[index+1] + output
        else:
            output = output + w[index+1]
    return output

def unbounce_left(w):
    return unbounce("L" + w) 

def unbounce_right(w):
    return unbounce("R" + w)

Answer by Mark Sapir for an operation on binary strings

2012-01-05T03:08:13Z

It may be convenient to consider an extension of the map to words in a double alphabet $A=\{L,R\}\times \{L,R\}$ or, equivalently, pairs of words in $\{L,R\}$ of the same length. (Your situation is obtained when you consider a pair: a word and the reverse word.) The advantage of the extension is that then the map is given by a Mealy automaton. Although I do not know whether exactly this transformation was studied, groups generated by such transformations have been of course studied as "automaton groups". See papers and books by Grigorchuk, Nekrashevych and others.

Answer by Aaron Meyerowitz for an operation on binary strings

2012-01-10T18:49:08Z

I suspect that it has not been studied, but it should be! I base this on the fact that various statistics one might expect to be associated with it do not appear in the OEIS (even with an appeal to superseeker@oeis.org). For example $$2, 3, 6, 7, 19, 27, 36, 79, 130, 384, 473, 710, 2903, 4197$$ gives the maximum size orbit for strings of lengths up to $16.$

It turns our that $RRRRRLRLLLLLL$ has an orbit of size $473$ and that is the longest orbit for any string of length 13.