Lemma: Given two cyclically reduced words $w,v$ they are conjugate to each other iff they are cyclic permutations of each other.
Some definitions:
Given a set $X$, we form the set of finite words on $X$, $W$. Formally this is a finite sequence of elements of set $S$ where $S=X\cup X^{-1}$ such that $X^{-1}=\{x^{-1}:x\in X\}$. We write $(s_1,\cdots,s_n)=s_1\dots s_n$
A word $w\in W$ is reduced if strings of the form $aa^{-1}$ or $a^{-1}a$ for $a\in S$ occurs. $w$ is cyclically reduced (cyc. red.) if every cyclic permutations of $w$ is reduced. So given $w=a_1\dots a_n$ every elements of form $a_na_1\dots a_{n-1}$, $a_{n-1}\dots a_{n-2}$ etc are reduced.
A word $w$ is conjugate to $v$ if $w=uvu^{-1}$ for some $u\in W$.
I find the given proof hard to follow and I think I've found a simpler proof, but I'm not sure if I'm missing something:
Proof: Fix a cyc. red. word $w$. Suppose there exist some cyc. red word $v$ conjugate to $w$ but $v$ is not a cyc. permutation of $w$.
Now choose some such $v$ and $g$ such that $w=gvg^{-1}$ AND length of $g$ is minimal among possible choices of $v,g$. (*)
The word $gvg^{-1}$ is not reduced; If it were then clearly it's not cyc. red. but we assumed that $w=gvg^{-1}$ is cyc. red. This means, if we write $g=g_1\dots g_n$ for $g_i\in S$, $v$ can be written as either $g_n^{-1}u$ or $ug_n$
Say $v=g_n^{-1}u$. But then we have $(g_1\dots g_{n-1})(ug_n^{-1})(g_{n-1}^{-1}\dots g_1^{-1})$. Clearly $ug_n^{-1}$ is cyc. permutation of $v$ and so is cyc. red. and conjugate to $w$. Then by minimality of $g$, we must have that $ug_n^{-1}$ is a cyc. permuation of $w$. But then $v$ is a cyc. permutation of $w$, a contradiction.
The other case is similar.
- Is this proof correct?
- For (*) I seem to have used axiom of choice. Is there any other way avoiding this? (I think original proof I've seen also used AOC anyway but...)