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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s