Finite-dimensional version of the word problem for groups - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T21:34:24Z http://mathoverflow.net/feeds/question/37083 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37083/finite-dimensional-version-of-the-word-problem-for-groups Finite-dimensional version of the word problem for groups Tsuyoshi Ito 2010-08-29T20:42:03Z 2010-08-30T06:08:49Z <p>The (uniform) word problem for groups can be stated in several equivalent ways:</p> <p><strong>Word Problem for Groups (WP)</strong><br> <em>Instance</em>: A finite presentation of a group G and an element w of G as a product of generators and their inverses.<br> <em>Question</em>: Does every linear representation of G in a (not necessarily finite-dimensional) Hilbert space map w to the identity operator?<br> <em>Equivalently</em>: Does every unitary representation of G in a Hilbert space map w to the identity operator?<br> <em>Equivalently</em>: Does every normal subgroup of G contain w?<br> <em>Equivalently</em>: Is w=1 in G?</p> <p>As is well-known, WP is undecidable; more specifically, it belongs to RE∖coRE, where <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#re" rel="nofollow">RE</a> is the class of recursively enumerable languages and <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:C#core" rel="nofollow">coRE</a> 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.)</p> <p>We can consider the finite-dimensional version of WP.</p> <p><strong>Finite-Dimensional Word Problem for Groups (FWP)</strong><br> <em>Instance</em>: Same as WP.<br> <em>Question</em>: Does every <em>matrix</em> representation of G map w to the identity matrix?<br> <em>Equivalently</em>: Does every unitary <em>matrix</em> representation of G map w to the identity matrix?<br> <em>Equivalently</em>: Does every normal subgroup of G <em>of finite index</em> contain w?<br> (The equivalence is based on a result by Malcev; see <a href="http://mathoverflow.net/questions/9628/finitely-presented-sub-groups-of-gln-c/9635#9635" rel="nofollow">this post</a> by Greg Kuperberg and the comments attached to it.)</p> <p>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 “<a href="http://mathoverflow.net/questions/9628/finitely-presented-sub-groups-of-gln-c" rel="nofollow">Finitely presented sub-groups of GL(n,C)</a>” by Dmitri.</p> <p>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.</p> <blockquote> <p><strong>Question</strong>: Is FWP decidable?</p> </blockquote> <p>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!</p> <p>(Note: FWP can be viewed as a (very) special case of the problem discussed in the question “<a href="http://mathoverflow.net/questions/33879/decidability-of-matrix-algebra" rel="nofollow">Decidability of matrix algebra</a>” by Ricky Demer.)</p> http://mathoverflow.net/questions/37083/finite-dimensional-version-of-the-word-problem-for-groups/37095#37095 Answer by Agol for Finite-dimensional version of the word problem for groups Agol 2010-08-29T22:31:34Z 2010-08-30T06:08:49Z <p>FWP is undecidable by a <a href="http://www.springerlink.com/content/x880g1x17754hq83/" rel="nofollow">result of Slobodskoi.</a> 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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.766" rel="nofollow">Kharlampovich-Sapir</a>, section 2.4 for a discussion), so the Q-theory is undecidable too. </p>