Non-generating sets in a free group. - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T12:01:37Z http://mathoverflow.net/feeds/question/115937 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115937/non-generating-sets-in-a-free-group Non-generating sets in a free group. Dror Bar-Natan 2012-12-10T00:47:36Z 2012-12-10T19:34:03Z <p>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 <strong>not</strong> generate $F_n$?</p> <p>For insufficient reasons partially related to a talk I gave once in <a href="http://www.math.toronto.edu/~drorbn/Talks/Hamburg-1208/" rel="nofollow">Hamburg</a> (video and handout there), and to a <a href="http://www.math.toronto.edu/~drorbn/papers/KBH/" rel="nofollow">paper I'm not done writing</a> (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?</p> http://mathoverflow.net/questions/115937/non-generating-sets-in-a-free-group/115942#115942 Answer by Greg Kuperberg for Non-generating sets in a free group. Greg Kuperberg 2012-12-10T01:36:23Z 2012-12-10T01:36:23Z <p>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})$.</p> <p>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.</p> http://mathoverflow.net/questions/115937/non-generating-sets-in-a-free-group/115943#115943 Answer by Ian Agol for Non-generating sets in a free group. Ian Agol 2012-12-10T01:38:13Z 2012-12-10T19:34:03Z <p>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? </p> <p>There is a nice <a href="http://www.ams.org/mathscinet-getitem?mr=695906" rel="nofollow">algorithm due to Stallings</a>, 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. </p> <p>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. </p> http://mathoverflow.net/questions/115937/non-generating-sets-in-a-free-group/115971#115971 Answer by HW for Non-generating sets in a free group. HW 2012-12-10T12:36:18Z 2012-12-10T13:17:41Z <p>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.</p> <p>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.</p> <p>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$.</p> <p>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}$.</p> <p>Here's a picture from one of my papers.</p> <p><img src="http://www.freeimagehosting.net/6wb7s" alt="The Whitehead graph of b^{-1}aba^{-2}."></p> <p>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. </p> <p><strong>Whitehead's Lemma:</strong> 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.</p> <p>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.</p> <p>For further details, see §I.4 of Lyndon and Schupp for the combinatorial approach and a paper of Stallings (click <a href="http://math.berkeley.edu/~stall/wh.dvi" rel="nofollow">here</a> for a dvi) for the topological approach.</p>