AF:Small: Computation in Very Large Groups

数学群论在科学和数学的其他分支中有着广泛的应用。当前感兴趣的一些重要例子是快速矩阵乘法、在存在对称性的情况下搜索以及在物理和化学中发现的对称性。目前的算法并不总是可伸缩的，或者在实现时并不总是实用的。超过这些水平，当前的算法往往变得不切实际，如一百万个点的排列、超过几十个矩阵群的维度以及超过1亿个陪集的陪集方法(在群上定义方程)。我们把这样的群体称为“非常大的群体”。这个项目将为非常大的群体开发一类新的算法。新的算法将利用P.I.和他的实验室在以前的计算中的经验，以及使用TB并行磁盘存储的算法。多磁盘方法的可行性之前已经在一个关于魔方的流行演示中得到了展示：魔方可以在26步或更短的时间内解出。这两个问题和更传统的问题将被用来进一步发展基于磁盘的语言Romy.重点将给予已知的不是多项式时间的问题(中心子，群交，正规化器等).在过去十年里，这些问题几乎没有取得什么进展。它们被认为是困难的，部分原因是它们与一个基团本身的共轭基团作用密切相关。在这个共轭作用观中，群被视为一个置换群，作用于几乎与群本身中的元素一样多的点上。在这种观点下，即使是中等大小的群体，在共轭作用下也会迅速变成非常大的群体。新的方法，如有偏见的蝌蚪，再加上宽敞的语言的力量，将使这一领域的进展得以恢复。更广泛的影响在于能够利用这些新的算法和实现来追求群论之外的应用，如前面提到的那些。长期以来，群论之外的研究人员一直有潜力产生超越标准软件能力的团队，例如免费和开源的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.