MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Question is edited Perhaps this formulation is clearer.

It is well known that if a power of a primitive (i.e. not a proper power) word $u$ contains two different occurrences of a word $v$, $|v|>|u|$, then the occurrences are shifts of each other by a multiple of $|u|$ (formally: $u^n\equiv pvq\equiv p'vq', |p|-|p'|\in |u|\mathbb{Z}$). What is the simplest proof of that fact? Is there a simple proof without using Fine-Wilf?

Added. A sketch of a proof. We can assume that $v$ starts with $u$, $v\equiv u^sw$ for $s\ge 1$. Then $v\equiv u^sw\equiv u_1u^sw_1$ such that $|u_1|>0$, $|u_1|+|w_1|=|w|$. Therefore $w\equiv w_2w_1$ for some $w_2$ whence $u^sw_2\equiv u_1u^s$. Then a standard fact from "combinatorics on words" gives that $u_1\equiv xy, w_2\equiv yx, u^s\equiv (xy)^mx$ for some words $x,y$ and some $m\ge 1$ (the fact is: if $pq=qr$, then $p\equiv p_1p_2, q\equiv (p_1p_2)^zp_1, q\equiv p_2p_1$ for some $p_1,p_2,z$). Therefore $u_1u^s\equiv xy(xy)^mx$ is periodic with periods $u$ and $xy$. Its length is at least $|xy|+|u|$. Therefore by Fine-Wilf it is periodic with period $t$ such that $|t|$ divides $|xy|=|u_1|$ and $|u|$. Hence $u$ is a power of a proper subword of $u$, a contradiction.

share|cite|improve this question
Is this really the right condition? 2 things seem wrong: (1) Do you mean $|p|-|p'|\not\in|u|\mathbb Z$? (2) If $v$ has the property in the question, so does any subword of $v$ that is longer than $u$. Can't you just build a prime length $v$ like this, which then can't be a power of any word. – Anthony Quas Mar 22 '13 at 4:17
@Antony: (1) Yes, it is $|p|-|p'|$. Thanks! (2) I will add a sketch of a proof. – Mark Sapir Mar 22 '13 at 4:26
Sorry, but what is that $\equiv$ sign? Equality? – darij grinberg Mar 22 '13 at 4:47
@Darij: ≡ - letter-by-letter equality. In group theory, $"="$ usually means "freely equal", "$\equiv$" means "graphicaly equal". – Mark Sapir Mar 22 '13 at 4:57
up vote 5 down vote accepted

As you observe, we may assume that $p'$ is empty, i.e., that $v$ starts with a power of $u$. If $p$ is not a multiple of $u$, then writing $u$ as a circular word, it means you can find two district places in the circle where you can read $u$. So $u=xy=yx$ for some $x,y$ (namely if $|p|$ is $r$ mod $|u|$ take $x$ to be the suffix of $p$ of length $r$ and $y$ the prefix of $v$ of length $|u|-r$). But then x,y are powers of a common element and hence u is not primitive.

share|cite|improve this answer
@Ben: Thank you! – Mark Sapir Mar 22 '13 at 13:54
You're welcome. – Benjamin Steinberg Mar 22 '13 at 14:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.