MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

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.

share|cite|improve this question
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$. – 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
up vote 11 down vote accepted

The question, as far as I know, is open. Sean Lawton, Lars Louder, and I are just finishing up a paper that addresses the complexity of the depth function for conjugacy separability. At present, we can prove that if you fix a word in the free group, then distinguishing the associated conjugacy class from another conjugacy class in finite quotients is polynomial in the word length of the varying class. The degree of the polynomial depends on the fixed word. We give two algorithms. One is geometric and one is algebraic.

We tie the complexity of this function with linear representations of groups as Mark mentioned above. The case of n=3 is not special and having any linear representation of the free group that sends conjugacy classes to distinct traces suffices for a polynomial upper bound. I hesitate to say too much as to where I lean but I would guess that the complexity of the depth function for conjugacy in free groups is super-polynomial. We provide a decent amount of evidence for this in the forthcoming paper.

We also prove that for groups like SL(n,Z), which are known by work of Stebe to not be conjugacy separable for n at least 3, have a rather dramatic failure of conjugacy separability. Essentially every infinite word will have infinitely many powers that are conjugate to other words that are not conjugate to the power in SL(n,Z). These other words are also primitive (not powers of another word). This investigation also leads to a general method for addressing the depth function for conjugacy on free groups.

With one of my students, Mark Pengitore, we are currently writing a paper on these conjugacy depth functions for other classes of groups; virtually polycyclic for instance.

share|cite|improve this answer
The paper mentioned in this comment is now available. Here is a link: – Khalid Bou-Rabee Apr 17 '14 at 21:06

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.