MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
3  
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
1  
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
4  
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 '15 at 0:56

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.