# The word problem for finite groups

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.

-

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

-
Interesting. I always see this result attributed to Mostowski. – HJRW Dec 31 '10 at 6:19
@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) – Neil Hoffman Aug 3 '15 at 8:10
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? – Neil Hoffman Aug 3 '15 at 8:25
@NeilHoffman, there are many examples of results that were proved independently on both sides of the iron curtain. Perhaps this is one of those? – HJRW Aug 3 '15 at 8:28
@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). userpages.umbc.edu/~rcampbel/CombGpThy/RF_Thesis/… – Neil Hoffman Aug 3 '15 at 8:46

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.

-

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.

-
According to 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? – Rahul Dec 29 '10 at 23:11
@Qiaochu: No, that's not what the word problem means. For a definition see e.g. en.wikipedia.org/wiki/Word_problem_for_groups – Bill Dubuque Dec 29 '10 at 23:25
@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. – Mariano Suárez-Alvarez Dec 29 '10 at 23:26
@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.) – Derek Holt Dec 30 '10 at 17:53
@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. – Derek Holt Dec 31 '10 at 11:56

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.

-
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... – user1729 Dec 13 '11 at 20:22
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. – Quinn Culver Dec 13 '11 at 23:37
@user1729 The point here is that this is not a uniform solution. – Quinn Culver Dec 14 '11 at 0:54
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. – user1729 Dec 14 '11 at 16:45
@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. – Quinn Culver Dec 14 '11 at 17:38