periodic tail of a periodic word

117 Views Asked by At

This problem was motivated by my work on this question

$\qquad$ Periodicity of words

Problem:

Given a finite alphabet, let $w = u^n,\;$where $n > 1,\;$and $u\;$is a non-periodic word.

Prove or disprove:$\;$If $w\;$has a periodic tail $v\;$such that $|v| > |u|,\;$then $v=u^k,\;$for some $k>1$.

Remarks:

It seems like it should be true, but I don't see an instant proof.

Suppose the claim is false.

Let $n\;$be the least positive integer for which there is a counterexample.

If $|v|\;$is a multiple of $|u|,\;$say $|v|=k|u|,\;$then it's automatic that $v=u^k$, and $k > 1$.

Thus, for our assumed counterexample, $|v|\;$is not a multiple of $|u|$.

In particular, we must have $|u| > 1$.

Since $n\;$is least, it follows that $(n-1)|u| < |v| < n|u|$.

Let $p\;$be the period of $v$.

It's clear that $p > 1,\;$else $u\;$is periodic.

Also, $p\;$can't be a multiple of $|u|,\;$else $v\;$would be power of $u$,

That's about as far as I've got.

Maybe I'm missing something simple.

Also, since this is not an area which I know much about, I wouldn't be surprised if this is a well known result, or a standard exercise. If so, please advise, and I'll delete the question.

Thanks.