Small group presentations with unsolvable word problem
Follow the latest progress by email.
How few generators and relators can a finite group presentation have while its word problem remains unsolvable? The word problem asks whether a word represents the identity.
Why it matters and what counts as progress
Why it matters: Small presentations make an undecidability construction more explicit without changing its computational impossibility.
What counts as progress: A smaller presentation with a proved reduction establishing unsolvability, or a size lower bound; an achieved relator count is not automatically minimal.
How the problem developed
- 1969 · Construction [1]
V. V. Borisov Gave a 12-relator group presentation with unsolvable word problem, a benchmark for later size reductions.
- 9 Sept 2026 · Construction [2]
Marc Kegel, Shana Yunsheng Li and Qiuyu Ren Constructed a 3-generator, 9-relator group with unsolvable word problem and fixed-size Adian–Rabin families; the paper includes a Lean 4 formalization of its algebraic results.
AI contribution
Small undecidable groups and fixed-size Adian–Rabin families
Kegel, Li and Ren give a finite presentation with three generators and nine relators whose word problem is unsolvable. The count is an achieved presentation size, not a minimum.
Sources
Website timeline
Publication dates and editorial changes.
AI-developed construction gives a nine-relator group with unsolvable word problem