Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 11 down vote accepted

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

share|improve this answer
    
Interesting. I always see this result attributed to Mostowski. –  HJRW Dec 31 '10 at 6:19

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.

share|improve this answer

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.

share|improve this answer
    
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
    
@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? –  Qiaochu Yuan Dec 30 '10 at 12:11
3  
@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

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.

share|improve this answer
    
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

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.