A combinatorial question

2012-07-27T09:36:53Z

This possibly easy question is related to this one. 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$.

Question Does this sequence of multisets determine the sequence $s_1,...,s_n$ up to a cyclic shift?

In particular, is the Prouhet-Morse-Thue sequence reconstructible (up to a cyclic shift)?

Example 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":

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

Does this sequence of polynomials determine the word $p_8$ up to a cyclic shift? Update Answer for $p_8$ is "yes" (computed using Maple).

Answer by Jyrki Lahtonen for A combinatorial question

2012-07-27T15:00:32Z

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

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.

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

I dare not guess yet, whether all $m$-sequences of a given length give rise to the same sequence of multisets.

A combinatorial question - MathOverflow

A combinatorial question

Answer by Jyrki Lahtonen for A combinatorial question