Non-generating sets in a free group.

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 I gave once in Hamburg (video and handout there), and to a paper I'm not done writing (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?

-
This question is about definable subsets of $F_n$, $n>2$ not folding. (The case $n=2$ is due to Nielsen, and there the answer is yes.) The set of $a_1$ such that there are $a_2,\dotsc,a_n$ so that $x_i^{a_i}$ generates is neither negligible nor co-negligible (see andromeda.rutgers.edu/~feighn/luminy.pdf) and is therefore not definable without coefficients. I don't know exactly, but my gut-feeling is that this set isn't definable with coeffcients either. Bestvina-Feighn probably works, and there is really no simple way to check, other than to go ahead and do it with folding. –  nolte Dec 10 '12 at 13:42
Shurely whether or not the question is 'about definable subsets' or 'about folding' depends on how you interpret the words 'Is there a nice way to tell...'!? Many (most?) would interpret it as a request for an algorithm. –  HJRW Dec 10 '12 at 14:11
Also, by 'Bestvina--Feighn' I think yo probably means a not-publicly-available sequel to their paper 'Notes on Sela's work'. –  HJRW Dec 10 '12 at 14:13
Sorry, I was referring to the second paragraph of the question, not the first (It seems like Dror is perhaps aware of Nielsen's criterion.). There is a paper by Kharlampivic and Myasnikov claiming to give a proof of BF, but I don't know if it works in this case. Either way, you can probably use Sela's envelopes to get something similar. –  nolte Dec 10 '12 at 14:24
@yo: Kharlampovich and Myasnikov not only claimed that, they also proved it. The question is not about definable sets, though. To check whether the conjugates generate $F$, people consider the lollipop graph, and do Stallings foldings. If the result is a 1-vertex graph, the elements generate, otherwise they don't. It is quite easy (certainly in P, perhaps much faster, there were papers about precise complexity of Stallings algorithm. –  Mark Sapir Dec 18 '12 at 11:10

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.

-
Dear Ian, I am not sure I understand your last paragraph. If there are no folds available, then the map is not an isomorphism, right? –  Roberto Frigerio Dec 10 '12 at 10:35
I think Ian meant that if the graph is not the rose and there are no folds available, then the endomorphism is not an isomorphism. (The necessary and sufficient condition to be an isomorphism is that after performing all folds, you have the rose.) –  Richard Kent Dec 10 '12 at 16:18
right, thanks for the correction. –  Ian Agol Dec 10 '12 at 19:32

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 of Stallings (click here for a dvi) for the topological approach.

-
Gah! Why doesn't the image work? –  HJRW Dec 10 '12 at 12:41

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.

-
Greg - FYI, Stallings' folding argument (described by Ian) does exactly compute that coset space. –  HJRW Dec 10 '12 at 12:08