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

This question came up in an algebra class I'm teaching. It's not my field and I couldn't find an answer easily, so I thought I would ask it here.

Is the fewest number of relations in a presentation of a group with undecidable word problem known?

The example with the fewest relations I could find by googling was 12 relations in a 1969 paper by Borisov (http://www.ams.org/mathscinet-getitem?mr=0260851) I also found a 1972 paper by Collins (http://www.ams.org/mathscinet-getitem?mr=0314998) which describes a presentation with 12 relations.

share|improve this question
I don't know what the current records are, but I doubt that the fewest number is known. In particular, it is still open whether the word problem is solvable in 2-relator groups. –  Andy Putman Sep 17 '12 at 5:19
Sapir says the Borisov example is the smallest known in his answer to Gower's question on economical undecidable word problems. –  Benjamin Steinberg Sep 17 '12 at 15:09
Yes, 12 is the current record. On the other hand, we do not know if there exists a group with 2 defining relation and undecidable word problem. For 1-related groups, the word problem is decidable by Magnus. For semigroups, even the 1-related case is still open. –  Mark Sapir Sep 18 '12 at 7:11
Just for the sake of completeness: Matiyasevich presented a semigroup with three defining relations for which the word problem is unsolvable. –  TT_ Aug 6 at 0:56

Your Answer


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

Browse other questions tagged or ask your own question.