Skip to main content
Added details
Source Link
HJRW
  • 25k
  • 3
  • 68
  • 144

This is a very nice question which, as Agol says, is probably out of reach at the moment. To say that there is a classification of the fp subgroups of $GL_2(\mathbb{C})$ would be to say that the set of presentations of those subgroups is recursively enumerable and has solvable Isomorphism Problem. It's hard to guess which way to jump for either of these properties: the Isomorphism Problem is known to be unsolvable for finitely presented subgroups of $GL_N(\mathbb{Z})$ for some large $N$, by work of Bridson--Miller and Haglund--Wise.

There is one nice, tangential but positive, result that I know of. Oddly enough, it says that we have some sort of limited decision-theoretic understanding of which groups are not subgroups of $GL_2(\mathbb{C})$. Apparently it was known to Mal'cev; Daniel Groves and I re-discovered it for ourselves, but then found it in Lubotzky and Segal's book.

It's well known that most nice (more precisely, Markov) classes of finitely presented groups aren't recursively recognizable, by the Adian--Rabin Theorem. This applies to subgroups of $GL_2(\mathbb{C})$, essentially because the word problem is solvable, as Igor Belegradek pointed out above. However, in nice cases, it turns out that the word problem is the only obstruction.

More precisely, Groves, Manning and I call a class $\mathcal{C}$ of fp groups recursive modulo the word problem if $\mathcal{C}\cap\mathcal{D}$ can be recursively recognized in any class of groups $\mathcal{D}$ in which the word problem is uniformly solvable. This holds for the trivial group, abelian groups, nilpotent groups of class at most $k$ for fixed $k$, free groups, Sela's limit groups, surface groups, 3-manifold groups...

There is some hope that this could hold for subgroups of $GL_2(\mathbb{C})$. As I said above, it's unknown whether the class of these subgroups is recursively enumerable. However, it is true that the complement of this class is recursively enumerable modulo the word problem. That is, the following holds:

Theorem: Let $\mathcal{L}_n$ be the set of all finite presentations of subgroups of $GL_n(\mathbb{C})$. There is a Turing machine that determines in finite time if a presentation $P\notin\mathcal{L}_n$, using a solution to the word problem in $P$.

The key point is that a group is in $\mathcal{L}_n$ if and only if it is fully residually $\mathcal{L}_n$, and this latter property can be reduced to the decidability of the elementary theory of $\mathbb{C}$ (Tarski).

===========

Added details:

As far as I know, the theorem above isn't written down anywhere. The proof I had in mind is essentially an application of the following theorem.

Theorem (Mal'cev): A finitely generated group $G$ is a subgroup of a group $GL_n(\mathbb{C})$ if and only if $G$ is fully residually $GL_n(\mathbb{C})$; that is, for any finite subset $X\subseteq G\smallsetminus 1$ there is a homomorphism $f:G\to GL_n(\mathbb{C})$ with $1\notin f(X)$.

This is Theorem 16.4.1 in Lubotsky and Segal's book Subgroup growth.

Proof of the first theorem. Let $G$ be the group presented by $P$. Using the word problem, enumerate balls $B(n)$ in $G$. If $G$ is not embeddable in $GL_n(\mathbb{C})$ then, by Mal'cev's theorem, for some $n$, every homomorphism $f:G\to GL_n(\mathbb{C})$ kills a non-trivial element of $B(n)$. This last statement can be rephrased as a system of equations and inequations over $\mathbb{C}$ with integral coefficients, and hence solved. QED

This is a very nice question which, as Agol says, is probably out of reach at the moment. To say that there is a classification of the fp subgroups of $GL_2(\mathbb{C})$ would be to say that the set of presentations of those subgroups is recursively enumerable and has solvable Isomorphism Problem. It's hard to guess which way to jump for either of these properties: the Isomorphism Problem is known to be unsolvable for finitely presented subgroups of $GL_N(\mathbb{Z})$ for some large $N$, by work of Bridson--Miller and Haglund--Wise.

There is one nice, tangential but positive, result that I know of. Oddly enough, it says that we have some sort of limited decision-theoretic understanding of which groups are not subgroups of $GL_2(\mathbb{C})$. Apparently it was known to Mal'cev; Daniel Groves and I re-discovered it for ourselves, but then found it in Lubotzky and Segal's book.

It's well known that most nice (more precisely, Markov) classes of finitely presented groups aren't recursively recognizable, by the Adian--Rabin Theorem. This applies to subgroups of $GL_2(\mathbb{C})$, essentially because the word problem is solvable, as Igor Belegradek pointed out above. However, in nice cases, it turns out that the word problem is the only obstruction.

More precisely, Groves, Manning and I call a class $\mathcal{C}$ of fp groups recursive modulo the word problem if $\mathcal{C}\cap\mathcal{D}$ can be recursively recognized in any class of groups $\mathcal{D}$ in which the word problem is uniformly solvable. This holds for the trivial group, abelian groups, nilpotent groups of class at most $k$ for fixed $k$, free groups, Sela's limit groups, surface groups, 3-manifold groups...

There is some hope that this could hold for subgroups of $GL_2(\mathbb{C})$. As I said above, it's unknown whether the class of these subgroups is recursively enumerable. However, it is true that the complement of this class is recursively enumerable modulo the word problem. That is, the following holds:

Theorem: Let $\mathcal{L}_n$ be the set of all finite presentations of subgroups of $GL_n(\mathbb{C})$. There is a Turing machine that determines in finite time if a presentation $P\notin\mathcal{L}_n$, using a solution to the word problem in $P$.

The key point is that a group is in $\mathcal{L}_n$ if and only if it is fully residually $\mathcal{L}_n$, and this latter property can be reduced to the decidability of the elementary theory of $\mathbb{C}$ (Tarski).

This is a very nice question which, as Agol says, is probably out of reach at the moment. To say that there is a classification of the fp subgroups of $GL_2(\mathbb{C})$ would be to say that the set of presentations of those subgroups is recursively enumerable and has solvable Isomorphism Problem. It's hard to guess which way to jump for either of these properties: the Isomorphism Problem is known to be unsolvable for finitely presented subgroups of $GL_N(\mathbb{Z})$ for some large $N$, by work of Bridson--Miller and Haglund--Wise.

There is one nice, tangential but positive, result that I know of. Oddly enough, it says that we have some sort of limited decision-theoretic understanding of which groups are not subgroups of $GL_2(\mathbb{C})$. Apparently it was known to Mal'cev; Daniel Groves and I re-discovered it for ourselves, but then found it in Lubotzky and Segal's book.

It's well known that most nice (more precisely, Markov) classes of finitely presented groups aren't recursively recognizable, by the Adian--Rabin Theorem. This applies to subgroups of $GL_2(\mathbb{C})$, essentially because the word problem is solvable, as Igor Belegradek pointed out above. However, in nice cases, it turns out that the word problem is the only obstruction.

More precisely, Groves, Manning and I call a class $\mathcal{C}$ of fp groups recursive modulo the word problem if $\mathcal{C}\cap\mathcal{D}$ can be recursively recognized in any class of groups $\mathcal{D}$ in which the word problem is uniformly solvable. This holds for the trivial group, abelian groups, nilpotent groups of class at most $k$ for fixed $k$, free groups, Sela's limit groups, surface groups, 3-manifold groups...

There is some hope that this could hold for subgroups of $GL_2(\mathbb{C})$. As I said above, it's unknown whether the class of these subgroups is recursively enumerable. However, it is true that the complement of this class is recursively enumerable modulo the word problem. That is, the following holds:

Theorem: Let $\mathcal{L}_n$ be the set of all finite presentations of subgroups of $GL_n(\mathbb{C})$. There is a Turing machine that determines in finite time if a presentation $P\notin\mathcal{L}_n$, using a solution to the word problem in $P$.

The key point is that a group is in $\mathcal{L}_n$ if and only if it is fully residually $\mathcal{L}_n$, and this latter property can be reduced to the decidability of the elementary theory of $\mathbb{C}$ (Tarski).

===========

Added details:

As far as I know, the theorem above isn't written down anywhere. The proof I had in mind is essentially an application of the following theorem.

Theorem (Mal'cev): A finitely generated group $G$ is a subgroup of a group $GL_n(\mathbb{C})$ if and only if $G$ is fully residually $GL_n(\mathbb{C})$; that is, for any finite subset $X\subseteq G\smallsetminus 1$ there is a homomorphism $f:G\to GL_n(\mathbb{C})$ with $1\notin f(X)$.

This is Theorem 16.4.1 in Lubotsky and Segal's book Subgroup growth.

Proof of the first theorem. Let $G$ be the group presented by $P$. Using the word problem, enumerate balls $B(n)$ in $G$. If $G$ is not embeddable in $GL_n(\mathbb{C})$ then, by Mal'cev's theorem, for some $n$, every homomorphism $f:G\to GL_n(\mathbb{C})$ kills a non-trivial element of $B(n)$. This last statement can be rephrased as a system of equations and inequations over $\mathbb{C}$ with integral coefficients, and hence solved. QED

Source Link
HJRW
  • 25k
  • 3
  • 68
  • 144

This is a very nice question which, as Agol says, is probably out of reach at the moment. To say that there is a classification of the fp subgroups of $GL_2(\mathbb{C})$ would be to say that the set of presentations of those subgroups is recursively enumerable and has solvable Isomorphism Problem. It's hard to guess which way to jump for either of these properties: the Isomorphism Problem is known to be unsolvable for finitely presented subgroups of $GL_N(\mathbb{Z})$ for some large $N$, by work of Bridson--Miller and Haglund--Wise.

There is one nice, tangential but positive, result that I know of. Oddly enough, it says that we have some sort of limited decision-theoretic understanding of which groups are not subgroups of $GL_2(\mathbb{C})$. Apparently it was known to Mal'cev; Daniel Groves and I re-discovered it for ourselves, but then found it in Lubotzky and Segal's book.

It's well known that most nice (more precisely, Markov) classes of finitely presented groups aren't recursively recognizable, by the Adian--Rabin Theorem. This applies to subgroups of $GL_2(\mathbb{C})$, essentially because the word problem is solvable, as Igor Belegradek pointed out above. However, in nice cases, it turns out that the word problem is the only obstruction.

More precisely, Groves, Manning and I call a class $\mathcal{C}$ of fp groups recursive modulo the word problem if $\mathcal{C}\cap\mathcal{D}$ can be recursively recognized in any class of groups $\mathcal{D}$ in which the word problem is uniformly solvable. This holds for the trivial group, abelian groups, nilpotent groups of class at most $k$ for fixed $k$, free groups, Sela's limit groups, surface groups, 3-manifold groups...

There is some hope that this could hold for subgroups of $GL_2(\mathbb{C})$. As I said above, it's unknown whether the class of these subgroups is recursively enumerable. However, it is true that the complement of this class is recursively enumerable modulo the word problem. That is, the following holds:

Theorem: Let $\mathcal{L}_n$ be the set of all finite presentations of subgroups of $GL_n(\mathbb{C})$. There is a Turing machine that determines in finite time if a presentation $P\notin\mathcal{L}_n$, using a solution to the word problem in $P$.

The key point is that a group is in $\mathcal{L}_n$ if and only if it is fully residually $\mathcal{L}_n$, and this latter property can be reduced to the decidability of the elementary theory of $\mathbb{C}$ (Tarski).