Is it decidable whether or not a collection of integer matrices generates a free group? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T01:30:48Z http://mathoverflow.net/feeds/question/74212 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74212/is-it-decidable-whether-or-not-a-collection-of-integer-matrices-generates-a-free Is it decidable whether or not a collection of integer matrices generates a free group? unknown (google) 2011-08-31T23:53:32Z 2011-09-01T06:00:53Z <p>Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether or not $\varphi$ is injective?</p> http://mathoverflow.net/questions/74212/is-it-decidable-whether-or-not-a-collection-of-integer-matrices-generates-a-free/74217#74217 Answer by Mark Sapir for Is it decidable whether or not a collection of integer matrices generates a free group? Mark Sapir 2011-09-01T01:47:11Z 2011-09-01T05:03:57Z <p>For $n=1, 2$ the answer is "yes" since the group is virtually free, for $n\ge 3$ the answer is not known (an open problem). </p> <p><b> Edit. </b> In fact even for two $n\times n$-matrices the problem is open. Moreover the solution of the following easier" problem is not known: for which algebraic integers $\lambda$ the matrices $\left(\begin{array}{ll} 1 &amp; 2\\ 0 &amp; 1 \end{array}\right)$ and $\left(\begin{array}{ll} 1 &amp; 0\\ \lambda &amp; 1 \end{array}\right)$ generate a free group (see <a href="http://cage.ugent.be/~bamberg/Research_files/Non-free%20points%20for%20groups%20generated%20by%20a%20pair%20of%202x2%20matrices.pdf" rel="nofollow"> this </a> paper, for example). The fact that this problem is easier follows from the trivial observation that the group generated by these two matrices is isomorphic to some effectively computable group of $n\times n$-integer matrices for some $n\ge 2$ (depending on the degree of the algebraic number $\lambda$). </p> http://mathoverflow.net/questions/74212/is-it-decidable-whether-or-not-a-collection-of-integer-matrices-generates-a-free/74231#74231 Answer by HW for Is it decidable whether or not a collection of integer matrices generates a free group? HW 2011-09-01T06:00:53Z 2011-09-01T06:00:53Z <p>Here are some general facts that may be relevant.</p> <p>Given a finitely presented group $G$ and a representation $\rho:G\to GL_n(\mathbb{Z})$, <a href="http://www.ams.org/mathscinet/search/publdoc.html?arg3=&amp;co4=AND&amp;co5=AND&amp;co6=AND&amp;co7=AND&amp;dr=all&amp;pg4=AUCN&amp;pg5=AUCN&amp;pg6=PC&amp;pg7=ALLF&amp;pg8=ET&amp;review_format=html&amp;s4=bridson&amp;s5=wilton&amp;s6=&amp;s7=&amp;s8=All&amp;vfpref=html&amp;yearRangeFirst=&amp;yearRangeSecond=&amp;yrop=eq&amp;r=1&amp;mx-pid=2782175" rel="nofollow">there is no algorithm</a> <em>which is uniform in $n$</em> that decides whether or not $\rho$ is injective. </p> <p>However, this leaves open the possibility that there is such an algorithm for particular $n$. (It's easy for $n=2$, when the group is virtually free. I believe nothing is known for $n>2$.) Also, the examples we construct are not free groups, so it may be possible to say something in that case.</p> <p>In another direction, given a finite presentation for a group $G$ <em>and a solution to the word problem in $G$</em>, <a href="http://www.ams.org/mathscinet/search/publdoc.html?pg1=IID&amp;s1=814406&amp;vfpref=html&amp;r=7&amp;mx-pid=2516172" rel="nofollow">one can algorithmically determine</a> whether or not $G$ is a free group.</p>