5
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Is $A_n$ correct? It isn't a multiset of pairs like the others. $\endgroup$ Jul 27 '12 at 10:11
  • $\begingroup$ @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$. $\endgroup$
    – user6976
    Jul 27 '12 at 10:16
  • $\begingroup$ How is this question related to the previous one? $\endgroup$ Jul 27 '12 at 15:24
  • $\begingroup$ @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. $\endgroup$
    – user6976
    Jul 27 '12 at 15:41
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Jul 27 '12 at 15:45
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, it is correct. I also found that the Prouhet-Morse-Thue word $p_{16}$ is not recovered. Thank you! $\endgroup$
    – user6976
    Jul 27 '12 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy