MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Is $A_n$ correct? It isn't a multiset of pairs like the others. – Brendan McKay Jul 27 '12 at 10:11
@Brendan, you are right, I have made it a pair. In fact $A_n$ is redundant because the sum $s_1+...+s_n$ is already encoded in $A_1$. – Mark Sapir Jul 27 '12 at 10:16
How is this question related to the previous one? – Mikael de la Salle Jul 27 '12 at 15:24
@Mikhael: Consider a word $w(A,B)=A^{s_1}BA^{s_2}B...A^{s_n}b$ where some $s_i$ may be 0. Let $A$ be the diagonal matrix $diag(a,b,c)$, and $B$ be a generic matrix as in the previous question. Monomials in $f_w$ correspond to sequences of numbers $1,2,3$: for every sequence $i_1...i_n$ we get a monomial $a^pb^qc^rB[i_1,i_2]B[i_2,i_3]...B[i_n,i_1]$ where $p,q,r$ are easy to define. Now if you collect all terms containing the same product $B[i_1,i_2]...B[i_n,i_1]$, its coefficient is a polynomial in $a,b,c$. For sequences $1,2,3,...,3$, $1,1,2,3,...,3$,... you get polynomias as here. – Mark Sapir Jul 27 '12 at 15:41
It means that if $w$ was determined by these multisets (=polynomials), then the answer to the previous question would be "yes". Now that we know that $w$ is not determined, one needs to consider different sequences of $1,2,3$. In the prev. answer the sequences were $(1,2,3,...,3)$, $(1,1,2,3,...,3)$, and so on. It did not come up nicely in LaTeX. – Mark Sapir Jul 27 '12 at 15:45
up vote 5 down vote accepted

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.

share|cite|improve this answer
Yes, it is correct. I also found that the Prouhet-Morse-Thue word $p_{16}$ is not recovered. Thank you! – Mark Sapir Jul 27 '12 at 15:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.