Non-generating sets in a free group

Question

Let $F_n$ be the free group generated by $x_i$, for $1\leq i\leq n$. Let $a_i$ be some elements of $F_n$, also for $1\leq i\leq n$. Is there a nice way to tell when the list $\{a_i^{-1}x_ia_i\}$ does not generate $F_n$?

For insufficient reasons partially related to a talk Balloons and Hoops and their Universal Finite Type Invariant, BF Theory, and an Ultimate Alexander Invariant I gave once in Hamburg (video and handout there), and to a paper I'm not done writing with the same title (PDF there), I expect that there might be a way to construct out of the $a_i$'s a conjugacy class in $F_n$ (or perhaps in some completion of $F_n$), whose non-triviality implies that $\{a_i^{-1}x_ia_i\}$ do not generate $F_n$. Does this to anyone make sense?

Answer 1

So you're giving an endomorphism $\varphi:F_n\to F_n$, such that $\varphi(x_i)=a_i^{-1}x_ia_i$, and you want to know if this is an isomorphism?

There is a nice algorithm due to Stallings, called Stallings foldings, which will quickly tell you the answer. One may assume that $a_i$ is a reduced word and does not begin in $x_i^{-1}$, and that the $a_i$'s share no common postfix. If you take a wedge of loops as a $K(F_n,1)$, with a loop for each generator $x_i$, then the map $\varphi$ may be realized by a map between wedges of loops, where the loop $x_i$ goes to a loop represented by $a_i^{-1}x_ia_i$. The domain graph gets an induced cell decomposition, where the loop $x_i$ gets subdivided into $|a_i^{-1}x_ia_i|$ edges. Then you can "fold" the domain graph, making it shorter by identifying edges stemming from a vertex which map to the same edge in the target. If you iterate until no folds are available, then the map will be an isomorphism if and only if the map is a homeomorphism at the end.

From this, one gets a simple sufficient criterion for the endomorphism to not be an isomorphism, namely there are no folds available. This happens if the elements $a_i$ end in different generators and their inverses as reduced words. In general, though, I think one would have to carry out Stallings algorithm to get a necessary criterion.

Answer 2

Stallings' folding algorithm (described by Agol) is probably the best way of doing this, but I thought I'd mention an older algorithm which is also useful, due to Whitehead.

Let $\{w_k\}$ be a collection of words in $F_n$. The Whitehead graph is defined as follows. There are $2n$ vertices, labelled $x_i^{\pm}$. Whenever $x_ix_j$ appears as subword of some $w_k$, an edge is added from $x_i^+$ to $x_j^-$. Similarly, when $x_i^{-1}x_j$ appears as a subword, an edge is added from $x_i^-$ to $x_j^-$, and so on.

A better description of the Whitehead graph for a topologist is as follows. Realize $F_n$ as the fundamental group of a handlebody $U_n$. Realize the generators $x_i$ by finitely many properly embedded discs $D_i$, which cut the interior of $U_n$ into a ball. Realize the words $w_k$ by an embedded 1-dimensional submanifold of $U_n$; after a homotopy, we may assume that the $w_k$ are ‘pulled tight’ with respect to the discs $D_i$.

As mentioned already, cutting along the discs $D_i$ gives a 3-ball $B$, and each disc $D_i$ lifts to a pair of discs $D_i^{\pm}$ in the boundary of $B$. The submanifold $w_k$ becomes a set of intervals joining these discs. This is precisely the Whitehead graph, with the disc $D_i^{\pm}$ corresponding to the vertex $x_i^{\pm}$.

Here's a picture from one of my papers.

Whitehead used this construction to produce an algorithm that computes shortest representatives for sets of words $\{w_k\}$ under the action of the automorphism group of $F_n$: if the set of words is not of shortest length then one can perform a ‘Whitehead move’, which replaces one cutting disc with a better one, and reduce the length. In particular, his algorithm can be used to recognise generating sets. In fact, he proved the following very useful lemma.

Whitehead's Lemma: If $F_n$ admits a free splitting $A*B$ in which every $w_k$ is conjugate into either $A$ or $B$ then the Whitehead graph is either disconnected or has a cut vertex.

In particular, if the Whitehead graph is connected with no cut vertices then the $w_k$ do not generate. If the Whitehead graph is disconnected or does have a cut vertex then you can perform Whitehead moves until you find the answer.

For further details, see §I.4 of Lyndon and Schupp for the combinatorial approach and a paper "Whitehead graphs on handlebodies" of Stallings (DVI or PDF) for the topological approach.

Answer 3

If you just want a sufficient condition, then you can typically establish what you want by taking a finite group quotient of $F_n$. For example, $S_{n+1}$ is generated by $n$ adjacent transpositions (the Coxeter presentation), and these can all be conjugated onto the same transposition. Or indeed if they fail to form the edges of a tree on the $n+1$ symbols, then they do not generate $S_{n+1}$. Of course there are similar tricks with $\mathrm{SL}(n,\mathbb{Z}/p)$ or even $\mathrm{SL}(n,\mathbb{Z})$.

If you want necessary and sufficient conditions, then I guess since free groups are LERF, the above sufficient condition actually is also necessary, but I have no feeling that it's the best algorithm. I would study the proof that free groups are LERF to see if that gives you a more direct algorithm to calculate the coset space of $F_n$ divided by a finitely generated subgroup.