A combinatorial question - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T17:00:49Z http://mathoverflow.net/feeds/question/103288 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103288/a-combinatorial-question A combinatorial question Mark Sapir 2012-07-27T09:36:53Z 2012-07-27T15:06:30Z <p>This possibly easy question is related to <a href="http://mathoverflow.net/questions/102933/reconstructing-a-word" rel="nofollow"> this one. </a> Let $s_1,...,s_n$ be a sequence of natural numbers (some of them may be equal to 0). Consider the following sequence of multisets of 2-vectors (each vector is counted with its multiplicity) of natural numbers $A_1=\{ (s_1,s_2),...(s_n,s_1)\}$, $A_2=\{(s_1+s_2,s_3),...,(s_n+s_1,s_2)\}$, ...,$A_n=\{(s_1+...+s_n,0)\}$. Note that each multiset is closed under taking cyclic shift on the set of indices $1,2,...,n$.</p> <p><b> Question</b> Does this sequence of multisets determine the sequence $s_1,...,s_n$ up to a cyclic shift?</p> <p>In particular, is the <a href="http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence" rel="nofollow">Prouhet-Morse-Thue</a> sequence reconstructible (up to a cyclic shift)?</p> <p><b> Example </b> If we encode every pair $(i,j)$ by a monomial $a^ib^j$ in commuting variables $a,b$, and interpret the multiplicity as a coefficient, we encode every multiset as a polynomial in $a,b$ over $\mathbb{Z}$. Here are the first 7 polynomials corresponding to the Prouhet-Morse-Thue word of length $8$ p_8="10010110":</p> <p>$$3a+1+3b+ab\\ 3a+b+3ab+{a}^{2}\\ 2ab+2a+2{a}^{2}b+2{a}^{2}\\ 2{a}^{2}+2\,ab+2{a}^{2}b+2\,{a}^{3}\\ 3{a}^{2}b+3{a}^{3}+{a}^{3}b+{a}^{2}\\ 3{a}^{3}b+3{a}^{3}+{a}^{4}+{a}^{2}b\\ 4{a}^{4}+4{a}^{3}b$$</p> <p>Does this sequence of polynomials determine the word $p_8$ up to a cyclic shift? <b> Update </b> Answer for $p_8$ is "yes" (computed using Maple).</p> http://mathoverflow.net/questions/103288/a-combinatorial-question/103318#103318 Answer by Jyrki Lahtonen for A combinatorial question Jyrki Lahtonen 2012-07-27T15:00:32Z 2012-07-27T15:06:30Z <p>Unless I made mistake a counterexample is formed by the binary $m$-sequence of length 7 $s=(1,0,0,1,0,1,1)$ and its reversal $\tilde{s}=(1,1,0,1,0,0,1)$ that is not a cyclic shift of $s$. Both lead to the sequence of generating functions $1+2a+2b+2ab$, $2a+b+a^2+2ab+a^2b$, $a+a^2+2ab+a^3+2a^2b$, $a^2+ab+2a^3+2a^2b+a^3b$, $2a^3+2a^2b+a^4+2a^3b$ and $3a^4+4a^3b$.</p> <p>The $m$-sequences are examples of de Bruijn -sequences. That is binary sequences of length $2^n-1$ such that every sequence of $n$ bits (with the exception of $n$ zeros) occurs exactly once in the cycle. This is, of course, then a natural source for an eventual counterexample as the condition is automatically satisfied for $A_j, j\lt n.$ Length 7 is the shortest, where not all de Bruijn sequences are cyclic shifts of each other. </p> <p>An $m$-sequence is generated by a linear feedback shift register that has a primitive polynomial of degree $n$ from the ring $\mathbb{F}_2[x]$ as a feedback polynomial. If you decimate an $m$-sequence with a decimation exponent $d$, $\gcd(d, 2^n-1)=1,$ by cyclically taking every $d^{th}$ member, you get another $m$-sequence. Therefore for larger $n$ the number of non-cyclically equivalent $m$-sequences increases. For example, the sequence $s$ is generated by the feedback polynomial $x^3+x^2+1$, or equivalently by the given first 3 bits and the recurrence relation $$s_n=s_{n-3}+s_{n-2}\pmod2$$ with subscript arithmetic done modulo seven. The reversed sequence $\tilde{s}$ is similarly generated by the reciprocal polynomial $x^3+x+1$.</p> <p>I dare not guess yet, whether all $m$-sequences of a given length give rise to the same sequence of multisets.</p>