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$

1 Answer 1

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.

$\endgroup$
3
  • $\begingroup$ Thank you, can you give me the other implication? $\endgroup$
    – asv
    Jan 16, 2020 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, 2020 at 10:22
  • 1
    $\begingroup$ Ok, just shift by $|u|$, right? $\endgroup$
    – asv
    Jan 16, 2020 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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