# Determining whether two free groups are conjugates

Let $$A= \langle a,b \rangle$$, i.e. the free group on two generators. Also, let $$B=\langle b^{-1}a^{-1}bab,b^{-1}a^2b, b^2, a^2, ab^2a^{-1}, abab^{-1}a^{-1} \rangle$$, $$C= \langle a^{-1}b^{-1}aba,a^{-1}b^2a, a^2, b^2, ba^2b^{-1}, baba^{-1}b^{-1} \rangle$$.

I'm trying to determine whether $$B$$ and $$C$$ are conjugate in $$A$$. From a glance, they don't look like they are but I'm not entirely sure how to formally write it. I know that the abelinations of $$B$$ and $$C$$ are the same in $$C$$, but that doesn't tell me whether they are actually conjugate or not.

• Use $\langle x\rangle$ for $\langle x\rangle$. – Shaun Nov 26 '20 at 22:20
• A computer calculation indicates that they $B=C$. They both have index $5$ in $A$. – Derek Holt Nov 26 '20 at 22:27
• @DerekHolt - did you do this in GAP? Is there a way to get a computer to output a witness $w$ such that $B^w = C$? – HallaSurvivor Nov 26 '20 at 22:36
• @HallaSurvivor If they are equal, then $w=e$. – Arturo Magidin Nov 26 '20 at 22:39
• @ArturoMagidin - It seems I read Derek's comment too quickly, haha. The question still stands in the case they're merely conjugate, though. – HallaSurvivor Nov 26 '20 at 22:41

To prove that $$B=C$$, we just have to prove that all of the generators of $$B$$ are in $$C$$ and vice versa. Many of these are clear. Here is a proof that the first generator of $$C$$ is in $$B$$ - the others are similar. (Of course this was all guided by computer calculations.)

$$a^{-1}b^{-1}aba=(a^{-2})(ab^2a^{-1})^{-1}(abab^{-1}a^{-1})(ab^2a^{-1})(a^2).$$

• Do you know if there's a simpler result that allows us to deduce they are the same without computer calculations. Something like "Two subgroups are conjugate iff they have the same abelinisation" (don't think this is true, just giving an example). – Hai Nov 27 '20 at 9:05
• Simpler result than what? This particular problem turns out to be relatively easy, because the two subgroups are equal. But I don't know of any such result for conjugacy testing of subgroups, which is computationally difficult in general. But it is decidable for subgroups of free groups. – Derek Holt Nov 27 '20 at 9:24
• Simple was perhaps not the correct word. I just meant something that wouldn't require computer calculation for similar, or even more complex, examples. But I suppose there isn't any such result. – Hai Nov 27 '20 at 9:33

One way to solve this by hand with pencil and paper (or e-tablet and e-pencil) is to compute the Stallings graphs of $$B$$ and $$C$$.

To describe the Stallings graph, start with the rose graph $$R_A$$ with one vertex $$V$$, and with two edges that are oriented and labelled $$a$$ and $$b$$ respectively. Any finite rank subgroup $$H < A$$ has a unique Stallings graph, which is a finite connected graph $$\Gamma_H$$ without valence 1 vertices, and which is labelled by assigning to each edge an orientation and one of the letters $$a$$ or $$b$$. The topological meaning of this is that the induced graph map $$f : \Gamma_H \to R_A$$ (taking each oriented, labelled edge of $$\Gamma_H$$ to the corresponding oriented labelled edge of $$R_A$$) is locally injective, and that $$H$$ is conjugate to the image of the induced homomorphism $$f_*: \pi_1(\Gamma_H,w) \to \pi_1(R_A,v) = \langle a,b \rangle$$ for any vertex $$w \in \Gamma_H$$. The uniqueness condition means that the label preserving isomorphism class of $$\Gamma_H$$ is uniquely determined by the conjugacy class of $$H$$.

Thus, if you can compute the Stallings graphs of $$B$$ and $$C$$ then you can examine the graphs to determine whether $$B$$ and $$C$$ are conjugate.

To compute the Stallings graph of $$B$$, for example, start with a rank 6 rose graph having one loop for each of the 6 words listed in the generating set for $$B$$. Subdivide the first loop into five edges labelled $$b^{-1} a^{-1} bab$$; subdivide the second loop subdivided into 4 edges labelled $$b^{-1} a a b$$; and subdivide similarly for the remaining four edges.

Now repeat the following step inductively: look for a vertex having two directions coming out of that vertex with identical labels, and compute the quotient graph by identifying those two edges. For example, the first loop has first edge labelled $$b^{-1}$$ and the second loop has first edge labelled $$b^{-1}$$; so identify those edges.

The number of edges will decrease strictly with each repetition, and therefore eventually you will arrive at a graph such that at each vertex, any two directions coming out of that vertex have distinct labels. The graph you end up with might have valence 1 vertices; inductively remove each such vertex and its incident edge. At the end of that process, the resulting labelled graph is the Stallings graph of $$B$$.

You can find a detailed description with examples in my book.

• It's interesting how mathematicians from different areas use apparently completely different terminology for the same algorithm. Many of us refer to the Stallings folding process as Todd-Coxeter coset enumeration. – Derek Holt Nov 27 '20 at 7:49
• Huh. Didn't know that they were that closely related. Perhaps the point is that Stallings couched things in topological/geometric language that some of us need to understand the algebra :-) – Lee Mosher Nov 27 '20 at 15:31
• I am pretty sure that they are essentially identical as algorithms. The folding process, where edges and vertices get identified corresponds to coincidence processing in coset enumeration. – Derek Holt Nov 27 '20 at 16:38