8

4

Here is a more general (and possibly more clearly stated) combinatorial version of this question, than this question. Let $u$ be a sequence of 0 and 1 of length $n$. Let $p,q,r$ be three natural numbers, $p+q+r=n$, and $w$ be a sequence of $a, b, c$ started with $p$ $a$'s, then $q$ $b$'s, then $r$ $c$'s. Define a monomial $m(u;p,q,r)$ in $a,b,c$ as the product of all letters of $w$ such that the corresponding entries of $u$ are equal to 1. For example, if $u=101001, p=1, q=2, r=3, w=abbccc$, then $m(u;p,q,r)=abc$ because the first letter of $w$ is $a$, the third letter is $b$ and the sixth letter is $c$, and 1,3, 6 are the places in $u$ where $1$ occurs. Now define a polynomial $P(u;p,q,r)$ as the sum of all $m(u',w)$ for all cyclic shifts $u'$ of $u$. Let $S(u)$ be the array of all polynomials $P(u;p,q,r)$ for all $p,q,r$ with $p+q+r=n$ (indexed by the triples $(p,q,r)$).

Question Does the array $S(u)$ determine $u$ up to a cyclic shift?

The answer is "yes" for all $n\le 15$. A positive answer would imply a positive answer to this previous question for positive words. This question is a version of the present question when we only consider $q=1$. In that case, as Jyrki Lahtonen showed the answer is "no" even for $n=7$.

flag
Are we told the $p,q,r$ values for the polynomials in $S(u)$? Also, do we get their multiplicities (i.e., is $S(u)$ actually a multiset)? – Brendan McKay Aug 7 at 0:41
@Brendan: You are right, in fact $S(u)$ is an array of polynomials indexed by $p,q,r$. I will fix the question. Thanks! – Mark Sapir Aug 7 at 0:57
Let an $(a,b)$-brick be a string of $a\gt 0$ ones followed by a string of $b\gt 0$ zeros. Except for $0^n$ and $1^n$, all circular sequences can be uniquely cut into bricks. I didn't write it down in detail, but I'm pretty sure that these polynomials determine the multiset of bricks used by the mystery string. What I don't see is how to determine the order in which the bricks are put together. – Brendan McKay Aug 9 at 0:18
@Brendan: The multiset of bricks is certainly determined. Indeed, if the brick is $111100000$ (4 1s and 5 0's) then consider the pattern $aaaabbbbbc....c$. In the polynomial, look at the coefficient of the monomial $a^4c^{n-4}$. It is the number of occurrences of the brick $111100000$. Right? I think that much more information about the bricks is recoverable. But I cannot so far decide whether the whole world is. – Mark Sapir Aug 9 at 0:45
No, the number of occurrences of the brick 111100000 is not the coefficient of $a^4 c^{n-4}$. Why do you think the $c$ part has $n-4$ ones? The length of the longest sequence of 1s is the greatest $p$ such that for some $q,r$, $m(u;p,q,r)$ has a term with $a^p$. Then amongst those look for the greatest $q$ such that there is one with a term $a^pb^0$. That gives you the $(p,q)$-bricks where $p$ is maximal and subject to that $q$ is maximal. Then you can start working downwards to count smaller bricks, subtracting off the contributions from the larger bricks you already counted. – Brendan McKay Aug 10 at 15:25
show 1 more comment

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.