Finite-dimensional version of the word problem for groups

2010-08-29T20:42:03Z

The (uniform) word problem for groups can be stated in several equivalent ways:

Word Problem for Groups (WP)
Instance: A finite presentation of a group G and an element w of G as a product of generators and their inverses.
Question: Does every linear representation of G in a (not necessarily finite-dimensional) Hilbert space map w to the identity operator?
Equivalently: Does every unitary representation of G in a Hilbert space map w to the identity operator?
Equivalently: Does every normal subgroup of G contain w?
Equivalently: Is w=1 in G?

As is well-known, WP is undecidable; more specifically, it belongs to RE∖coRE, where RE is the class of recursively enumerable languages and coRE is the class of their complements. (In fact, it is known that WP remains undecidable even if we fix the group G and its finite presentation suitably, but that is not the topic of this question.)

We can consider the finite-dimensional version of WP.

Finite-Dimensional Word Problem for Groups (FWP)
Instance: Same as WP.
Question: Does every matrix representation of G map w to the identity matrix?
Equivalently: Does every unitary matrix representation of G map w to the identity matrix?
Equivalently: Does every normal subgroup of G of finite index contain w?
(The equivalence is based on a result by Malcev; see this post by Greg Kuperberg and the comments attached to it.)

The two problems have different answers for some instances; that is, sometimes w≠1 in G but every matrix representation maps w to the identity matrix. There even exists a finitely presented infinite group which does not have a nontrivial matrix representation. See the answers to the question “Finitely presented sub-groups of GL(n,C)” by Dmitri.

In fact, FWP is in coRE unlike WP: if we also give the dimension as part of the input, the problem becomes decidable (because it is a system of algebraic equations over ℂ), and therefore FWP can be put in coRE by trying all dimensions.

Question: Is FWP decidable?

I do not even know whether FWP is NP-hard or not. As far as I know, FWP can be in P or undecidable, or anywhere in between!

(Note: FWP can be viewed as a (very) special case of the problem discussed in the question “Decidability of matrix algebra” by Ricky Demer.)

Answer by Agol for Finite-dimensional version of the word problem for groups

2010-08-29T22:31:34Z

FWP is undecidable by a result of Slobodskoi. Slobodskoi shows that the "Universal theory" of finite groups is undecidable. What you are asking for is whether the "Q-theory" of the pseudovariety of finite groups is decidable. The universal theory and Q-theory are equivalent for the pseudovariety of finite groups (see Kharlampovich-Sapir, section 2.4 for a discussion), so the Q-theory is undecidable too.

Finite-dimensional version of the word problem for groups - MathOverflow

Finite-dimensional version of the word problem for groups

Answer by Agol for Finite-dimensional version of the word problem for groups