## A combinatorial question

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

Is $A_n$ correct?  It isn't a multiset of pairs like the others. – Brendan McKay Jul 27 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 at 10:16
How is this question related to the previous one? – Mikael de la Salle Jul 27 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 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 at 15:45
show 5 more comments

## 1 Answer

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.

-

Yes, it is correct. I also found that the Prouhet-Morse-Thue word $p_{16}$ is not recovered. Thank you! – Mark Sapir Jul 27 at 15:31
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 68, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.921979546546936, "perplexity_flag": "head"}