Presentations of infinite index subgroups - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T05:23:00Z http://mathoverflow.net/feeds/question/105514 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105514/presentations-of-infinite-index-subgroups Presentations of infinite index subgroups Dan 2012-08-26T10:47:53Z 2012-08-26T19:15:03Z <p>Suppose we have a finitely presented group $G$ with a concrete presentation and a subgroup $H$, generated by a finite set of elements from $G$. How to find the presentation for $H$?</p> <p>If $H$ has finite index we can use Reidemeister-Schreier procedure. But what if $H$ has infinite index? What methods exist? Are there some methods if $H$ is normal?</p> http://mathoverflow.net/questions/105514/presentations-of-infinite-index-subgroups/105568#105568 Answer by HW for Presentations of infinite index subgroups HW 2012-08-26T19:15:03Z 2012-08-26T19:15:03Z <p>The following answer will only be about decidability results or, more often, undecidability results. Of course, if you have a particular group in mind, it may be that something positive can be said. I will leave others to talk about practical algorithms.</p> <p>Let $G=\langle X\mid R \rangle$ be a finitely presented group, $S$ a finite subset and $H=\langle S\rangle$.</p> <p>As you mentioned recursive presentations in your comment, let me mention that there is a naive algorithm that always finds a recursive presentation for $H$: just enumerate all words in $S$ that happen to lie in $\langle\langle R \rangle\rangle$. Of course, as there are finitely presented groups that are not coherent, $H$ may not be finitely presentable, so this is the best you can hope for.</p> <p>Even if you assume that $H$ is finitely presentable, as Misha says, there is no algorithm to compute a finite presentation for $H$. This follows immediately from the undecidability of the word problem: if you could compute a presentation for $\langle w\rangle$ then, in particular, you could determine whether or not $w=1$. </p> <p>Of course, the next thing to wonder is whether there are examples with solvable word problem. <a href="http://www.ams.org/mathscinet/search/publdoc.html?arg3=1973&amp;co4=AND&amp;co5=AND&amp;co6=AND&amp;co7=AND&amp;dr=pubyear&amp;pg4=AUCN&amp;pg5=AUCN&amp;pg6=PC&amp;pg7=ALLF&amp;pg8=ET&amp;review_format=html&amp;s4=collins%252C%2520d%2a&amp;s5=&amp;s6=&amp;s7=&amp;s8=All&amp;vfpref=html&amp;yearRangeFirst=&amp;yearRangeSecond=&amp;yrop=eq&amp;r=1&amp;mx-pid=398813" rel="nofollow">Collins</a> constructed a group with solvable word problem and unsolvable <em>order problem</em> --- that is, you can tell whether or not an element $w$ is trivial, but you can't compute the order of $w$. Again, it follows that you can't compute a presentation for $\langle w\rangle$.</p> <p>The examples so far are specially constructed to behave badly. <a href="http://arxiv.org/abs/1003.5117" rel="nofollow">Bridson and I</a> used work of Haglund and Wise to give examples which show that you can't compute presentations for finitely presentable subgroups even in 'naturally occurring' classes like automatic groups and matrix groups. You can also look at Section 8 of our paper for a summary of positive results. </p>