5
$\begingroup$

Definition. A word $w \in \Sigma^*$ is primitive if $w=u^n \rightarrow n=1$.

Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?

$\endgroup$
5
$\begingroup$

Yes, this is true. The direct implication ($\Rightarrow$) is the hardest to prove, and you will need the following lemma: two words commute if and only if they are powers of the same word (R.C. Lyndon and M.P. Schützenberger, The equation a M = bncp in a free group, Michigan Math. J. 9 (1962) 289-298. Or in this: H. Petersen, On the language of primitive words, Theor. Comp. Sci., 1996 https://doi.org/10.1016/0304-3975(95)00098-4). The rest of the proof should be straightforward enough.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, can you give me the other implication? $\endgroup$ – asv Jan 16 at 10:20
  • 2
    $\begingroup$ By contraposition: assume the word is not primitive, then explicitely construct two cyclic permutations which are equal. $\endgroup$ – integrator Jan 16 at 10:22
  • 1
    $\begingroup$ Ok, just shift by $|u|$, right? $\endgroup$ – asv Jan 16 at 10:26

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.