# Conjugacy depth of free groups

This question is related to this one but for some reason I did not see a connection before Ben McReynolds asked me that question.

Question What is the smallest function $f(n)$ such that for every two non-conjugate words $u,v$ from the free group $F_2$ of length $\le n$ there exists a finite homomorphic image of $F_2$ of order $\le f(n)$ where $u,v$ are not conjugate?

The function $f(n)$ can be called the conjugacy depth function of $F_2$. The ordinary depth function intruduced by Bou-Rabee "serves" the word problem in a similar way. It is known and not difficult to deduce from the fact that $F_2$ is linear that the depth function of the free group is polynomial (the best known estimate is due to Kassabov and Matucci). Is the conjugacy depth function of the free group bound by a polynomial? It would be so if the answer to the that question is "yes" because matrices with different traces are not conjugate and if two matrices in $SL_3(Z[x_{11},...,y_{33}])$ have different traces, then these two matrices will have different traces in some small finite factor. As Ben McReynolds pointed out to me, if one uses nilpotent factors of $F_2$ to estimate the conjugacy depth growth,one gets exponential estimates.

Update. One does not need work of Marshall Hall, Hempel, Stallings or Stebe to prove conjugacy separability of $F_2$. One does not need linear groups as well. Here is a proof. Let $u,v$ be cyclically reduced words in $F_2$, $u$ is not a cyclic shift of $v$, $n=|v|\ge |u|$. Consider a finite 4-regular graph $(V,E)$ containing exactly one cycle $C$ of length $n$ (exercise: construct such a graph). Label the edges of $C$ by the generators of $F_2$ and their inverses so that $C$ spells $v$. Extend the labeling of $C$ to a lebeling of $(V,E)$ by the generators of $F_2$ and their inverses to obtain a complete automaton (no two edges having the same tail have the same label). Then each generator of $F_2$ induces a permutation of $V$. So the labeling induces a homomorphism of $F_2$ into the symmetric group $S_{V}$. The images of $u$ and $v$ under this homomorphism are not conjugate because the image of $v$ has a fixed point while the image of $u$ has not.

-
Nice question!! –  Benjamin Steinberg Mar 26 '13 at 18:02
Given that McReynolds asked you this, surely this is an open question? –  HJRW Mar 26 '13 at 19:56
Actually, in any free group, there are non-conjugate elements which have the same trace in any representation to $SL_2$. ams.org/mathscinet-getitem?mr=314993 –  Ian Agol Mar 26 '13 at 20:40
Mark, obviously that's not the sense of 'open' I meant. I suppose I'm just uncertain what sort of answer you expect to get on MO. This is a topic of active research. –  HJRW Mar 26 '13 at 21:54
Nice proof! Two further comments: 1. This technique is exactly the method of proof (of LERF, say) of Marshall Hall, as interpreted by Hempel/Stallings, so I don't know why you say you don't need them. 2. Perhaps you meant to stipulate that your graph has no cycles of length less than n, if you want to argue that u has no fixed point? –  HJRW Mar 27 '13 at 20:55