an operation on binary strings - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T13:24:24Z http://mathoverflow.net/feeds/question/84824 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84824/an-operation-on-binary-strings an operation on binary strings James Propp 2012-01-03T18:48:25Z 2012-01-10T18:49:08Z <p>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. </p> <p>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.</p> <p>Has this operation been studied before?</p> http://mathoverflow.net/questions/84824/an-operation-on-binary-strings/84880#84880 Answer by Benjamin Young for an operation on binary strings Benjamin Young 2012-01-04T12:39:42Z 2012-01-04T14:04:42Z <p>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:</p> <ul> <li>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. </li> <li>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 <a href="https://oeis.org/A027375" rel="nofollow">https://oeis.org/A027375</a>.</li> <li>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.</li> </ul> <p>None of the other obvious statistics that describe this map are in the OEIS yet.</p> <p>Here are naive python implementations of $B_L, B_R, B_L^{-1}, B_R^{-1}$ if you want to check these assertions.</p> <pre><code>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) </code></pre> http://mathoverflow.net/questions/84824/an-operation-on-binary-strings/84929#84929 Answer by Mark Sapir for an operation on binary strings Mark Sapir 2012-01-05T03:08:13Z 2012-01-05T03:08:13Z <p>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. </p> http://mathoverflow.net/questions/84824/an-operation-on-binary-strings/85353#85353 Answer by Aaron Meyerowitz for an operation on binary strings Aaron Meyerowitz 2012-01-10T18:49:08Z 2012-01-10T18:49:08Z <p>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.$ </p> <p>It turns our that $RRRRRLRLLLLLL$ has an orbit of size $473$ and that is the longest orbit for any string of length 13.</p>