# Combinatwordsing on sunday…

From S. Tringali. link Let $\Sigma$ be a set and denote by $\Sigma^*$ the free monoid on $\Sigma$, which we write, as usual, in multiplicative notation. Let $\varepsilon$ be the identity element of $\Sigma^*$ and $|\cdot|$ the function $\Sigma^* \to \mathbb N$ mapping a word $w$ to its length (here, $\mathbb N$ means the non-negative integers). Then, pick $w \in \Sigma^+$.

1. Prove that for every $k \in \mathbb N$ there exists at most one pair $(e,v) \in \mathbb N \times \Xi^*$ such that $v^e = w$ and $|v| = k$.

2. Prove the following: If $v_1, v_2 \in \Xi^*$ and $e_1, e_2 \in \mathbb N^+$ are such that $v_1^{e_1} = v_2^{e_2} = w$, then there exists $v \in \Xi^*$ such that $w = v^{\text{lcm}(e_1, e_2)}$ and $v_i = v^{\text{lcm}(e_1, e_2)/e_i}$.

Proof.

1. If $v_1^{e_1} = v_2^{e_2}$ and $|v_1|=|v_2|$ then $e_1=e_2$ hence $v_1=v_2$.

2. $v_1^{e_1}=v_2^{e_2}$ for $e_1, e_2\geq 1$. By symmetry wlog $e_1 \leq e_2$ and $|v_1|\geq|v_2|$.
It must be $v_1=v_2x$ for some $x\in\Sigma^*$.
So $v_1^{e_1}=(v_2x)^{e_1}=v_2^{e_2}$, then $(xv_2)^{e_1-1}x=v_2^{e_2-1}$, right multiply by $v_2$ to get $(xv_2)^{e_1}=v_2^{e_2}$.
That is $(v_2x)^{e_1}=(xv_2)^{e_1}\Rightarrow v_2x = xv_2\Rightarrow v_1=v_2x=xv_2$.
From this we have $v_1v_2 = (v_2x)v_2 = v_2(x v_2) = v_2v_1$.
Now, since $v_1 v_2 = v_2 v_1$ we set $n:=|v_1v_2|$ and observe by induction that
if $n=2$ then $v_1=v_2$ and the thesis follows.
Otherwise let $n>2$. There must be a word $y\in\Sigma^*$ s.t. $v_1=v_2y=yv_2$.
Observe $|v_2y|=v_1<|v_1v_2|=n$.
Apply induction hypothesis we see that there must be a word $v\in\Sigma^+$ and integers $a, b>0$ s.t. $v^a=v_2$ and $v^b=y$.
Hence $v_1=v^{a+b}$ and $v_2=v^b$. We pick the longest such $v$.
From $|v|\mid |v_1|, |v_2|$ it must be $|v|=\text{gcd}(|v_1|, |v_2|)$, since otherwise we pick $v^{\text{gcd}(|v_1|, |v_2|)/|v|}$ against the maximality of $|v|$.
Moreover if we set $a':=a+b, b':=b$ observe $e_1a'=e_2b'$ and denote by $l$ such a number.
$l$ is a multiple of both $e_1$ and $e_2$.
Since $v_1^{e_1}=v^l=v_2^{e_2}$ and we picked the longest $v$, there cannot be a smaller such $l$, since otherwise we pick $v^{l/ \text{lcm}(e_1, e_2)}$.
This imply $l=\text{lcm}(e_1, e_2)$, that is $a'=\frac{\text{lcm}(e_1,e_2)}{e_1}$ and $b'=\frac{\text{lcm}(e_1,e_2)}{e_2}$.Q.E.D.