How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?

Question

How to prove that a string, s is made up of n > 1 subsequences occurring some arbitrary number of times using concatenation and stripping first and last character? E.g s = xyzxyz, subsequence is xyz and it occurs 2 times. The solution is to concatenate the same string e.g. xyzxyzxyzxyz and then strip the first and last character to get yzxyzxyzxy, then you find s (xyzxyz) inside that.

Other examples:

1. The word Table does not have a subsequence so the above method will give: Table||Table -> TableTable -> ableTabl -> which does not contain Table so Table does not contain a subsequence
2. The word mmebmmebmmeb -> has to return true with the above method because it contains mmeb repeated 3 times. So, mmebmmebmmeb || mmebmmebmmeb -> mmebmmebmmebmmebmmebmmeb -> (strip first and last) mebmmebmmebmmebmmebmme which contains mmebmmebmmeb (meb**mmebmmebmmeb**mmebmme)

My thought was to assume that there is at least one character in s that will invalidate the occurrence of a subsequence. E.g. instead of xyzxyzxyz (xyz occurring three times) we have xyzxyzxya where a is the wrong char. Now we assume that in yzxyzxyaxyzxyzxy (after concatenation and stripping first and last) that the string s does exist which should be a contradiction - but I am stuck.

Could someone give me a formal mathematical proof?

Looked at this for ideas: How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?

Answer 1

Let us first state the theorem that we are trying to prove.

Theorem. Let $w \neq \epsilon$ be a word. Then $w^2 = xwy$ for $x,y \neq \epsilon$ if and only if $w = z^p$ for some $p > 1$.

Proof. Let us first suppose that $w = z^p$ for some $p > 1$. Then $w^2 = z^{2p} = zwz^{p-1}$, where $z,z^{p-1} \neq \epsilon$.

In the other direction, write $w = w_1w_2$, where $|xw_1| = |w_2y| = |w|$. Since $x,y \neq \epsilon$, we see that $|w_1|,|w_2| < |w|$. We have $ww = xw_1w_2y$ implies that $w = xw_1 = w_2y$, and so $x = w_2$ (since $|x| = |w|-|w_1| = |w_2|$). In other words, $w = w_2w_1$.

Now let $w = \sigma_0 \ldots \sigma_{n-1}$, and let $|w_2| = m$. Note that since $|w_1|,|w_2| < n$, we have $0 < m < n$. The equality $w = w_2w_1$ implies (check!) that $\sigma_i = \sigma_{i+m \bmod{n}}$. Let $g$ be the GCD of $m$ and $n$; note that $g < n$. It is known that $g = am + bn$ for some integers $a,b$, and so $\sigma_i = \sigma_{i+bm \bmod{n}} = \sigma_{i+g \bmod{n}}$. Since $g \mid n$, this implies that $w = (\sigma_1 \ldots \sigma_g)^{n/g}$, where $n/g > 1$.