Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 12 down vote accepted

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.

share|improve this answer
    
Thanks for the carefully written answer! For the record, the result by Slobodskoi is explained nicely in Section 7.4.3 of the survey by Kharlampovich and Sapir. –  Tsuyoshi Ito Aug 30 '10 at 13:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.