3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Mar 22, 2013 at 4:17
  • $\begingroup$ @Antony: (1) Yes, it is $|p|-|p'|$. Thanks! (2) I will add a sketch of a proof. $\endgroup$
    – user6976
    Mar 22, 2013 at 4:26
  • $\begingroup$ Sorry, but what is that $\equiv$ sign? Equality? $\endgroup$ Mar 22, 2013 at 4:47
  • $\begingroup$ @Darij: ≡ - letter-by-letter equality. In group theory, $"="$ usually means "freely equal", "$\equiv$" means "graphicaly equal". $\endgroup$
    – user6976
    Mar 22, 2013 at 4:57

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.