9
$\begingroup$

The word problem for finite groups is decidable. Is it obvious that this is true?

In particular, I'm not entirely sure about what it means for the problem to be decidable (in this case---I think I understand what decidable means in general). I assume it means that we are given a fixed group G (do we have to assume this), but is the generating set (the letters) also fixed?

To decide the word problem for the group of symmetries of a square, with reflection $r$ and transposition $t$ as the generators, I would first find a canonical form for the group elements $1,r,r^2,r^3,t,tr,tr^2,tr^3$, and then note that using the relations $r^4=1$ and $rt=tr^3$ to show that any word can be reduced to something on my list. However, this seems like a lot of work, and it's not obvious to me what should be done in the case of an arbitrary finite group.

4 Answers 4

14

One can prove quite simply a much more general result due to McKinsey, viz. alt text alt text

  • 0
    Interesting. I always see this result attributed to Mostowski.2010-12-31
  • 0
    @HJRW J.C.C McKinsey "The decision problem for some classes of sentences without quantifiers." (in The Journal of Symbolic Logic 8.03 (1943): 61-76) is given as motivation in Lydon and Schupp's treatment of this theorem in "Combinatorial Group Theory" (Chapter IV, Theorem 4.6). They also list V.H. Dyson's "The word problem and residually finite groups" (in Notices Amer. Math. Soc 11 (1964): 743) as a reference. (comment continued below)2015-08-03
  • 0
    While both of these would predate A. Mostowski's "On the decidability of some problems in special classes of groups" (in Fundamenta Mathematicae 2.59 (1966): 123-135), Dyson's paper doesn't appear to be listed on MathSciNet and McKinsey doesn't seem to use the term"residually finite" instead using "finitely reducible" in the 1943 paper. Also, on first reading it appears that only the abelian case receives treatment. However, I can't say that I have read McKinsey's complete works. Perhaps the answer is referring to a different McKinsey or a different McKinsey reference?2015-08-03
  • 0
    @NeilHoffman, there are many examples of results that were proved independently on both sides of the iron curtain. Perhaps this is one of those?2015-08-03
  • 0
    @HJRW You are probably right about that. Notices of the AMS is American, while Fundamenta Mathematicae is Polish. On his webpage, Rolfen gives both Dyson and Mostowski as a reference (along with Lydon and Schupp). http://userpages.umbc.edu/~rcampbel/CombGpThy/RF_Thesis/1_Decision_Problems.html2015-08-03
10

I would recommend Rotman's book "An Introduction to the Theory of Groups" for basic material on word problems of groups, and for a reasonably accessible proof of the Novikov-Boone theorem which asserts the existence of finitely presented groups with unsolvable word problem.

The notion of the word problem of a group is generally applied to groups defined by a specific finite presentation, but it is not hard to prove that, for a group $G$, the solvability of the word problem of $G$ is independent of the given presentation of $G$, so it is customary simply to say that the word problem of $G$ is or is not solvable.

Lots of familiar classes of groups are known to have solvable word problem, including finite groups, finitely presented residually finite groups (proof given above by Bill Dubuque), automatic groups, finitely generated nilpotent groups. But, by a recent result of Olga Kharlampovich, there exist finitely presented solvable groups of derived length $3$ with unsolvable word problem.

Note that the word problem is semi-decidable for all groups given by a recursively enumerable presentation, in the sense that if you are given a word in the generators that does represent the identity element of the group, then it is possible to prove that it does. You can do that naively by systematically trying all possibilities for expressing the word as a product of conjugates of defining relators, but there are more efficient and practical methods of attempting this by using rewriting systems or coset enumeration.

6

The sense in which I think this statement is usually meant is that you are given the entire multiplication table of the group. Then it's obvious that the word problem is decidable. You seem to be thinking about a different question: maybe you are given generators and relations and you are told that they define a finite group, then asked to solve the word problem. This question, to me, is not obvious.

  • 0
    According to http://www-history.mcs.st-and.ac.uk/HistTopics/Word_problems.html, "any two finite presentations for the same group can be transformed to each other by applying finitely many Tietze transformations". It seems to me then that any presentation of a finite group can be transformed into its multiplication table; is that correct, and if so, how obvious is the fact about the Tietze transformations?2010-12-29
  • 0
    @Qiaochu: No, that's not what the word problem means. For a definition see e.g. http://en.wikipedia.org/wiki/Word_problem_for_groups2010-12-29
  • 0
    @Rahul, it is not hard, but exceeds the 600 character limit of a comment :) this is treated in detail in the good books on combinatorial group theory.2010-12-29
  • 0
    @Bill: Wikipedia says that the word problem is solvable for any automatic group, and it also says that any finite group is automatic. I guess what that actually means is that any presentation of a finite group is automatic. Is that true? Is it obvious?2010-12-30
  • 0
    @Qiaochu: The automaticity of a group does not depend on the generating set so you do not normally talk about a presentation of a group being automatic. Once you have understood the definition of an automatic group, it is not hard to prove that all finite groups are automatic.2010-12-30
  • 0
    @Derek: maybe I am just unclear about what data you are given here, or maybe I should learn some combinatorial group theory. Are you saying that the following statement is true: if you are given generators and relations for a group and told that it is finite, then you can give it an automatic structure, hence solve its word problem? What is the obvious proof?2010-12-30
  • 4
    @Qiaochu: It is not necessary to involve automatic structures. If you are given a (finite) set of generators and relations for a group $G$ and told that it is finite, then you can use the Todd-Coxeter coset enumeration algorithm to find the Cayley graph of the group on its given generating set. You can then use this to solve the word problem. (For typical well-behaved presentations Todd-Coxeter is efficient - if you are unlucky, and the presentation is pathological, then it could take unpredictably long, but since you are told the group is finite, it is guaranteed to temrinate eventually.)2010-12-30
  • 0
    @Derek: thanks, that makes sense. I guess what annoyed me is that you know that the algorithm terminates but you don't know when that guarantee is.2010-12-30
  • 1
    @Qiaochu: That's an inevitable consequence of the fact that many properties of groups defined by finite presentations (such as is the group trivial, finite, abelian, etc.) are known to be undecidable. If you could predict how long coset enumeration would take, then you could solve some of these problems.2010-12-31
  • 0
    @Derek: yes, that's precisely what was confusing me. I thought that being able to solve this problem implied being able to solve those problems, although your explanation makes it clear that it does not.2010-12-31
1

The easiest way to see that a finite group has solvable word problem is to notice that the solution is not required to be uniform over all finite groups. Given a finite group (presentation) there is an algorithm that takes that group (presentation) as input but ignores it. The algorithm then uses the group table, which is hard-coded into the algorithm, to reduce the word. The algorithm reduces the word by always replacing the product of the first two elements with a single element until there's just one element remaining.

  • 0
    Surely you need to solve the word problem to get the group table? By the logic you just proposed, let $G$ be given by a presentation with two generators, then one could claim that we are given the "list" of elements of the free group (which makes sense as the free group on two generators is countable, and so one can list them), and with each word we are given the fact of whether this word is trivial or not. Thus, we have solved the word problem...2011-12-13
  • 0
    The problem with your argument is that you don't know if the list of words that are trivial is computable. In general it won't be, which is exactly what "undecidability" of the word problem means. Thus in general there's no way (hard-coding or otherwise) for an algorithm to know if an word is trivial. Finite objects (in this case the table) are computable. Infinite objects (even countable ones) need not be.2011-12-13
  • 0
    @user1729 The point here is that this is not a *uniform* solution.2011-12-14
  • 0
    I understand what you are getting at, certainly. However, I am not entirely convinced - my point is that, yes, you need to compute this list, but at no point have you computed this list for your finite groups. Such a list will always exist, and the word problem, as you pointed out, comes down to computing it. Thus, to write the algorithm you propose *you must first solve the word problem*.2011-12-14
  • 0
    @user1729 If someone says, "I have a finite group. Is there an algorithm that, given a word as input, halts and outputs 'yes' if the word is trivial and 'no' otherwise?" I can answer "yes", without knowing anything else about the group (even, e.g., its presentation). Although I might not be able to give the asker the program that solves the given group's word problem, I know such a program must exist since one of the (countably) infinitely many programs has the group's multiplication table, which is a finite object, hard-coded into it and works a I described above.2011-12-14
  • 0
    This is tantamount to saying "for each $n$ there is an algorithm that halts on $n$ iff $n \in K$, where $K$ is the [halting set](http://en.wikipedia.org/wiki/Halting_problem#Representing_the_halting_problem_as_a_set) (or any incomputable set). That is possible since for each $n$ there's an algorithm that halts on $n$ and one that doesn't halt on $n$. What's false, of course, is saying that there's an algorithm that, for each $n$, halts on input $n$ iff $n \in K$. Notice the switch of quantifiers; the first gives an algorithm for each $n$ whereas the second asks for a *uniform* algorithm.2011-12-14