Word problem (group theory)

Word problem (group theory)
Name	Word problem (group theory)
Field	Algebra, Mathematics
Introduced	1911
Notable	Higman embedding theorem, Novikov–Boone theorem, Dehn's algorithm, Mikhail Gromov

Word problem (group theory) The word problem in group theory asks whether two words in a group's generators represent the same element. It is a central decision problem linking Max Dehn, Emil Post, Pyotr Novikov, William Boone, Graham Higman, Alonzo Church and Alan Turing to concrete algorithmic questions about Cayley graphs, group presentations, and effective properties of groups. The problem has deep interrelations with results from Hilbert's problems, Gödel, Tarski, and modern geometric group theory around figures such as Mikhail Gromov and Gromov–Schoen collaborators.

Introduction

The word problem is formulated for a group given by a finite group presentation ⟨S | R⟩ and asks whether a finite word over the generating set S and its inverses equals the identity. Connections appear across work of Max Dehn on fundamental groups of surfaces, Dehn surgery contexts, and algorithmic studies by Emil Post and scholars at institutions like Princeton University, Cambridge University, and Harvard University. The decision question inspired research in computability theory by Alan Turing and Alonzo Church and later influenced results by Pyotr Novikov and William Boone on undecidability.

Formal statement and variants

Formally: given a finite generating set S and relators R, the word problem asks, for an input word w ∈ (S ∪ S^{-1})*, whether w equals the identity in the group ⟨S | R⟩. Variants include the conjugacy problem (are two words conjugate?), the isomorphism problem (are two finite presentations isomorphic?), and the membership problem (is an element in a subgroup?), connecting to work by Higman, Mikhail Gromov, Sergei Adian, and others. For groups given by infinite presentations, or by constructive descriptions from von Neumann algebras or C*-algebra contexts, the problem formulation adapts to computability models associated with Turing machines and recursive function theory studied by Stephen Kleene.

Decidability and algorithmic results

Classic decidability results include Dehn's algorithm for fundamental groups of closed hyperbolic surfaces and small-cancellation groups studied by O. J. Schupp and Gerald A. Miller. The Novikov–Boone theorems proved existence of finitely presented groups with undecidable word problem, work associated with Pyotr Novikov, William Boone, and later refinements by Graham Higman and Ralph Strebel. Higman's embedding theorem relates recursively presented groups to finitely presented ones, linking to Church–Turing thesis discussions and implications for the Markov property of groups. Decidability holds for classes like free groups (via Nielsen reduction and Stallings foldings), finite groups (trivial via Cayley table), and linear groups over fields studied by Issai Schur and Alexander Malcev.

Connections to group properties and constructions

Decidability often aligns with algebraic or geometric properties: hyperbolic groups (à la Mikhail Gromov) have linear-time solutions via automatic structures developed by David Epstein, Myles Riley, and collaborators at University of Warwick and University of Chicago. Automatic groups, biautomatic groups, and virtually special groups linked to Ian Agol and Daniel Wise give algorithmic control over the word problem. Constructions such as HNN extensions, amalgamated free products, and wreath products—studied by H. S. M. Coxeter, Otto Schreier, and Reidemeister—affect decidability, with classic examples by Adian and Novikov showing pathological behaviour. Embedding theorems by Higman and techniques from combinatorial group theory elucidate how group properties propagate to word-problem complexity.

Complexity and hardness results

Complexity classifications range from linear-time solutions for free groups and hyperbolic groups to NP-complete, PSPACE, and undecidable instances. Results tying the word problem to complexity theory involve reductions to and from problems studied at Bell Labs and institutions like MIT; connections to P versus NP problem and complexity classes such as NP, PSPACE, and coNP are explored through constructions by Martin Davis-era recursion theory and later complexity-theoretic embeddings. Hardness results demonstrate finitely presented groups whose word problem is as hard as arbitrary recursively enumerable sets, leveraging machinery from G. H. Hardy-era decision problems and later computer science collaborations.

Examples and important classes

Key decidable classes: free groups (Nielsen, Wilhelm Magnus), finite groups (classification uses Emmy Noether-era algebraic methods), free abelian groups, hyperbolic groups (Gromov), automatic groups (Epstein, Thurston-era links), and linear groups over fields (Malcev). Important pathological examples include Boone–Novikov groups, Adian groups illustrating Burnside-type pathologies studied by Sergei Adian, and Higman's universal finitely presented group. Surface groups, knot groups associated with Alexander polynomial studies, and 3-manifold groups linked to work by William Thurston and Grigori Perelman serve as central geometric cases.

Historical developments and key theorems

Origins trace to Dehn's 1911 questions about surface groups, followed by mid-20th-century undecidability breakthroughs by Novikov and Boone. Higman's embedding theorem and later geometric group theory advances by Gromov, Thurston, Agol, and Wise reframed decidability in geometric terms. The Novikov–Boone results catalyzed cross-pollination between logic (Gödel), computability (Turing), and algebra, producing an extensive literature involving University of Cambridge, Princeton, Moscow State University, and many contributors across Europe and North America.

Category:Group theory