Algorithms for Arithmetic Groups

Colorado State University, Fort Collins CO

Investigators

Abstract

The objects, called arithmetic groups, considered in this project are sets of matrices (representing symmetries of a space) whose entries can be considered as integral coordinates in a geometrical object. They lie at the intersection of Algebra, Geometry and Number Theory. If a number of such matrices are given, we consider the subset that can be formed by combining these matrices that is applying the symmetries in turn. It is called the subgroup (generated by the matrices). A natural question now arises on whether finitely many translated copies of such a given subgroup amount to the whole set, in this case the subgroup is called arithmetic. This question has come up in many concrete examples brought up by researchers in number theory or geometry but so far the only solution approach have been ad-hoc methods for small cases. The PI will design new algorithms for answering this question on a computer and provide an open-source implementation of this algorithm. The project will also train a graduate student in the development of mathematical software. The PI will develop new algorithms for calculations with classes of arithmetic groups, in particular developing methods that may determine whether a subgroup given by generating matrices is itself arithmetic. Practical implementations of these algorithms will be made available as a package for the computer algebra system GAP. By utilizing state-of-the art techniques for finite matrix groups, developed only in the last years, this project will make significant progress on algorithmic questions for infinite integral matrix groups, extending current methods that have been mostly restricted to the case of finite groups. The approach envisioned will intermesh calculations with finitely presented groups and with matrix groups in a novel way. Several subtasks require the development of new algorithms for finite groups, as well as for coset enumeration, and thus contribute to the algorithmic theory of finite and finitely presented groups. The software developed as part of the project will be of use to investigators in the many areas encountering arithmetic groups -- geometry, number theory, theoretical physics, and others. The project will contribute to the development of the open-source computer algebra system GAP (and thus also to the system SAGE) that is used by a multitude of researchers world-wide, has been cited in over 2000 refereed publications, and also has seen use as a tool in undergraduate abstract algebra classes. Integrating research and education this project will contribute to the training of a graduate student in developing mathematical software and utilizing standard open-source software development tools. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.