AF:Small: Computation in Very Large Groups

点击翻译按钮获取中文摘要

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.