30

Is it decidable whether two given elements of ${\rm GL}(n,{\mathbb Z})$ generate a free group of rank 2?

This is a simple question that I have been asking people for the past couple of years, but nobody has known the answer, so I thought I would try here.

The Tits alternative is known to be (effectively) decidable for finitely generated subgroups of ${\rm GL}(n,{\mathbb Z})$, but that is not helpful here.

Added: From what Misha says, the answer to the general problem might be unknown, but it is likely to be undecidable. An easier question would be, assuming that the group in question is not virtually solvable, can we find a nonabelian free subgroup (with proof). I think the answer to that might be yes, using pingpong.

This second question is answered positively here

Derek Holt
  • 36,425
  • 4
  • 91
  • 144
  • 8
    I am quite sure that this is an open problem (even if n=3). Non-freedom is, of course, semi-decidable. Proving freedom in all known to me cases requires getting hold of some geometry, e.g. finding a quadruple of domains allowing for ping-pong. The trouble is that while every free subgroup will have such domains (in a flag-manifold or in the symmetric space), their boundaries are not guaranteed to be finitely-definable. This is already apparent in the case of subgroups of $O(3,1, {\mathbb Z})$. My personal feeling is that freedom is undecidable but we are lucking tools for proving this. – Misha Apr 16 '19 at 02:16
  • @Misha Yes, I thought that was probably the case, and the fact that nobody I have asked knows the answer suggests that it is an open problem. – Derek Holt Apr 16 '19 at 02:18
  • 4
    Derek: Your second question is much easier, this is the area known as "quantitative Tits' alternative". – Misha Apr 16 '19 at 02:28
  • @Misha One notable exception of proving freedom without ping pong is in the construction of large girth graphs with bounded diameter-by-girth ratio by Goulnara Arzhantseva and Arindam Biswas. See Proposition 4.1 and the discussion before it in https://arxiv.org/abs/1803.09229 – Tony Huynh Apr 16 '19 at 02:41
  • @Misha thanks, that made it easy to find a reference. – Derek Holt Apr 16 '19 at 02:42
  • 3
    Some evidence that such questions might be undecidable: see Corollary D of this paper https://www.ems-ph.org/journals/show_abstract.php?issn=1661-7207&vol=5&iss=2&rank=7 – Ian Agol Apr 16 '19 at 05:23
  • 3
    Just a trivial restatement of the question. For a non-free pair $(u,v)$ in a group, let $N(u,v)$ be the smallest length of a nontrivial group word $w$ such that $w(u,v)=1$. In $\mathrm{GL}_d(\mathbf{Z})$, define $s_d(n)$ as the min of $N(u,v)$ over all non-free pairs $(u,v)$ with $|u|,|v|\le n$ (sup norm of matrices). Then the decidability problem is equivalent to whether $n\mapsto s_d(n)$ is computable, and it's equivalent to whether it's bounded above by a computable function. – YCor Apr 16 '19 at 06:56
  • @LucGuyot in $\mathrm{GL}_2(\mathbf{Z})$ it's also decidable, and probably easier, whether a pair is free (instead of positively free as you mention), and more generally in any virtually free f.g. group $G$. – YCor Apr 16 '19 at 07:31
  • 1
    On a closely related topic: https://mathoverflow.net/questions/74212/is-it-decidable-whether-or-not-a-collection-of-integer-matrices-generates-a-free – Luc Guyot Apr 16 '19 at 12:24
  • 1
    @TonyHuynh: Thank you, I did not know about this paper. However, I intentionally said "e.g." instead of "i.e.", as there are also coarse-geometric tools for proving freedom in matrix groups. This becomes an actual algorithm in $SL(2,C)$ and a semi-algorithm for Anosov representations in higher rank. – Misha Apr 16 '19 at 14:06
  • 4
    It was shown in Klarner, Birget and Satterfield that freeness of the semigroup generated by 3x3 integer matrices is undecidable. Probably this is a bad sign for groups thought it doesn't really imply it. – Benjamin Steinberg Apr 16 '19 at 18:51

0 Answers0