Word problem for groups: Difference between revisions

Revision as of 01:23, 8 April 2025

Revision as of 01:24, 8 April 2025

Line 1:

{{Short description|Problem in finite group theory}}

{{CS1 config|mode=cs2}}

In [[mathematics]], especially in the area of [[abstract algebra]] known as [[combinatorial group theory]], the '''word problem''' for a [[finitely generated group]] <math>G</math> is the algorithmic problem of deciding whether two words in the generators represent the same element of <math>G</math>. The word problem is a well-known example of an [[undecidable problem]].

Line 14 ⟶ 15:

The word problem was one of the first examples of an unsolvable problem to be found not in [[mathematical logic]] or the [[theory of algorithms]], but in one of the central branches of classical mathematics, [[abstract algebra|algebra]]. As a result of its unsolvability, several other problems in combinatorial group theory have been shown to be unsolvable as well.

The word problem is in fact solvable for many groups <math>G</math>. For example, [[polycyclic group]]s have solvable word problems since the normal form of an arbitrary word in a polycyclic presentation is readily computable; other algorithms for groups may, in suitable circumstances, also solve the word problem, see the [[Todd–Coxeter algorithm]]<ref>{{cite journalcitation |last1=Todd |first1=J. |last2=Coxeter |first2=H.S.M. |title=A practical method for enumerating cosets of a finite abstract group |journal=Proceedings of the Edinburgh Mathematical Society |volume=5 |issue=1 |pages=26–34 |date=1936 |doi=10.1017/S0013091500008221 |url=|doi-access=free }}</ref> and the [[Knuth–Bendix completion algorithm]].<ref>{{cite bookcitation |first1=D. |last1=Knuth |first2=P. |last2=Bendix |chapter=Simple word problems in universal algebras |chapter-url=https://books.google.com/books?id=KIDiBQAAQBAJ&pg=PA263 |editor-first=J. |editor-last=Leech |title=Computational Problems in Abstract Algebra: Proceedings of a Conference Held at Oxford Under the Auspices of the Science Research Council Atlas Computer Laboratory, 29th August to 2nd September 1967 |publisher=Springer |date=2014 |orig-year=1970 |isbn=9781483159423 |pages=263–297 |url=}}

</ref> On the other hand, the fact that a particular algorithm does not solve the word problem for a particular group does not show that the group has an unsolvable word problem. For instance Dehn's algorithm does not solve the word problem for the fundamental group of the [[torus]]. However this group is the direct product of two infinite cyclic groups and so has a solvable word problem.

Line 50 ⟶ 51:

*Finitely generated [[free abelian group]]s

*[[Polycyclic group]]s

*Finitely generated recursively [[Absolute presentation of a group|absolutely presented group]]s,<ref>{{cite journalcitation |first=H. |last=Simmons |title=The word problem for absolute presentations |journal=J. London Math. Soc. |volume=s2-6 |issue=2 |pages=275–280 |date=1973 |doi=10.1112/jlms/s2-6.2.275 |url=}}</ref> including:

**Finitely presented simple groups.

*Finitely presented [[residually finite]] groups

*One relator groups<ref>{{cite bookcitation |first1=Roger C. |last1=Lyndon |first2=Paul E |last2=Schupp |title=Combinatorial Group Theory |publisher=Springer |date=2001 |isbn=9783540411581 |pages=1–60 |url=https://books.google.com/books?id=aiPVBygHi_oC&pg=PP1}}</ref> (this is a theorem of Magnus), including:

**Fundamental groups of closed orientable two-dimensional manifolds.

*Combable groups

Line 262 ⟶ 263:

== References ==

* {{cite bookcitation |first1=W.W. |last1=Boone |first2=F.B. |last2=Cannonito |first3=Roger C. |last3=Lyndon |title=Word problems : decision problems and the Burnside problem in group theory |publisher=North-Holland |date=1973 |isbn=9780720422719 |pages= |url=https://www.sciencedirect.com/bookseries/studies-in-logic-and-the-foundations-of-mathematics/vol/71/suppl/C |series=Studies in logic and the foundations of mathematics |volume=71}}

* {{cite journalcitation | last1 = Boone | first1 = W. W. | last2 = Higman | first2 = G. | year = 1974 | title = An algebraic characterization of the solvability of the word problem | journal = J. Austral. Math. Soc. | volume = 18 | pages = 41–53 | doi=10.1017/s1446788700019108| doi-access = free }}

* {{cite journalcitation | last1 = Boone | first1 = W. W. | last2 = Rogers Jr | first2 = H. | year = 1966 | title = On a problem of J. H. C. Whitehead and a problem of Alonzo Church | journal = Math. Scand. | volume = 19 | pages = 185–192 | doi=10.7146/math.scand.a-10808| doi-access = free }}

*{{Citation | last1=Borisov | first1=V. V. | title=Simple examples of groups with unsolvable word problem | mr=0260851 | year=1969 | journal=Akademiya Nauk SSSR. Matematicheskie Zametki | issn=0025-567X | volume=6 | pages=521–532}}

* {{Citation | last1=Collins | first1=Donald J. | title=Word and conjugacy problems in groups with only a few defining relations | mr=0263903 | year=1969 | journal=Zeitschrift für Mathematische Logik und Grundlagen der Mathematik | volume=15 | issue=20–22 | pages=305–324 | doi=10.1002/malq.19690152001}}

Line 285 ⟶ 286:

*{{Citation | last1=Dehn | first1=Max | author1-link=Max Dehn | title=Über unendliche diskontinuierliche Gruppen | doi=10.1007/BF01456932 | mr=1511645 | year=1911 | journal=[[Mathematische Annalen]] | issn=0025-5831 | volume=71 | issue=1 | pages=116–144| s2cid=123478582 |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0071&DMDID=DMDLOG_0013&L=1}}

*{{Citation | last1=Dehn | first1=Max | author1-link=Max Dehn | title=Transformation der Kurven auf zweiseitigen Flächen | doi=10.1007/BF01456725 | mr=1511705 | year=1912 | journal=[[Mathematische Annalen]] | issn=0025-5831 | volume=72 | issue=3 | pages=413–421| s2cid=122988176 |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0072&DMDID=DMDLOG_0039&L=1}}

* {{cite journalcitation |first=A.V. |last=Kuznetsov |title=Algorithms as operations in algebraic systems |journal=Izvestia Akad. Nauk SSSR Ser Mat |volume=13 |issue=3 |pages=81 |date=1958 |doi= |url=}}

* {{cite bookcitation |first=C.F. |last=Miller |chapter=Decision Problems for Groups — Survey and Reflections |chapter-url=https://link.springer.com/chapter/10.1007/978-1-4613-9730-4_1 |title=Algorithms and Classification in Combinatorial Group Theory |series=Mathematical Sciences Research Institute Publications |publisher=Springer |date=1991 |volume=23 |isbn=978-1-4613-9730-4 |pages=1–60 |url= |doi=10.1007/978-1-4613-9730-4_1}}

* {{Citation | last1=Nyberg-Brodda | first1=Carl-Fredrik | title=The word problem for one-relation monoids: a survey | year=2021 | journal=[[Semigroup Forum]] | volume=103 | issue=2 | pages=297–355 | doi=10.1007/s00233-021-10216-8 | arxiv=2105.02853 | doi-access=free }}

*{{Citation | last1=Rotman | first1=Joseph | title=An introduction to the theory of groups | publisher=[[Springer-Verlag]] | isbn=978-0-387-94285-8 | year=1994}}

* {{cite journalcitation | last1 = Stillwell | first1 = J. | year = 1982 | title = The word problem and the isomorphism problem for groups | journal = Bulletin of the AMS | volume = 6 | pages = 33–56 | doi=10.1090/s0273-0979-1982-14963-1| doi-access = free }}

{{DEFAULTSORT:Word Problem For Groups}}