Development, implementation and applications of fundamental algorithms, relying on Gröbner bases in free associative algebras

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

This project is part of mathematical Computer Algebra. It has applications in Ring Theory, Representation Theory, Computer Science and other disciplines. In order to perform Gröbner basis-like computations in a free associative algebra, one can use the recently developed letterplace correspondence between ideals and perform the computations in a large commutative polynomial ring. Such rings have been intensively studied before, in particular from a computer algebraic point of view. As a result, very effective data structures are known and fundamental algorithms have been optimized and implemented in computer algebra systems. The corresponding situation for non-commutative rings is less developed. The systematic use of the letterplace correspondence provides new insights and new levels of efficiency into the challenging realm of computations in free algebras and their factor rings. We aim at the creation of an extension LETTERPLACE of the well-known computer algebra system SINGULAR. This will for the first time provide efficient implementations of Gröbner bases and all the basic algorithms involving Gröbner bases in these algebras, for instance syzygy modules, elimination, kernels of ring and module homomorphisms. A preliminary implementation of the Letterplace Gröbner basis algorithm is available in the kernel of SINGULAR and it has already demonstrated very good performance. The next step will be to use these implementations to tackle hitherto unaccessible problems. For instance, we intend compute the K-dimension, explicit K-bases and (truncated) Hilbert series for non-commutative K-algebras. Another area of applications are computations in monoid and group rings where we plan to adress questions such as finiteness of a finitely presented group, the generalized word problem, the conjugator search problem, freeness tests for groups and the structure of the group of torsion elements of a group algebra. To guide these applications, we intend to collaborate with several research groups in Germany and across the world.