Is it decidable whether or not a collection of integer matrices generates a free group? - MathOverflow

Is it decidable whether or not a collection of integer matrices generates a free group?

2011-08-31T23:53:32Z

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?

Answer by Mark Sapir for Is it decidable whether or not a collection of integer matrices generates a free group?

2011-09-01T01:47:11Z

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).

Edit. 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 & 2\\ 0 & 1 \end{array}\right)$ and $\left(\begin{array}{ll} 1 & 0\\ \lambda & 1 \end{array}\right)$ generate a free group (see this 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$).

Answer by HW for Is it decidable whether or not a collection of integer matrices generates a free group?

2011-09-01T06:00:53Z

Here are some general facts that may be relevant.

Given a finitely presented group $G$ and a representation $\rho:G\to GL_n(\mathbb{Z})$, there is no algorithm which is uniform in $n$ that decides whether or not $\rho$ is injective.

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.

In another direction, given a finite presentation for a group $G$ and a solution to the word problem in $G$, one can algorithmically determine whether or not $G$ is a free group.