<p>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...?   </p>

CC BY-SA 4.0
2018-09-04T07:01:51.337Z
2018-09-04T07:01:51.337Z
Zed
<p>I'm searching for a reference for the following property:</p>

<p><strong>Fact.</strong>  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:</p>

<ul>
<li>$w = z \cdot z'$</li>
<li>$v \cdot u = (z' \cdot z)^c$</li>
<li>$u \in (z \cdot z')^* \cdot z$ and $v \in z' \cdot (z \cdot z')^*$</li>
</ul>

<p><em>Proof.</em> Most of the statement is given by, e.g., Lothaire 83:
<a href="https://i.sstatic.net/sQNvA.png"><img src="https://i.sstatic.net/sQNvA.png" alt="Lothaire"></a>
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 <em>not</em> a permutation, that is, $z_\text{s} = \varepsilon$. $\square$</p>

<reference-request><co.combinatorics><fl.formal-languages>
If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$
Michaël Cadilhac
# If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$

(Asked by: username_0 on 2017-01-24)

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](https://i.sstatic.net/sQNvA.png)](https://i.sstatic.net/sQNvA.png)
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$

**Tags:** reference-request, co.combinatorics, fl.formal-languages

---

## 1 answers

### Answer by username_1 on 2018-09-04. Score: 2

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...?


---

