A perfect shuffle of two words $u=a_{1}a_{2} \cdots a_{n}$ and $v=b_{1}b_{2} \cdots b_{n}$ where $a_{i}$'s and $b_{j}$'s are letters from the alphabet $\Sigma$ is defined as $u \diamond v=a_{1}b_{1} \cdots a_{n} b_{n}$.

It is obvious that if for two primitive words $u$ and $v$, their shuffle $u \diamond v$ need not be primitive. (e.g., for $u=abc$, $v=cab$, $u \diamond v=acbacb$ is not primitive.

So, my question is is there any result that proves that under certain conditions set of all primitive words is closed under this perfect shuffle? (There are results in the literature that talks about square-free shuffle but not primitivity, at least I didn't come across any.)

Please help.


I am not aware of any result of this type. And as your example shows, the set Q of all primitive words is not closed under this operation.

You can find subsets of Q which will result only in primitive words. For example a a+ b b+. The perfect shuffles will be from a a+ (ba)+ b b+ and all of these are primitive again (though not from the original set).

The results on square-free shuffle seem to be not about the perfect shuffle, but the general case. Then they say that at least one square-free word is in the shuffle. That should be easy to show for primtive words. In your example, all resulting words are primitve except the one from the perfect shuffle.


Your Answer

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

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