# an operation on binary strings

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?

-
Ultimately it does not matter, but I think it would be nicer to start by reading the symbol on the right (which immediately becomes the leftmost symbol of the next string.) Otherwise we have some initial substring ($L^kR$ for some $k \ge 0$) which is invariant and then the rest of the word which bounces according to the rule I suggest. The description with circular words makes some sense but it has to be (oriented) circular words with a distinguished start letter. After all, $RRLL$ and $RLLR$ behave differently. –  Aaron Meyerowitz Jan 10 '12 at 21:52

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)

-
Do I understand it correctly from the code that your $B_R$ reads things from the right but still writes the result from the left? (It is not quite clear from the word description of $B_R$, and was not my naive guess about it before reading the code.) –  Vladimir Dotsenko Jan 4 '12 at 13:37
Yes, you understand it correctly. I'll edit the description so that it is less ambiguous. Thanks. –  Benjamin Young Jan 4 '12 at 13:55
I mean, it's sort of odd that a procedure for reading a string at both ends should always start at the left end. That's the only reason I even thought about $B_R$ at all. It also might be interesting to think about reversing the string you write down. –  Benjamin Young Jan 4 '12 at 14:03
Great, thanks a lot! –  Vladimir Dotsenko Jan 4 '12 at 15:24
Hi Ben! This is a really silly remark but you're missing out on perhaps the best piece of Python syntax, negative indexing: pyfaq.infogami.com/what-s-a-negative-index –  Dan Petersen Jan 11 '12 at 7:17
show 1 more comment

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.

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