I'm searching for a reference for the following property:

Fact. Let $u, v \in A^*$. Write $w$ for the primitive root of $u\cdot v$, i.e., $u\cdot v = w^c$. There are unique words $z, z'$ such that:

  • $w = z \cdot z'$
  • $v \cdot u = (z' \cdot z)^c$
  • $u \in (z \cdot z')^* \cdot z$ and $v \in z' \cdot (z \cdot z')^*$

Proof. Most of the statement is given by, e.g., Lothaire 83: Lothaire What is left to show is the last point. From $u \cdot v = (z\cdot z')^c$, we obtain that $u = (z\cdot z')^k\cdot z_{\text{p}}$ and $v = z_{\text{s}}\cdot z' \cdot (z\cdot z')^{k'}$ where $z = z_{\text{p}}\cdot z_{\text{s}}$ (the case where $u$ ends with a prefix of $z'$ is similar). Since $v \cdot u = (z' \cdot z)^c$, it holds that $$z' \cdot z = z_{\text{s}}\cdot z' \cdot z_{\text{p}}\enspace.$$ As $z' \cdot z$ is primitive, all of its permutations are distinct, hence the right-hand side of the previous equation is not a permutation, that is, $z_\text{s} = \varepsilon$. $\square$


The full statement (including the last point) seems to follow directly from the proof of Proposition 1.3.3 in (Lothaire '83). The last point is part of the proof: using the notation in the original post, the proof states that $u = (z \cdot z')^{k_1} \cdot z$ and $v = z' \cdot (z \cdot z')^{k_2}$ for some $k_1$ and $k_2$ such that $k_1+k_2+1 = c$. Perhaps the proof of this proposition could be cited...?


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.