AF:Small: Computation in Very Large Groups

数学群论在科学和其他数学分支中有着广泛的应用。当前感兴趣的一些重要的例子是快速矩阵乘法、存在对称性的搜索，以及在物理和化学中发现的对称性。目前的算法并不总是可伸缩的，或者在实现上并不总是实用的。当前算法在超过100万个点的排列、超过几十个的矩阵群维度以及超过1亿个协集的协集方法（在群上定义方程）等级别上变得不切实际。我们称这样的群体为“超大群体”。这个项目将为非常大的群体开发一类新的算法。新的算法将利用P.I.和他的实验室在以前的计算和算法中使用tb级并行磁盘存储的经验。多盘方法的可行性先前在一个关于魔方的流行演示中得到了证明：魔方可以在26步或更少的时间内解决。这两个问题以及更多的传统问题都将用于进一步开发基于磁盘的语言Roomy。重点将放在已知不是在多项式时间内的已知问题上（中心化、群交、归一化等）。在过去十年中，这些问题几乎没有取得进展。它们被认为是困难的，部分原因是它们与群对自身的共轭群作用密切相关。在这个共轭作用的观点中，一个群被看作是一个作用于几乎和群本身的元素一样多的点的置换群。在这种观点下，即使是中等规模的群体在共轭作用下也会迅速变成非常大的群体。像偏向蝌蚪这样的新方法，加上Roomy语言的力量，将使这一领域的进展得以恢复。更广泛的影响在于利用这些新算法和实现来追求诸如前面提到的群论以外的应用程序的能力。长期以来，群论之外的研究人员一直有可能产生超出标准软件（如免费和开源的GAP包）能力的群体。扩大GAP和其他熟悉的工具的能力将使新的发现成为可能。Roomy平台的进一步发展也是一个重要的副产品，其价值将远远超出其群论起源。

Mathematical group theory has wide applications to the sciences and to other branches of mathematics. Some important examples of current interest are fast matrix multiplication, search in the presence of symmetry, and symmetries to be found in physics and chemistry. Current algorithms do not always scale or are not always practical in implementation. Some levels beyond which current algorithms tend to become impractical are permutations of a million points, matrix group dimensions beyond a few tens, and coset methods (defining equations on groups) beyond 100 million cosets. We call such groups "very large groups".This project will develop a new class of algorithms for very large groups. The new algorithms will take advantage of the experience of the P.I. and his lab in previous computations and algorithms using terabytes of parallel disk storage. The feasibility of a many-disk approach had previously been shown in a popular demonstration concerning Rubik's cube: Rubik's cube can be solved in 26 moves or less. Both that and more traditional problems will be used to further develop the disk-based language, Roomy.Emphasis will be given to well-known problems not known to be in polynomial time (centralizer, group intersection, normalizer, etc.). These problems have seen little progress during the last decade. They are considered hard in part due to their close connection with the conjugate group action of a group on itself. In this conjugate action view, a group is seen as a permutation group acting on almost as many points as there are elements in the group itself. In this view, even moderate size groups quickly turn into very large groups under the conjugate action. Novel methods such as the biased tadpole, coupled with the power of the Roomy language, will enable a resumption of progress in this area.The broader impact lies in the ability to harness these new algorithms and implementations in pursuit of applications outside of group theory such as those mentioned earlier. Researchers outside of group theory have long had the potential to generate groups beyond the capabilities of standard software, such as the free and open source GAP package. Extending the capabilities of GAP and other familiar tools will enable new discoveries. The further development of the Roomy platform is also an important byproduct, whose value will extend far beyond its group theory origins.