1993年前计算群论史History of Computational Group Theory to 1993

1993年，群论圣安德鲁斯会议在爱尔兰高威举行。Joachim Neubüser是受邀演讲者，并作了题为An invitation to computational group theory的报告。他报告的一部分涉及计算群论（CGT）的历史，我们在下面给出一个版本。我们还给出他关于“关切”的最后一部分的一个版本。

1. 计算群论的一些历史

史前时期（1953年之前）。

群论不仅是由五次方程根式可解性这一极具计算性的问题引发的，而且从以米里迂·拉·马丢发现第一批零星群到奥托·赫尔德确定阶为pqr的群，这些（手工）计算构成了上世纪群论的很大一部分。然而，马克斯·登在1911年对有限呈现群的词问题、共轭问题和同构问题的表述[19]（尽管有先例）可以被视为计算群论真正史前时期的开端，将注意力集中在群论算法的需求上。有两点值得注意：

- 这一挑战来自拓扑学，而非群论内部，而且事实上即使在现在，在群论之外使用群的人也是计算群论的强大“客户”。

- Novikov对字的判定问题算法不可解性的证明，终结了群论能够满足马克斯·登要求的希望。不久之后，人们证明了不存在能够判定一个有限呈现群是否平凡、有限、交换等的算法（关于生动的描述，见G Baumslag的书[3]）。

尽管如此，1936年J A Todd和哈罗德·斯科特·麦克唐纳·考克斯特[64]至少提供了一种通过“陪集枚举”来尝试证明有限性的系统方法，而今天CGT提供了一整套用于研究有限呈现群的方法，这些方法在频繁使用中已被证明相当强大，尽管它们不是判定算法。

在使用真正的计算机之前的时期，我还想提及另外三件事：

- 1948年，H Zassenhaus描述了一种用于空间群分类的算法[65]，该算法很久以后得到了非常实际的应用。

- 1951年，马克斯·纽曼在“曼彻斯特大学计算机落成会议”[47]上的演讲中提出使用概率方法来对256阶群的大量数目获得一些了解。该演讲的标题：“自动计算机对数学方法的影响”在当时是引人注目的，并且应当指出，该阶的（56 092）个群直到1989年才由E A O'Brien确定[54]。

- 然而，也许最值得注意的是其远见性，艾伦·图灵在1945年关于建造电子计算机的一份提案中的引文：“即使我们突然希望从计算氖原子的能级切换到枚举720阶群，也绝对不需要进行任何内部改动”（见[26]，第293页）。

早期历史（1953—1967）

这可以看作是从群的计算方法的首次实现开始的。据我所知，最早的、大约在1953年的工作，是B Haselgrove在剑桥的EDSAC II上对约翰·阿瑟·托德-哈罗德·斯科特·麦克唐纳·考克斯特方法的部分实现（见[35]），以及S Comet在斯德哥尔摩的BARK计算机上对对称群特征标计算方法的部分实现[17]。此后不久，群论的其他领域也被尝试。E T Parker和P J Nicolai对以米里迂·拉·马丢群的类似物进行了一次——不成功的——搜寻[56]，1959年编写了计算置换群子群格的程序[44]，稍后又编写了用于多循环呈现的2-群的程序。随后出现了其他方法和专门研究，这一时期的程序大多用机器码编写，使用各种技巧来节省存储空间，而计算时间（尽管不那么紧迫）也是至关重要的。这一时期的结束大致以1967年牛津会议“抽象代数中的计算问题”为标志[36]，在此期间CGT开始展开，但几乎没有对群论做出能让群论学家大为印象深刻的贡献。其会议录包含了对当时已尝试内容的综述[45]，但也包含了一些引向……的论文。

发现的十年（1967—1977）。

在牛津会议上，一些计算方法首次被提出，这些方法现在（在某些情况下经过变化和改进）已成为CGT系统的主力：Sims处理大置换群的方法[59]，试图从呈现构造重写系统的高德纳-Bendix方法[32]，用于确定子群呈现的约翰·阿瑟·托德-哈罗德·斯科特·麦克唐纳·考克斯特方法的变体[42]。其他方法，如J D Dixon确定特征标表的方法[20]，I D Macdonald的$p$-幂零商方法[41]，以及G Havas用于子群呈现的Reidemeister-Schreier方法[23]，在该会议后的几年内发表。

然而，至少同样重要的是，一些计算方法的应用程序使群论学家意识到了CGT。我提及其中三个：C C Sims在1973年使用他的置换群方法证明了Lyons零星单群的存在[60]，M F 马克斯·纽曼和G Havas使用原始$p$-幂零商方法的扩展确定了阶为$2^{422}$的威廉·伯恩赛德群$B(4, 4)$[49]，以及确定了4维空间的（4783个同构类的）空间群[4]，这不仅使用了Zassenhaus的算法，还利用了使用确定子群格的程序来找到$GL(4, \mathbb{Z})$的极大有限子群的所有子群的可能性。

这一进展鼓励了设计CGT系统的尝试，在这些系统中可以使用各种方法而无需将数据从一个程序转换到另一个程序。到1974年，第一个“亚琛-悉尼群系统”投入运行[11]，1976年John Cannon发表了“群论语言阿瑟·凯莱草案描述”[12]，这可以被视为转向……

现代时期。

大约自1977年以来，计算群论（CGT）的发展正在迅速加快，这一说法可以通过考察四个方面来证明：成果、方法、系统和宣传。

成果。

具体的计算结果，这里再次仅列举部分：Sims证明了阶为4 154 781 481 226 426 191 177 580 544 000 000的Babymonster作为次数为13 571 955 000的置换群的存在性，使用的是基于其置换群技术的非常特殊的实现[61]；Janko的$J_{4}$的存在性则是通过模表示的計算技术证明的[51]。$p$-幂零商技术现在已经足够强大，例如可以证明受限威廉·伯恩赛德群$B(2, 7)$的类18因子的阶为$7^{6366}$[25]。根据M F 纽曼的建议[50]，E A O'Brien实现了一个$p$-群生成程序，足以确定阶为$2^{n}, n ≤ 8$的群（58760个同构类）[54]。制作和检查Cambridge Atlas of Finite Groups[14]——可能是使用最广泛的群论表——涉及大量的实现和群论程序的使用（特别是用于处理特征标），对于列出散在单群的理查德·布饶尔树[24]或完美群[27]的书籍以及其他列表，例如本原或传递置换群的列表，情况也是如此。

方法。

这些以及更多具体的计算之所以成为可能，是因为大量新方法及其被整合到通用和专用系统中。

我已经提到过$p$-群生成方法，它建立在$p$-幂零商算法（pNQ）之上，并与最近探索借助空间群对具有恒定余类的$p$-群族进行分类的可能性相关联[38]。pNQ的另一个非常新的产物是（真）幂零商算法，它沿着有限呈现群的下中心列逐步下降。已经提出了若干方案，其中一些最近已实现，用于寻找有限呈现群的可解因子群，使用了诸如上同调群、模表示或Gröbner基等概念[37]、[55]、[62]。

通过同态像进行研究已成为处理多循环呈现的有限可解群的首选方法[39]，但也已成为处理置换群不可或缺的方法[33]。

研究置换群的方法几乎经历了一场革命，引入了结构理论，如本原群的O'Nan-Scott分类，甚至有限单群的分类，如今例如在某些情况下允许确定次数高达数十万的群的合成列。特别有趣的是，这些置换群的新方法——如今也已变得非常实用——最初是通过对置换群算法复杂性的相当理论性的讨论而引入的。（[46]、[31]、[34]、[8]、[7]、[9]，仅提及关于此主题的众多论文中的一小部分。）

有多种多样的方法可用于处理表示和特征标[53]、[40]，其中许多是交互式的。

CGT中一个长期被忽视但如今发展非常迅速的分支是研究有限域上矩阵群的方法[52]，它们大量利用了Aschbacher分类[1]。

系统。一个程序系统包含多个组成部分：存储管理、一种既可用于交互使用又可用于编写程序的问题导向语言，该语言可以调用系统函数（并可能直接访问数据）、一个可应用于所研究对象的函数库，以及此类对象的库。CGT的第一个通用系统开发于70年代中期，是亚琛-悉尼群系统，其中J 安妮·坎农提供了存储管理（栈处理器）和语言（凯莱）。函数用Fortran编写。该系统发展成为凯莱系统[5]，其函数在1987年左右被半自动地翻译成C。凯莱最近以MAGMA [CP93]之名被重新建模，并扩展为一个超越CGT的通用计算机代数系统。

另一个用于CGT的通用系统称为GAP（Groups, Algorithms, and Programming），于1986年在亚琛启动。其设计受到计算机代数系统Maple的影响：GAP有一个用C语言编写的内核，包含存储管理、GAP语言的解释器（将来还会有编译器）以及基本的时间关键函数。GAP函数的绝大多数是用GAP语言编写的，因此可以被理解、检查和修改，这一点我将在最后一节中评论。

凯莱和GAP都得到了广泛使用。对于凯莱可以给出更精确的数字，因为它必须付费获得许可，J 坎农报告到1990年有超过200个许可证[13]。GAP可以通过ftp免费获得并转发，因此无法完全控制其传播。一个迹象是GAP论坛约有240名成员，以及我们获得的超过350份安装报告。

在70年代末和80年代，编写了许多非常专门的系统，它们被凯莱和GAP吸收或淘汰，还有一些补充了这两个通用系统的范围，其中包括Quotpic [28]，为有限呈现群的因子群计算步骤提供了非常好的可视化，MOLGEN [22]用于将群论方法应用于图的构造，特别是表示有机化合物的结构，以及MOC [40]用于构造模特征表。

宣传。

对CGT系统的需求已经表明算法方法在群论研究（以及日益增长的教学）中的广泛使用。CGT在群论一般会议上的出现，如1981年、1985年、1989年以及现在的1993年所有四次Groups St Andrews会议，以及CGT专门会议日益频繁，都是进一步的迹象。虽然第一次完全致力于CGT的会议于1982年在达勒姆举行[2]，但后续会议有1988年和1992年的Oberwolfach，1991年[21]和1994年的DIMACS。除了一些综述（特别参见[15]以获取最近一篇带有许多参考文献的综述）外，最近还出版了两本关于该领域部分内容的专著。Greg Butler [10]试图向没有群论预备知识的计算机科学学生介绍置换群的计算方法，而Charles Sims [63]则权威地阐述了研究有限呈现群的方法，强调各种方法的共同特征。

Joachim Neubüser对Sims的Computation with finitely presented groups的评论位于THIS LINK。

2. 一些担忧。

总结前面各节所报告的内容，人们可能会得出非常乐观的结论。计算群论已经证明了它的威力，它的许多方法普遍且方便地可用，并被广泛使用。而对于未来：计算机变得更快，存储空间更大，两者都更便宜，方法更好，程序系统更全面且更易于使用。所以未来一片光明，充满希望！是这样吗？我有一些担忧。

1. 我提到1967年，即牛津会议那年，是CGT取得突破的时间。同一年，Huppert的书《Endliche Gruppen I》问世。它仍然在我的书架上，和27年前一样有用，而我们在牛津自豪地谈论的那些程序没有一个还在运行。当然，Huppert建立在群论一百多年的研究以及近百年撰写相关书籍的经验之上，而计算群论及其实施方法的艺术仍处于起步阶段。然而，我必须承认：虽然Huppert的书在27年后的2021年很可能仍会在你的书架上，但人们必须严重怀疑那时你是否还能使用GAP（或MAGMA）。计算机和计算机语言仍在迅速变化。例如，押注并行计算机作为未来的工具非常流行，但我完全不清楚众多并行计算机模型、操作系统及其语言中哪一种会成功。而且我们仍然缺乏可靠的方法来保存已经投入和正在投入大量工作开发的系统（如GAP或MAGMA）的工作，哪怕是在可预见的时期内。我们甚至没有定义好的标准来保存已经通过使用CGT创造的数学事实——特征表、群分类等——以一种能保证多年内可以使用和检查它们的方式。
2. 我有幸参与了Huppert著作的校对工作。几乎每一页都被极其仔细地阅读、重写并反复重读多次。然而，该书的最后一版仍有将近三页的勘误。我必须承认，对于GAP，我们没有足够的人力和时间进行任何同等强度的检查，我怀疑其他系统的情况也好不到哪里去。但更糟糕的是：在Huppert书的第128页，Schreier猜想被写成了“Schreibweise Vermutung”。这样的笔误出现在教科书中，读者至多一笑置之，但在程序中，它可能导致计算机做出某些不可预测的操作。
   
   需要明确一点：这并不是要复活那种认为不能信任计算机计算所得结果的旧偏见。现代计算机在按规则进行计算方面比人脑可靠几个数量级。当我们谈论bug时，我们谈论的是人在建立这些规则（即程序）时所犯的错误，其性质与证明中出现的错误完全相同。在诸如GAP这样的程序系统中，目前内核约有50 000行C代码，程序库中有120 000行GAP代码，手册约1000页，bug实际上是不可避免的。其中，导致系统崩溃或产生明显无意义结果的bug令人烦恼，真正危险的是那些产生错误输出、但乍看之下仍然可能甚至看似合理的bug。系统开发者对此能做些什么呢？
   
   程序一直是通过运行示例来测试的，选择一个足够有代表性的测试示例集是一个数学洞察力和想象力的问题，而选择足够大的示例集则是一个人力问题。我们将在第(iv)点中回到这个问题。
   
   使用允许甚至强制要求更透明地实现算法的现代编程语言，无疑在很大程度上帮助避免和发现bug——正如现代形式化和表述证明的标准在数学写作中所起的作用一样。然而，这并没有完全消除问题——同样的话也必须适用于证明的写作标准。
   最后就这个话题再说一点：为一本书提供勘误是件容易的事：我用我1967年那本Huppert的书，配上那3页勘误表；如果需要，我只需用铅笔在页边标出即可。那么从程序中消除错误呢？如果源代码是解释执行的，打补丁仍然相当容易。如果使用的是（编译后的）可执行文件，那么要么在源代码可用时修正源代码再重新编译，要么在源代码不可用时获取并安装新的可执行文件。每一种都是麻烦得多的过程，需要系统开发者方面多得多的协助。
3. 你可以在图书馆里读到Huppert书中的彼得·卢德维格·梅德尔·西罗定理及其证明，甚至无需购买该书，然后你可以终身免费使用彼得·卢德维格·梅德尔·西罗定理，但是——出于可以理解的获取维护资金的原因，我已经在(i)和(ii)中指出了这种维护的必要性——对于许多计算机代数系统，在其整个使用期间必须定期支付许可费。为了保护你所支付的东西，你得不到源代码，只能得到一个可执行文件，即一个黑箱。你可以按下按钮并得到答案，就像你从电视机上得到明亮的画面一样，但在这两种情况下你都无法控制它们是如何产生的。
   
   这种情况违反了数学中两条最基本的行事规则：在数学中，信息是免费传递的，一切都公开以供检验。不将这些规则应用于为数学研究而制作的计算机代数系统（CGT系统几乎完全如此），意味着朝着一个最不可取的方向发展。最重要的是：我们能期望有人相信一个他不被允许看到的程序的结果吗？此外：我们真的想向摩尔多瓦的同行收取一个计算机代数系统相当于他们几年薪水的费用吗？甚至：如果O'Nan和Scott必须为使用他们关于本原群思想的实现支付许可费，那么他们难道不也有权为在实现中使用他们的思想而收取许可费吗？
4. 前面的讨论描述了一个两难困境。一方面，CGT系统对于让算法思想对我们关于具体群的知识进展产生影响，其作用与书籍对于传播理论洞见的作用一样有用，事实上甚至更加不可或缺。另一方面，应当已经清楚的是，这类系统的开发和维护比写一本书带来更多问题，并且需要更多持续投入的人力。我希望我也已经给出了充分的理由，说明为什么我不认为许可费是一个理想的解决方案。大多数系统都通过研究资助获得了一些支持——就GAP而言，我们感激地承认德国研究联合会提供的此类支持——但通常这类支持是在有限时间内为原始开发提供的，而不是为维护持续提供的。
   
   对于这个问题我没有灵丹妙药，但让我在结尾先描述我们在GAP中尝试做的事情，然后描述在我看来，如果CGT要像自1967年牛津会议以来那样继续良好发展，在更广泛层面上需要什么。
5. 我们的政策是：(C-)内核和GAP函数库都以完整源代码形式，通过匿名ftp免费分发。我们每隔几个月提供补丁，大约每9至12个月发布系统的新版本。其他团队编写的一些C程序，针对特殊问题并为此调优到高效率，作为“共享库”链接到GAP，可以从GAP调用，但仍由其作者负责。
   
   我们维护一个电子“GAP论坛”，不仅用于讨论GAP在研究 and 教学中的使用，也（至少同样重要地）用于用户报告错误，从而使其立即为众人所知，我们鼓励用户加入该论坛。此外，在一些有经验的用户帮助下，我们尝试为发送到“GAP-trouble”地址的技术问题提供建议，例如安装问题。
   
   GAP的内核包含系统中时间关键的部分，例如存储管理、语言解释器和基本函数。显然，大多数GAP用户既不了解也不想了解内核中使用的方法，他们理所当然只想依赖它们。因此内核被保持得尽可能小，以便其开发和维护可以由极少数在系统构建方面经验丰富的人管理（目前首先是Martin Schönert）。另一方面，大得多的GAP库是用更透明的GAP语言编写的，这一事实允许用户在GAP的开发中发挥积极作用。他们可以并且应该——就像使用程序时一贯那样——运用他们所有的专业知识来批判性地检查结果是否“看起来正确”，如果有疑问，他们可以查看代码，尝试定位甚至纠正错误，但无论如何，他们可以并且应该通过GAP论坛将他们的疑问与整个用户社区以及系统开发者联系起来。事实上，这一方案在过去几年中运行得相当好，并大大帮助提高了GAP的可靠性。
   几乎不用说，GAP语言相对容易读写，这也让用户有更好的机会改编现有函数或为他们的特定问题编写新函数，事实上现在这也经常发生。然而，最理想的是，如果在更多情况下能花费一些额外的努力，将这样的“私人”程序准备为通用程序并向公众提供。再次，对于GAP，我们尝试为这样的程序公开提供一些组织上的帮助。当然，控制、改编或修改GAP中函数的能力至少以对群论算法的一些基本知识为前提，因此这些知识应该开始进入群论课程，完全不是为了取代，而是为了补充理论的某些部分。
6. 我已强调过，我们在“GAP政策”中赋予合作的核心作用。仍然有大量工作要由相当少的人来完成，他们开发和维护GAP。重要的是要认识到，这样的工作，如果要达到最先进水平，就必须与群论的进展以及目前正在研究的群论问题密切结合。CGT在范围上的进展，也在实现效率上的进展，更多地来自于对底层数学的更好理解，而不是更好的实现技术。（这些技术对代码的可靠性、灵活性和可移植性反而很重要。）也就是说，群论系统的开发是群论学家的工作（其中一些人还擅长系统编程），而不是专业系统程序员的工作。但随后也必须认识到，这些人的工作必须被承认为对数学的贡献。我仍然经常看到作者的论文，他们为这篇论文成功使用了GAP（或MAGMA或其他系统），并通过说：“……然后通过计算机计算我们得到了……”来提及这种使用。你会引用一篇有作者和标题的论文中的定理，说：“……然后通过浏览我们的图书馆，我们得知了以下事实……”吗？当然，如果我们要求改变这种习惯，在系统开发者方面，我们必须更加小心地将贡献归于个人（对于GAP，我们至少尝试这样做），并且我们还必须找到类似于已建立的发表论文方法来认证对系统的贡献。

总而言之，在我看来，有必要避免任何会将算法设计与实现的工作与其他数学工作分开的事情。相反，我们必须尽一切努力适应习惯，并采用数学其他部分中常见的行事规则。为此，计算群论需要与群论的所有其他部分最紧密地合作。这正是论文标题想要表达的：我想邀请你们进入计算群论，它不应被视为群论的天堂，那里闪亮的黑箱吐出特征表和上同调群，而应被视为一个需要大量照料的领域，但也值得你们帮助照料它。