群的文字题Word problems for groups

组合群论始于瓦尔特·冯·戴克，他是菲利克斯·克莱因的学生。相关论文于1882年发表，第二年又发表了第二篇论文。他的目的是研究双曲空间的离散等距群。1882年的论文Gruppentheoretische Studien Ⓣ（群论研究）中首次出现了我们所知的群呈现。他假设（没有严格证明）每个有限秩的自由群的存在，并给出了一个结果（同样没有严格证明）：每个m生成元群都可以通过向秩为m的自由群添加关系来得到。他凭直觉知道如何判断自由群中的一个词是否平凡——对词中出现的每个生成元$a$，进行所有$aa^{-1}$和$a^{-1}a$的消去。

Heinrich Tietze于1908年发表了论文Über die topologischen Invarianten mehrdimensionaler MannigfaltigkeitenⓉ（《多维流形的拓扑不变量》）。这篇论文的拓扑部分基于儒勒·昂利·庞加莱在1895年引入的基本群概念。在1908年的论文中，Tietze定义了流形的基本群，并证明了它是一个拓扑不变量。为此，他引入了Tietze变换。他证明了同一个群的任意两个有限表现都可以通过应用有限多个Tietze变换相互转化。他写道：-

人们立刻注意到，两个群可能是同构的，尽管它们是用不同的生成元和定义关系系统定义的。……然而，无论是刻画给定群的所有抽象生成方式的总体这一一般问题，还是寻找一种方法来判断由各自表现给出的两个群是否同构这一特殊问题，都尚未解决。

1910年，马克斯·登发表了Über die Topologie des dreidimensionalen Raumes Ⓣ（《三维空间的拓扑学》）。在这篇论文中，他在儒勒·昂利·庞加莱工作的基础上，考虑了两个纽结何时相同的问题。在这里，他将基本群作为一个关键不变量来处理，而这个群自然地以表现的形式出现。他很快意识到，纽结理论问题是关于有限表现群的更一般问题的特例。他在1911年的论文Über unendliche diskontinuierliche GruppenⓉ（《论无限不连续群》）中明确提出了这些群论问题。我们引用该论文中给出马克斯·登关于群的字的问题的表述：-

一般的不连续群由n个生成元和它们之间的m个关系给出，如瓦尔特·冯·戴克所定义（Math. Ann.，20和22）。然而，那些工作的结果本质上涉及有限群。以这种方式定义的一般群论目前在无限情形下显得非常不发达。这里首先有三个基本问题，它们的解决非常困难，若不深入钻研这一主题就不可能解决。

1. 恒等问题[现在称为词问题]：群的一个元素被表示为生成元的乘积。要求给出一种方法，通过有限步数判定该元素是否为单位元。

2. 变换问题[现在称为共轭问题]：给定群中任意两个元素S和T。寻求一种方法来判断S和T是否可以相互变换，即是否存在群中元素U满足关系$S = UTU^{-1}$。

3. 同构问题：给定两个群，要判断它们是否同构（并且进一步，判断一个群的生成元与另一个群的元素之间的给定对应是否为同构）。

这些问题的困难程度非常不同。……拓扑学中的工作已经必然使人遇到它们。每条纽结空间曲线，为了被完全理解，都要求在特殊情形下解决上述三个问题。

注意，共轭问题与字的問題之间存在简单的联系。如果一个人能解决某个特定群中的共轭问题，那么他就能解决字的問題。因为如果一个字w共轭于单位元，那么它就等于该群的单位元。马克斯·登还在这篇1911年的论文中证明了，一个有限表现群可以有一个不是有限表现的子群。他还解决了具有如下性质的有限表现群的同构问题和共轭问题：每个生成元在每一个定义关系中至多出现两次。

1912年，马克斯·登研究了可定向闭二维流形的基本群的字问题和共轭问题。这些是1-关系群，即具有单个定义关系的呈示的群。他在Transformationen der Kurven auf zweiseitigen Flächen Ⓣ（《双侧曲面上曲线的变换》）（1912）中表明，在特殊情形下，人们可以用一种直接的方法解决字问题——今天称为马克斯·登算法。在这种情形下，人们可以构造群生成元中的一列有限个字$u_{1} , v_{1} , u_{2} , v_{2} , ... u_{n} , v_{n}$，具有以下性质。作为群中的元素有$u_{i} = v_{i}$，对每个$i$，$v_{i}$比$u_{i}$短，并且具有这样的性质：如果$w$是生成元中表示单位元的任意一个字，那么至少有一个$u_{i}$是$w$的子字。当具有这些性质的一列字存在时，人们可以容易地解决字问题。因为给定一个字$w$，人们查看它是否包含一个u$_{i}$。如果它不包含，那么$w$不是单位元。如果它确实包含一个$u_{i}$，那么把$u_{i}$替换为$v_{i}t$，得到一个新字$w'$。然后继续这个过程，查看$w'$是否包含一个$u_{i}$。这个过程必须在有限步内终止，因为每次把一个$u_{i}$替换为一个$v_{i}$时，都得到一个更短的字。

马克斯·登知道这个问题很困难，并在数学中提出了一种全新类型的问题。他写道：-

解决所有群的这个问题也许就像解决所有数学问题一样不可能。

马克斯·登在1914年解决了三叶结群的这个问题。他用他的解答表明，右三叶结和左三叶结是不同的。顺便提一下，我们注意到，Waldhausen在1968年解决了所有纽结群的这个问题。

我们现在想沿着两条路线前进，一条针对自由群，一条针对1-关系群。首先注意，自由群中的字问题是容易解决的。正如瓦尔特·冯·戴克所指出的，只需使用自由约化（但要得到严格证明还需要更多，我们将在下面讨论）。

1921年，Jakob Nielsen发表了Om Regning med ikke kommutative Faktoren og dens Anvendelse in Gruppeteorien Ⓣ（《论非交换环及其在群论中的应用》）。在这篇论文中，他表明，给定自由群中的一组字$\{ u_{1} , u_{2} , ..., u_{m} \}$，人们可以构造它们生成的子群的一组自由生成元。特别地，他可以推出自由群的有限生成子群必然是自由的。他的工作受到字问题研究的推动。他还给出了一种解决自由群中成员问题的方法，即一种算法，用来判定自由群中给定的字$w$是否包含在由$\{ u_{1} , u_{2} , ..., u_{m} \}$生成的子群中。

直到1958年，Mihailova才给出成员问题的一般陈述：

成员问题：设$G = < X | R >$是一个有限表现，$U$是字母表$X$中词的有限集合$\{ u_{1} , u_{2} , ..., u_{m} \}$。设$H$是由$U$生成的$G$的子群。给定生成元$X$中的一个词$w$，能否判定$w$是否在$H$中？

当$\{ u_{1} , u_{2} , ..., u_{m} \}$是$X$的子集时，成员问题也称为广义词问题。

Otto Schreier于1926年1月在汉堡参加了Kurt Reidemeister的一次讲座。在这次讲座中，Reidemeister描述了如何为有限呈示群中的有限指数正规子群找到一个呈示。讨论班之后，Schreier思考了Reidemeister的方法，并最终看到了如何将该方法推广到可数生成群中可能具有无限指数的任意子群。借助这一方法，他得以推广Nielsen关于自由群子群的结果，证明自由群的每个子群都是自由的。他于1927年发表了这些结果，同时给出了自由群中字问题解的一个简单而严格的证明。在这篇1927年的论文中，他还引入了带 amalgamation 的自由积的概念。

Nielsen于1955年回到可数秩自由群的问题。他指出，若$G = < X | R >$且$F$是集合$X$上的自由群，则可定义一个从$F$到$G$的自然同态。设$K$是该同态的核，于是$K$是自由群$F$中字集$R$的正规闭包。那么$G$的字问题等价于判定$F$中哪些元素属于$K$的问题。他写道：-

若K由生成$K$的给定无限元素集$S = \{ a_{1} , a_{2} , .... \}$确定，则存在函数L(n)，使得K中长度不超过n的所有元素都包含在由S的子集$\{ a_{1} , a_{2} , ...., a_{L} \}$生成的子群$K_{L}$中；且对于$K_{L}$，可在有限步内构造一组基。然而，除非能从$S$的结构中获得进一步信息，一般无法确定L对n的依赖关系。因此，只有对有限生成群$K$，才能在有限次检验中无条件地保证其元素的识别。

1926年，埃米尔·阿廷解决了辫群的字问题。

现在来看单关系群。这类群字问题的解决始于马克斯·登，他陈述了Freiheitssatz：

设$G = < A | r = 1 >$，其中$r$是自由且循环约化的。设$U$是$A$的子集，具有性质：并非$r$中出现的每个生成元都在$U$中。则$U$自由生成$G$的一个自由子群。

马克斯·登对这一结果的证明并不满意，因此，他有一位优秀的研究生威廉·马格努斯，便把给出严格证明的任务交给了这位学生。威廉·马格努斯于1930年解决了马克斯·登交给他的问题。Schreier引入了带 amalgamation 的自由积概念，威廉·马格努斯使用了这些思想，但他的证明并非基于Schreier的结果，而是更愿意重新证明他所需要的特殊情形。次年，威廉·马格努斯发表了一篇论文，包含单关系群字问题的一个特殊情形，随后于1932年发表了该类群字问题解的完整证明。

我们已经给出了若干例子，说明某些群类的字问题已被证明可解，但对于字问题不可解的群却只字未提。直到20世纪50年代，人们只能得到正面结果，因为即使要陈述“找到一个具有不可解字问题的群”这一问题，并以数学家们有机会给出证明所需的形式精确性来表达，也需要全新的方法。正如和威廉·马格努斯所述：-

判定问题的答案是一种算法，或一种普遍有效的过程。在大卫·希尔伯特和马克斯·登的时代，关于这些概念所能说的只是：见到一个就知道是它。

然而，如果人们只是“见到一个就知道是它”，那么怎么可能证明不存在这样的算法呢？这需要可计算性理论和数理逻辑的发展，才能使问题变得精确，但这些领域不仅提供了明确的问题，还提供了问题的解答。

20世纪30年代，库尔特·弗雷德里希·哥德尔研究了形式逻辑中的符号操作如何能用自然数上的函数来模拟。这些函数由简单函数构建而成。独立于库尔特·弗雷德里希·哥德尔，丘奇正在发展λ演算，旨在澄清数学的基础，特别是变量的含义。这一发展导致了递归函数的研究。克林是普林斯顿丘奇的博士生，他被分配了一个项目，任务是确定哪些函数是λ可定义的。起初，克林在这个项目上毫无进展，后来有一天他去看牙医拔两颗智齿。坐在牙医的椅子上等待这一不愉快经历时，灵感突然降临，他一下子看到了解决问题的途径。六个月内，他完全解决了这个问题。1933年，丘奇提出了今天被称为“丘奇论题”的内容，它指出λ可定义性是“可计算函数”的精确概念。这不是一个定理，只是说“可计算函数”这一模糊概念可以给出λ可定义性这一严格定义。1936年，艾伦·图灵提出了艾伦·图灵机的概念，并提出“可计算函数”就是可由艾伦·图灵机计算的函数。很快人们就证明，一个函数是λ可定义的当且仅当它可由艾伦·图灵机计算，因此这两个概念是等价的。这足以让几乎所有数学家接受，这些等价的概念严格体现了“可计算函数”的直观概念。

给定一个问题$P$，其中$P$是无限的问题集$Q_{i}$，我们说$P$是可解的，如果我们能计算函数$f : P \to \{ Y, N \}$，使得当$Q_{i}$的答案为是时$f(Q_{i}) = Y$，当$Q_{i}$的答案为否时$f(Q_{i}) = N$。如果我们能证明这样的函数$f$不能由艾伦·图灵机计算，那么问题$P$就是不可解的。在继续描述历史之前，让我们先定义一些概念。

一个集合$S$是递归可枚举的，如果存在一个算法可以列出$S$的元素，这里我们使用标准的艾伦·图灵机计算模型。

一个集合$S$是递归的，如果$S$及其补集都是递归可枚举的。

数学中所有不可判定的问题都是由于存在递归可枚举但非递归的集合这一事实。对于一个有限呈示群，我们上面描述的所有判定问题——字问题、共轭问题等——都是递归可枚举但非递归的。我们的意思是，给定任何有限呈示群，我们可以启动一个程序，如果我们给出的字等于群单位元，它就会说YES。然而，如果它不等于，它不会说NO，所以我们坐等程序说YES，但如果什么也没发生，我们就无法判断这个字是否平凡。如果有可能启动第二个程序，在我们给出的字不等于群单位元时说NO，那么我们就可以同时启动两个程序，等待其中一个完成。然而，由于这个问题不是递归的，不存在会说NO的程序。让我们回到群的字问题的历史。

1938年，丘奇提出应该利用新的严格的可计算定义来证明群的字问题不可解。1946年和1947年，波斯特取得了第一个突破。波斯特的运气真是难以置信地差。他在库尔特·弗雷德里希·哥德尔和丘奇之前就已经产生了他们的大部分想法，但他的工作被认为不适合发表。常常有这种情况：当某人提出一个真正革命性的想法时，世界还没有准备好接受它，这里似乎就是这种情况。尽管遭受了工作无法发表的打击，波斯特继续工作，并在与艾伦·图灵大约同时提出了艾伦·图灵机的想法。然而，艾伦·图灵的工作很快就在波斯特之前发表了，而后者鉴于自己在发表方面的糟糕经历，并不急于付印。当波斯特在艾伦·图灵之后五年终于发表时，他给出了今天所谓的波斯特对应问题。

波斯特对应问题：给定一个字母表$A = \{ a_{1} , a_{2} , ...., a_{n}\}$和一个无限的字对集合$S$，其中$( u_{i} , v_{i})$，$u_{i} , v_{i}$是$A$中的字。判定$S$中是否有任何一对的两个分量相等。

波斯特证明了波斯特对应问题不可解。丘奇看到了波斯特的论文，并建议他尝试证明半群的字问题不可解。他成功了，并于1947年发表了半群的字问题不可解的证明。然而，波斯特又一次运气不佳——马尔可夫在同一年独立于波斯特发表了相同结果的证明。

如果波斯特的半群能够嵌入到一个群中，那么群的字问题就会同时被否定解决。然而，情况并非如此，群的字问题仍然悬而未决。艾伦·图灵在阅读了波斯特的论文后了解到了群的字问题。他思考了这个问题十天，然后宣称他已经解决了它。他安排了一个研讨会来描述这个证明，但就在研讨会之前，他发现了一个错误。然而，他还是有所收获，他证明了可消半群的字问题是不可解的。

1954年，Bill Boone发表了一篇论文，在其中定义了拟威廉·马格努斯问题并证明了它不可解。

拟威廉·马格努斯问题：设群$G$由有限呈示$< A | R >$给出。判定字母表$A$中的一个字$w$作为$G$的元素是否等于$A$中的一个字$u$，其指数全为正（即字$u$中不出现生成元的逆）。

Boone是丘奇的博士生，这一结果出现在Boone1952年的学位论文中。到1956年，Boone已经证明了群的字问题不可解。然而，Petr Sergeevich Novikov一直在研究这个问题，并在1952年宣布他证明了群的字问题不可解。很少有人相信他，因为尽管他是一位知名数学家，但他已经51岁，而且在此之前主要发表数学物理论文。马克斯·登没能活到看见他的基本问题被解决。他于1952年去世，就在彼得·诺维科夫宣布其结果前不久。然而，在那个阶段，彼得·诺维科夫没有发表证明，所以Boone很高兴继续他自己最终成功的尝试。

然而，一种不同的方法被证明具有高度重要性。格雷厄姆·希格曼、伯恩哈德·诺伊曼和Hanna Neumann在1949年引入了现在称为HNN扩张的概念。格雷厄姆·希格曼利用HNN扩张取得了重大突破。首先给出一个定义：

一个有限生成群$G$是递归可表示的，如果它有一个展示$< A | R >$，其中$R$是一个递归可枚举的字集。

格雷厄姆·希格曼在1961年证明了格雷厄姆·希格曼嵌入定理：

格雷厄姆·希格曼嵌入定理：一个有限生成群$H$能嵌入一个有限表示群，当且仅当$H$是递归可表示的。

这导致了字问题不可解性的一个非常不同的证明。取$H(S) = < a, b, c, d | a^{-i}ba^{i} = c^{-i}dc^{i}, i \in S >$，其中$S$是一个递归可枚举但非递归的集合。那么$H(S)$是自由群$< a, b >$与自由群$<c, d>$关于子群$< a^{-i}ba^{i} | i \in S >$和$< c^{-i}dc^{i} | i \in S >$的融合自由积。于是$a^{-i}ba^{i}c^{-i}d^{-1}c^{i} = 1$在$H(S)$中当且仅当$i$在$S$中。但这是不可判定的。因此$H(S)$有不可解的字问题。最后利用格雷厄姆·希格曼嵌入将$H(S)$嵌入一个有限表示群$G(S)$，得到一个具有不可解字问题的有限表示群。

我们注意到格雷厄姆·希格曼也使用他的嵌入定理证明了存在一个有限表现群$U$，使得给定任何有限表现群$G$，则$G$同构于$U$的子群。

谢尔盖·阿迪安是Petr Sergeevich Novikov的学生，他在1957年和1958年基于马尔可夫性质的思想证明了一系列判定问题。

马尔可夫 性质：有限呈现群的一个抽象性质 $P$ 是一个 马尔可夫 性质，如果存在两个有限呈现群 $G(+)$ 和 $G(-)$，使得

(a) $G(+)$具有性质$P$

(b) 如果$G(-)$嵌入到一个有限呈现群$G$中，那么$G$不具有性质$P$。

例如，“有限”是一个马尔可夫性质——取$G(+)$为2阶循环群，$G(-)$为无限循环群。

有限呈现群的一个抽象性质$P$是递归可识别的，如果给定一个任意的有限呈现，可以用艾伦·图灵机器计算具有该呈现的群是否具有性质$P$。换句话说，存在一个算法来确定具有给定呈现的群是否满足性质$P$。

谢尔盖·阿迪安在1957年证明了以下定理：

定理：
如果$P$是有限呈现群的一个马尔可夫性质，那么$P$不是递归可识别的。

由此得到以下推论：

推论：
有限呈现群的以下性质不是递归可识别的，即

（i）平凡群；
（ii）有限；
（iii）阿贝尔；
（iv）幂零；
（v）可解；
（vi）自由；
（vii）无挠；
（viii）剩余有限；
（ix）具有可解的字问题；
（x）单。

我们注意到，尽管给定一个有限群呈现，我们不能递归地识别该群是否为单群，但如果我们知道一个给定的呈现定义了一个单群，那么该群具有可解的字问题。

作为谢尔盖·阿迪安定理的一个推论，还可以得到同构问题是不可解的，因为无法确定一个群是否同构于平凡群。

1959年，Gilbert Baumslag、Bill Boone和伯恩哈德·诺伊曼证明了以下定理：

定理：
存在一个有限呈现群$G$，使得没有算法判定给定生成元中的一个字是否表示

（i）$G$的中心的一个元素；
（ii）与一个给定元素交换的元素；
（iii）一个$n$次幂，其中$n > 1$固定；
（iv）具有有限多个共轭的元素；
（v）一个换位子；
（vi）一个有限阶元素。

最后让我们指出，Mihailova 在 1958 年引入了隶属问题并证明了：

定理：
设$F$是秩为2的自由群，$G$是$F$与自身的直积。则$G$有一个子群$L$，其成员问题不可解。

Miller 在 1971 年进一步研究了 $G = F \times F$，证明了人们无法判定是否 $L = G$。他还证明了 $G$ 有一个子群 $L$，其共轭问题是不可解的。这给出了字问题可解但共轭问题不可解的群。

作者：J J O'Connor 和 E F Robertson
最后更新：2008年7月