Word problem for groups: Difference between revisions

Revision as of 02:08, 3 April 2024

Latest revision as of 11:24, 24 July 2025

(11 intermediate revisions by 6 users not shown)

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. More precisely, if <math>A</math> is a finite set of [[Generating set of a group|generators]] for <math>G</math> then the word problem is the membership problem for the [[formal language]] of all words in <math>A</math> and a formal set of inverses that map to the identity under the natural map from the [[free monoid with involution]] on <math>A</math> to the group <math>G</math>. If <math>B</math> is another finite generating set for <math>G</math>, then the word problem over the generating set <math>B</math> is equivalent to the word problem over the generating set <math>A</math>. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group <math>G</math>.

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]].

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. More precisely, ifIf <math>A</math> is a finite set of [[Generating set of a group|generators]] for <math>G</math>, then the word problem is the membership problem for the [[formal language]] of all words in <math>A</math> and a formal set of inverses that map to the identity under the natural map from the [[free monoid with involution]] on <math>A</math> to the group <math>G</math>. If <math>B</math> is another finite generating set for <math>G</math>, then the word problem over the generating set <math>B</math> is equivalent to the word problem over the generating set <math>A</math>. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group <math>G</math>.

The related but different '''uniform word problem''' for a class <math>K</math> of recursively presented groups is the algorithmic problem of deciding, given as input a [[presentation of a group|presentation]] <math>P</math> for a group <math>G</math> in the class <math>K</math> and two words in the generators of <math>G</math>, whether the words represent the same element of <math>G</math>. Some authors require the class <math>K</math> to be definable by a [[recursively enumerable]] set of presentations.

Line 6 ⟶ 9:

== History ==

Throughout the history of the subject, computations in groups have been carried out using various [[Normal form (abstract rewriting)|normal forms]]. These usually implicitly solve the word problem for the groups in question. In 1911 [[Max Dehn]] proposed that the word problem was an important area of study in its own right,{{sfn|Dehn|1911}} together with the [[conjugacy problem]] and the [[group isomorphism problem]]. In 1912 he gave an algorithm that solves both the word and conjugacy problem for the [[fundamental group]]s of closed orientable two-dimensional manifolds of genus greater than or equal to 2.{{sfn|Dehn|1912}} Subsequent authors have greatly extended [[Small cancellation theory#Dehn's algorithm|Dehn's algorithm]] and applied it to a wide range of group theoretic [[decision problem]]s.<ref>{{Citation|last=Greendlinger|first=Martin|date=June 1959|title=Dehn's algorithm for the word problem|journal=[[Communications on Pure and Applied Mathematics]]|volume=13|issue=1|pages=67–83|doi=10.1002/cpa.3160130108|postscript=.}}</ref><ref>{{Citation|last=Lyndon|first=Roger C.|author-link=Roger Lyndon|date=September 1966|title=On Dehn's algorithm|journal=[[Mathematische Annalen]]|volume=166|issue=3|pages=208–228|doi=10.1007/BF01361168|hdl=2027.42/46211|s2cid=36469569|postscript=.|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002296799&L=1|hdl-access=free}}</ref><ref>{{Citation|author-link1=Paul Schupp|last1=Schupp|first1=Paul E.|date=June 1968|title=On Dehn's algorithm and the conjugacy problem|journal=Mathematische Annalen|volume=178|issue=2|pages=119–130|doi=10.1007/BF01350654|s2cid=120429853|postscript=.|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002300036&L=1}}</ref>

It was shown by [[Pyotr Novikov]] in 1955 that there exists a finitely presented group <math>G</math> such that the word problem for <math>G</math> is [[Undecidable problem|undecidable]].<ref>{{Citation|last=Novikov|first=P. S.|author-link=Pyotr Novikov|year=1955|title=On the algorithmic unsolvability of the word problem in group theory|language=ru| zbl=0068.01301 | journal=[[Proceedings of the Steklov Institute of Mathematics]]|volume=44|pages=1–143}}</ref> It follows immediately that the uniform word problem is also undecidable. A different proof was obtained by [[William Boone (mathematician)|William Boone]] in 1958.<ref>{{Citation|last=Boone|first=William W.| author-link=William Boone (mathematician) | year=1958|title=The word problem|journal=[[Proceedings of the National Academy of Sciences]]|volume=44|issue=10|pages=1061–1065|url=http://www.pnas.org/cgi/reprint/44/10/1061.pdf|doi=10.1073/pnas.44.10.1061|zbl=0086.24701 |pmc=528693|pmid=16590307|bibcode=1958PNAS...44.1061B|doi-access=free}}</ref>

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.

It is important to realize that theThe 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 48 ⟶ 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 57 ⟶ 60:

Examples with unsolvable word problems are also known:

*Given a recursively enumerable set <math>A</math> of positive integers that has insoluble membership problem, <math>\langle a, b, c, d \, | \, a^n b a^n = c^n d c^n : n \in A \rangle</math> is a finitely generated group with a recursively enumerable presentation whose word problem is insoluble{{sfn|Collins|Zieschang|19901993|p=149}}

*Every finitely generated group with a recursively enumerable presentation and insoluble word problem is a subgroup of a finitely presented group with insoluble word problem{{sfn|Collins|Zieschang|1993|loc=Cor. 7.2.6}}

*The number of relators in a finitely presented group with insoluble word problem may be as low as 14 {{sfn|Collins|1969}} or even 12.{{sfn|Borisov|1969}}{{sfn|Collins|1972}}

Line 146 ⟶ 149:

\end{cases}</math>

:: '''Boone-RogersBoone–Rogers Theorem:''' There is no uniform [[partial algorithm]] that solves the word problem in all finitely presented groups with solvable word problem.

In other words, the uniform word problem for the class of all finitely presented groups with solvable word problem is unsolvable. This has some interesting consequences. For instance, the [[Higman embedding theorem]] can be used to construct a group containing an isomorphic copy of every finitely presented group with solvable word problem. It seems natural to ask whether this group can have solvable word problem. But it is a consequence of the Boone-RogersBoone–Rogers result that:

:: '''Corollary:''' There is no universal solvable word problem group. That is, if <math>G</math> is a finitely presented group that contains an isomorphic copy of every finitely presented group with solvable word problem, then <math>G</math> itself must have unsolvable word problem.

'''Remark:''' Suppose <math>G = \langle X \, | \, R \rangle</math> is a finitely presented group with solvable word problem and <math>H</math> is a finite subset of <math>G</math>. Let <math>H^* = \langle H \rangle</math>, be the group generated by <math>H</math>. Then the word problem in <math>H^*</math> is solvable: given two words <math>h, k</math> in the generators <math>H</math> of <math>H^*</math>, write them as words in <math>X</math> and compare them using the solution to the word problem in <math>G</math>. It is easy to think that this demonstrates a uniform solution of the word problem for the class <math>K</math> (say) of finitely generated groups that can be embedded in <math>G</math>. If this were the case, the non-existence of a universal solvable word problem group would follow easily from Boone-RogersBoone–Rogers. However, the solution just exhibited for the word problem for groups in <math>K</math> is not uniform. To see this, consider a group <math>J = \langle Y \, | \, T \rangle \in K</math>; in order to use the above argument to solve the word problem in <math>J</math>, it is first necessary to exhibit a mapping <math>e : Y \to G</math> that extends to an embedding <math>e^* : J \to G</math>. If there were a recursive function that mapped (finitely generated) presentations of groups in <math>K</math> to embeddings into <math>G</math>, then a uniform solution of the word problem in <math>K</math> could indeed be constructed. But there is no reason, in general, to suppose that such a recursive function exists. However, it turns out that, using a more sophisticated argument, the word problem in <math>J</math> can be solved ''without'' using an embedding <math>e : J \to G</math>. Instead an ''enumeration of homomorphisms'' is used, and since such an enumeration can be constructed uniformly, it results in a uniform solution to the word problem in <math>K</math>.

===Proof that there is no universal solvable word problem group===

Line 188 ⟶ 191:

\end{cases}</math>

But this uniformly solves the word problem for the class of all finitely presented groups with solvable word problem, contradicting Boone-RogersBoone–Rogers. This contradiction proves <math>G</math> cannot exist.

==Algebraic structure and the word problem==

There are a number of results that relate solvability of the word problem and algebraic structure. The most significant of these is the [[Boone-HigmanBoone–Higman theorem]]:

::A finitely presented group has solvable word problem if and only if it can be embedded in a [[simple group]] that can be embedded in a finitely presented group.

Line 203 ⟶ 206:

What is remarkable about this is that the algebraically closed groups are so wild that none of them has a recursive presentation.

The oldest result relating algebraic structure to solvability of the word problem is [[Alexander Kuznetsov|Kuznetsov]]'s theorem:

::A recursively presented simple group <math>S</math> has solvable word problem.

Line 260 ⟶ 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}}

* {{Citation | last1=Collins | first1=Donald J. | title=On a group embedding theorem of V. V. Borisov | mr=0314998 | year=1972 | journal=[[London Mathematical Society|Bulletin of the London Mathematical Society]] | issn=0024-6093 | volume=4 | issue=2 | pages=145–147 | doi=10.1112/blms/4.2.145}}

* {{Citation | last1=Collins | first1=Donald J. | title=A simple presentation of a group with unsolvable word problem | mr=840121 | year=1986 | journal=Illinois Journal of Mathematics | issn=0019-2082 | volume=30 | issue=2 | pages=230–234 | doi=10.1215/ijm/1256044631| doi-access=free }}

*{{citation

* {{Citation | last1=Collins | first1=Donald J. | last2=Zieschang | first2=H. | title=Combinatorial group theory and fundamental groups | publisher=[[Springer-Verlag]] | mr=1099152 | year=1990 | pages=166}}

| last1 = Collins | first1 = D. J.

| last2 = Zieschang | first2 = H.

| contribution = Combinatorial group theory and fundamental groups

| doi = 10.1007/978-3-642-58013-0

| isbn = 3-540-54700-2

| ___location = Berlin

| mr = 1265270

| pages = 1–166

| publisher = Springer

| series = Encyclopaedia of Mathematical Sciences

| title = Algebra VIII: Combinatorial Group Theory, Applications to Geometry

| volume = 58

| year = 1993}}

*{{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}}