Home Projects

Projects Second Period

Exploiting torus actions in algebraic geometry
Project Leader: Klaus Altmann (FU Berlin)
Torus actions translate the language of algebraic geometry into the language of combinatorics, making the development of algorithms possible that run faster than the usual ones. We want to extend this ansatz to the more general case of complexity-one torus actions. In order to do this it is not enough to use purely combinatorial software. Instead it is necessary to combine software from algebraic geometry and combinatorics. During the last two years the foundation has been built to connect the computer algebra system Singular with polymake, software for convex polyhedra. The goal is now to stabilize this connection and implement existing algorithms. A different ansatz, using the same connection, is the generalization of well- known Newton boundary methods of singularity theory through tropical methods. This allows examining the general case (instead of hypersurfaces).
Constructive derived equivalences and equivariant vector bundles
Project Leader: Mohamed Barakat (TU Kaiserslautern)
Computer algebra is facing new challenges as mathematicians are inventing new and more abstract tools to answer difficult problems and connect apparently remote fields of mathematics. With the invention of new high level programming languages these tools now start to find their way to computer algebra. The software project homalg emerged from the need to make the abstract notions of category theory and homological algebra accessible to the machine. They both provide extremely powerful organizing tools which translate to transparent algorithms able to organize many different computations and keep track of an enormous amount of data. The homalg project was designed to combine abstraction and efficiency, two traditionally conflicting goals. Written in GAP4 it is already interacting with almost all computer algebra systems of the priority program SPP1489, especially with SINGULAR and polymake. Abstract ABELian categories are already formalized in homalg. Driven by many concrete applications we will render derived categories and derived equivalences constructive. The ability of derived equivalences to relate two completely different ABELian categories is an invitation for computer algebra to change worlds; abandoning data structures with an unnecessary overhead in favor of more compact representations which speed up computations considerably. We aim at various tilting equivalences between derived categories of coherent sheaves on toric varieties and derived categories of modules over finite dimensional noncommutative algebras. Our goal is to setup a framework making such abstract equivalences computationally exploitable. The main application of the proposed project is the search for low-rank vector bundles equivariant under a finite group action.
Algorithmic aspects of branch groups
Project Leader: Laurent Bartholdi (Göttingen)
Branch groups form a basic class of infinite groups, and include such important examples as the "Grigorchuk group" of intermediate word-growth and the "Gupta-Sidki groups" - all examples of infinite torsion groups.
Although most algorithmic problems are unsolvable in the general class of groups, e.g. those given by a finite presentation (recognizing trivial, finite, or isomorphic subgroups, e.g.), many useful tools have been developed to deal with specific classes groups, and they perform well in practice. In particular, there are satisfactory algorithms that operate on hyperbolic groups and on matrix groups.
The proposal will extend the realm of algorithmic group theory in the direction of self-similar groups: in particular, solutions for these groups of the word problem, the conjugacy problem, the isomorphism problem, and the construction of recursive presentations ("L-presentations") will be addressed, with efficiency and actual implementation in mind.
Computational aspects of modular forms and p-adic Galois representations
Project Leaders: Gebhard Böckle (Heidelberg), Gabor Wiese (Luxembourg)
Recent breakthroughs in Arithmetic Geometry and various topical conjectures in the spirit of the Langlands programme establish and postulate deep correspondences between certain geometric objects: Modular and automorphic forms and certain number theoretic objects: Galois representations. The geometric side is often amenable to calculations and by the explicit nature of the correspondences also number theoretic objects become computationally accessible. The objectives of this project concern the investigation of these geometric and arithmetic objects either directly or through the correspondence. One main research line will lead to the computation of integral properties of p-adic modular Galois representations. Another research line will study the finiteness and describe the growth of sets of p-adic modular Galois representations modulo prime powers. Both lines are naturally related to level and weight optimisation modulo prime powers. They are also intimately linked to the p-adic coefficient fields of newforms about which numerous conjectures exist. These coefficients fields are strongly affected by the local coefficient field at p and a so called L- invariant. The latter will be explored by generating new data. Finally in weight two the integral local representation at good primes away from p will be studied by methods involving abelian varieties and their endomorphism rings. The methods to be employed are experimental, algorithmic, and theoretical and progress is expected from the interplay of these. For the experimental study, algorithms will be developed and implemented in computer algebra systems and a publicly available database will be computed. These new computer tools will be of service to other researchers as well.
Note: This project is also partly funded by the Fonds National de la Recherche Luxembourg.
L-functions and other arithmetic invariants of curves of genus greater than or equal to 3
Project Leaders: Stefan Wewers (Hannover), Irene Bouw (Ulm)
We propose to compute arithmetic invariants attached to smooth projective curves over number fields, like L-functions, the conductor and the local Tamagawa number. We focus on general curves of genus greater than or equal to 3. Our main tools are algorithms to compute the semistable reduction of the curve at primes of bad reduction.
Algorithms for rational cones and toric geometry
Project Leader: Winfried Bruns (Osnabrück)
The first goal of the project is the further development of the software package Normaliz that combines several algorithms for rational cones and affine monoids, in particular the computation of triangulations, Hilbert bases and h-vectors. The computation of Hilbert bases is of considerable interest in many areas of mathematics, for example, commutative algebra, algebraic geometry, number theory and combinatorial optimization. Meanwhile Normaliz has found applications in theoretical physics and algebraic topology. The further development applied for is supposed to improve the capacity of Normaliz and to open further applications for Normaliz. The second goal is the algorithmic search for counterexamples to open questions in projective toric geometry, notably the projective normality of smooth toric varieties and their definition in degree 2.
Improving and Combining Gröbner bases and SAT solving techniques for algebraic cryptanalysis
Project Leaders: Johannes Buchmann (TU Darmstadt), Gert-Martin Greuel (TU Kaiserslautern)
The project aims for development and improvement of high-performance computing techniques for exact solving of large-scale polynomial systems of equations arising from algebraic cryptanalysis. Since such equations naturally occur in applications areas like computational algebra, geometry, and number theory as well, we plan to intensify scientific exchange and joint software development within the priority program.
There are three main goals: Further development of Gröbner basis techniques and symbolic linear algebra methods for large systems; combining the latter with SAT solvers for effectively solving practically relevant Boolean equation systems; attacks to symmetric and asymmetric cryptographic schemes. Recent advances illustrate that we can go a major step ahead.
The following four work packages reflect these goals. The first work package improves exact methods for structured linear algebra over finite fields. Therefore, we will extend the previously established software library LELA which had been developed in the ongoing project. For well-scaling on realworld problems from cryptanalysis LELA will have to utilize matrix structures as well as parallelization.
The second work package proposes the development of high-performance symbolic techniques for cryptanalytic applications. Based those linear methods mentioned above and the ongoing preliminary work a toolbox with various, easy to use variants for computing large-scale Gröbner bases will be developed. This encourages scientific exchange and further research in the priority program and beyond.
A third work package focuses on new hybrid approaches for large Boolean systems. While Gröbner bases perform well on dense systems, the SAT approach is better suited for sparse Boolean systems and low memory demands. Therefore, it is necessary to provide a robust strategy for combining the strengths of both worlds. On the one hand Gröbner basis subroutines can be used within SAT solving, on the other hand both approaches can interact on the same problem instance.
Finally, these new methods will be used for cryptanalytic attacks on important symmetric and asymmetric cryptographic schemes. Systematic tests and analysis of the system of equations will help to identify an optimally performing representation of the equations. We are confident that this leads to new cryptographic attacks on these ciphers.
Combinatorial and geometric structures for reflection groups and groupoids
Project Leaders: Michael Cuntz (TU Kaiserslautern), Christian Stump (Hannover)
There are numerous combinatorial and geometric structures related to finite Weyl groups that are studied in various fields of mathematics. Particular examples are noncrossing partitions, Shi arrangements, cluster algebras, subword complexes, root posets, and q; t-Catalan numbers. These structures are deeply related and each of them reflects certain properties of the finite Weyl groups. There are several very natural generalizations of finite Weyl groups: A fine Weyl groups, Coxeter groups, complex reflection groups, Weyl groupoids, and simplicial arrangements. Each of these generalizations maintains some of the properties of the finite Weyl group and thus retains some of the combinatorics. For two reasons, there are many pieces missing to the big picture of reflection structures. On the one hand, some of the combinatorial structures have been introduced just recently. On the other hand, some of the generalizations are new or have experienced a renaissance in the last years. We propose to fill the gaps by implementing a package for reflection structures for Sage and GAP, and by then using it to collect experimental evidence for new conjectures and eventually to help us prove new theorems.
Arrangements of complex reflection groups: Geometry and combinatorics
Project Leaders: Gerhard Röhrle (Bochum), Michael Cuntz (TU Kaiserslautern)
The theory of hyperplane arrangements has close links with many parts of mathematics. The use of modern computer algebra allows for significant advances in resolving deep and longstanding conjectures concerning the combinatorial and geometric nature of hyperplane arrangements. In a recent joint paper with Hoge, using a computer based proof, we were able to confirm a conjecture by Orlik and Terao from 1992 on the question of freeness of restrictions of reflection arrangements of complex reflection groups. These restrictions are key to an understanding of the underlying arrangement. We intend to further investigate questions of combinatorial and geometric properties of reflection arrangements in this proposal.
We have three core research strands we aim to pursue. It was only very recently that Bessis established the K(π, 1)-property for all reflection arrangements which had been conjectured since the late 1980s. Orlik and Terao conjectured in the 1990s that this property also holds for all restrictions. For Coxeter arrangements, this had been known since 1972 due to seminal work of Deligne. Our first aim is to prove this conjecture which will lead to a better understanding of the topological nature of reflection arrangements.
Freeness is a fundamental notion due to Saito and plays a pivotal role in understanding general hyperplane arrangements. There is the stronger notion of inductive freeness and the weaker one of recursive freeness. While it is known that not every free arrangement is inductively free, it is still an open conjecture by Orlik and Terao from 1992 that every free arrangement is already recursively free. In recent joint work with Hoge, we determined the class of inductively free reflection arrangements. Secondly, we want to investigate these various notions of freeness for reflection arrangements and their associated restrictions. Specifically, we want to confirm this conjecture by Orlik and Terao for reflection arrangements.
In our third project, we look beyond reflection arrangements and consider more generally simplicial arrangements. With the aid of Cuntz's database of simplicial arrangements, our goal is to determine combinatorial invariants which will allow us to distinguish the free and inductively free from the remaining simplicial arrangements.
Carrying out these projects will enhance our understanding of complex reflection groups and their arrangements, as well as hyperplane arrangements in general.
Explicit Chabauty-Kim theory for the thrice punctured line
Project Leader: Ishai Dan-Cohen (Duisburg-Essen)
Let X denotes the thrice punctured line, and let S denote a finite set of prime numbers. Then the set of S-integral points of X has been known for a long time to be finite, but an algorithm for finding all points has yet to be developed. A new theory pioneered by Minhyong Kim may hold the key to developing algorithms for finding integral points in a wide range of situations. My collaborative work with Stefan Wewers has brought us closer to achieving this goal for our X. The project being proposed will be devoted to constructing such an algorithm. A priori, our algorithm will only provide an upper bound for the number of points, but Kim's conjecture implies that in fact this bound will be sharp. We will use our algorithms to compute many examples. In turn, our computations will help refine the conjecture and give evidence for or against its plausibility.
Geometric Aspects of Differential Equations
Project Leader: Michael Dettweiler (Bayreuth)
Differential equations are fundamental objects within mathematics and especially within algebraic geometry. Often, fundamental aspects of a geometric problem can be described in terms of a system of differential equations. Let us mention here the principle of monodromy (analytic continuation of solutions) and the notion of a variation of periods, describing the integration of differential forms (i.e. the Hodge theory) on a family of varieties. These concepts both play an important role in the field of Mirror Symmetry of Calabi-Yau varieties with many applications to physics and enumerative mathematics. It is the aim of this proposal to develop and implement two computer algebra packages which make the above mentioned concepts accessible for explicit computation.
The first package shall deal with computational aspects of the Hodge theory of families of varieties with a special attention to the important case of Calabi-Yau varieties and related convolutions of variations of Hodge structures.
The second shall deal with the computation of the monodromy of integrable differential equations (integrable connections) on quasiprojective varieties.
Thereafter, these packages shall be applied to various aspects, e.g., determination of new differential operators of Calabi-Yau type, computation of Instanton numbers or the computation of uniformizing differential equations.
Symmetries of singular del Pezzo surfaces in algebraic and arithmetic geometry
Project Leaders: Jürgen Hausen (Tübingen), Ulrich Derenthal (LMU Müchen)
A central task of algebraic geometry is the classification of algebraic varieties, i.e., solution sets of systems of polynomial equations. One of the oldest problems in number theory is the question of rational solutions of diophantine equations; in the language of algebraic geometry, this means studying the question of existence and distribution of rational points on algebraic varieties. This project takes up both questions for the class of (possibly singular) del Pezzo surfaces; these play a central role as basic objects in the classification theory of algebraic varieties. They are interesting from a number theoretic point of view since the distribution of rational points is precisely predicted by Manin's conjecture. We will examine symmetries of del Pezzo surfaces, develop methods to determine their automorphism groups, classify del Pezzo surfaces with rich symmetries and study their rational points.
Our approach to determine and describe automorphism groups is based on Cox rings. The choice of approach to Manin's conjecture depends on the symmetries: In case of in finite automorphism groups, the use of harmonic analysis is promising; otherwise an approach via universal torsos, which are described explicitly by Cox rings, in combination with analytic number theory is suitable.
Fundamental Algorithms in Singular
Project Leaders: Wolfram Decker (TU Kaiserslautern), Gerhard Pfister (TU Kaiserslautern), Mathias Schulze (TU Kaiserslautern)
Driven by mathematical demand, the advancement of computer algebra systems is a fundamental goal of SPP1489. Our proposal concerns the system SINGULAR which is, as we believe, a key player in SPP1489. Our goal is to create a computational framework for deep mathematical applications, based on a highly efficient and user friendly software platform. Both the benefits and challenges are manifold. On the mathematical side, while we wish to provide cutting-edge tools for application areas such as commutative algebra, algebraic geometry, arithmetic algebraic geometry, singularity theory, and many more, the implementation of advanced tools often depends on a chain of additional specialized tools and data structures to be developed at different levels. On the software development side, for cross-border approaches to solving mathematical problems, the efficient interaction of systems specializing in different areas is indispensable; handling complex examples or large classes of examples often requires a considerably enhanced performance. Whereas the interaction of systems is based on a systematic software modularization and the design of mutual interfaces, a new level of computational performance is reached via parallelization, which opens up the full power of multi-core computers, or clusters of computers. Connecting SINGULAR to other systems within SPP1489 is already a success story, with cross border mathematical tools and synergy effects arising at all levels. Links to systems for convex geometry, for example, provide the effective basis for a wealth of applications in the context of toric and tropical geometry, torus actions on semi-projective varieties, mirror symmetry, semi group rings, and Mori theory - achieved in what we consider a showcase example for collaboration within SPP1489. Another such example is the SINGULAR-GAP collaboration, which brings computational tools for algebraic geometry together with those from group theory, with GAP additionally benefiting from the computational power of SINGULAR with respect to polynomials, and SINGULAR from GAP's high level programming language. In the second round of SPP1489, we plan to include a general frame work for number theory developed in close collaboration with others. words for a substantial extension of the mathematic toolbox in our own area of expertise include extending the standard basis engine to the arithmetic case, absolute polynomial factorization, enhanced syzygy algorithms, parallel algorithms for primary decomposition, implementing differential forms, (parametric) DeRham cohomology, and numeric-symbolic methods for solving, with potential applications in computing regular and canonical models, studying 1- parameter families of affine, projective, and toric varieties via Gauss-Manin systems, and studying residues of differential forms. A particularly rich problem area is the algorithmic access to closure operations in commutative algebra.
Classification of nilpotent associative algebras and coclass theory
Project Leader: Bettina Eick (TU Braunschweig)
Associative algebras arise naturally in various areas of mathematics. For example, they play a role in representation theory and in cohomology; they arise as universal enveloping algebras in Lie theory, or as group algebras in group theory. Our central aim is to develop effective algorithms for the classification, construction and enumeration of finite dimensional nilpotent associative algebras. We first use the dimension as primary invariant and develop effective algorithms to construct or enumerate the isomorphism types of nilpotent associative algebras of a given dimension over a single finite field. We then extend our results to cover all finite fields and we consider the case of infinite fields. Coclass theory has been a highly successful tool in the classification of finite nilpotent groups. We translate the central ideas of coclass theory to finite dimensional nilpotent associative algebras and then develop algorithms to classify and investigate finite dimensional nilpotent associative algebras by coclass. The results of this research will yield significant new insights into the structure of nilpotent associative algebras.
Syzygies, Hurwitz spaces and Ulrich sheaves
Project Leader: Gavril Farkas (HU Berlin)
The Hurwitz space is the parameter space of degree k ramified coverings of the projective line by smooth curves of genus g. Via the Riemann existence theorem, every curve of genus g appears in this way, for a suitable choice of k. We propose to use syzygy methods to determine asymptotically the geometric nature (Kodaira dimension) of this space and study its singularities. Our methods should completely describe the resolution of a general k-gonal curve of genus g and lead to a full solution of a well-known conjecture of Green-Lazarsfeld concerning the minimal resolution of the coordinate ring associated to a non-special line bundle on a curve. Several generalizations of Green's conjecture are proposed and will be tested with the help of computer algebra.
Class group computation in large fields
Project Leader: Claus Fieker (TU Kaiserslautern)
The class group is one of the most important invariants of number fields; it underpins all problems regarding the multiplicative structure of number fields. While class groups have been at the centre of attention for a long time now, their behavior is still mysterious: for example in randomly chosen fields, class groups tend to be trivial, yet it is not known if there are infinitely many fields with trivial class group! On the other hand, in specific families class groups are known to be large. Class groups and their computation are also intimately linked to problems rearding the distribution of so called smooth numbers: algebraic integers that have no large prime divisors. This project has two core aims: mathematically, we want to study the distribution of smooth numbers in number fields in order to gain a better understanding of the performance of various class group related algorithms. In particular, the project will develop new methods to generate and analyses smooth numbers, to work with large very sparse matrices over the integers and study Brauer relations with the aim of verifying class groups. On the computer algebra side, this projects aims to provide the foundations of algebraic number theory, namely algorithms for class and unit group computations, smoothness tests and practical linear algebra in low dimensions to the SPP 1489. Those algorithms will form the foundation of an independent new computer algebra system that is tightly integrated with both Singular and Gap; hence will open the gate towards interdisciplinary applications. In this sense, the project aims to be a successor to the no longer active systems Kant/KaSH, LiDIA and Simath.
Algorithmic methods for arithmetic surfaces and regular, minimal models
Project Leaders: Anne Frühbis-Krüger (Hannover), Florian Heß (Oldenburg)
Regular and minimal models of algebraic curves over number fields are arithmetic surfaces that play an important role in arithmetic geometry. This research project aims at developing algorithms for such arithmetic surfaces and for the computation of regular and minimal models. The main topics are a desingularisation procedure following Lipman, functionality for the intersection pairing, exceptional divisors, blow ups and blow downs. On the basis of these algorithms applications to the Birch and Swinnerton-Dyer conjecture and other related areas are finally investigated.
Algorithmic tropical intersection theory on moduli spaces
Project Leaders: Andreas Gathmann (Kaiserslautern), Hannah Markwig (Saarbrücken)
Tropical geometry is a field of mathematics that uses combinatorial methods to study problems in algebraic geometry. Over the last years it has been particularly successful for the study of enumerative geometry, i.e. for questions about counting curves in a fixed variety satisfying some given conditions. The usual strategy to attack problems of this type is to interpret such numbers of curves as intersection products on appropriate moduli spaces parameterizing the curves in question, and then study the intersection theory of these spaces. In our proposal, which is a continuation of the project "Algorithmic methods in tropical geometry" from the first half of the SPP 1489, we plan to continue the development of our tools - in particular of the Polymake extension a-tint for algorithmic tropical intersection theory - and to apply them to problems in tropical enumerative geometry. We will study the tropical moduli spaces of covers of a curve together with the connection to their algebraic counterparts, the Hurwitz schemes. Due to the combinatorially involved nature of these objects, the extensive use of computational and experimental methods will be inevitable for this task. Moreover, for enumerative applications of our results we will continue to develop the tropical intersection theory of matroid fans both from a theoretical and an algorithmic point of view. Relating it to the algebraic intersection theory of toric varieties and their subvarieties, we thus plan to contribute new results and computational methods to the fruitful and deep connection between toric and tropical geometry.
Computing with Coxeter groups and Hecke algebras (CHEVIE/PyCox)
Project Leader: Meinolf Geck (Stuttgart)
We will be concerned with the theory of Coxeter groups (or, more generally, finite groups generated by reflections in a real or complex space) and related algebraic structures, especially Hecke algebras. These form the combinatorial skeleton of various more complex structures arising in Lie theory. The consideration of algorithmic aspects has a long tradition in this area. Our objectives are:
1. to contribute to the development of efficient algorithms for "high performance computations" with Coxeter groups and Hecke algebras;
2. to integrate these algorithms (and related data) in freely available and user-friendly computer algebra systems;
3. to perform specific experiments which help us clarify major open problems in the general theory.
By "high performance computations" we mean computations which go far beyond what is currently available or possible. A specific goal is to develop general programs which are, finally, capable of computing the left cells and the corresponding W-graph representations of the biggest of the finite Coxeter groups of exceptional type (E8). This would settle a line of research in which the first standards were set by Alvis in the 1980s, followed by DuCloux in the 1990s. These, and related programs to be developed, will allow us to perform systematic experiments with a new version of Lusztig's asymptotic algebra J (introduced by the applicant in 2009). The goal of these experiments will be to find patterns which help us clarify open questions about this algebra (e.g., the conjectured integrality of structure constants, or a description by generators and relations). It is hoped that this will lead to progress on Lusztig's conjectures on Hecke algebras with unequal parameters, in particular, the combinatorial version of these conjectures in type B_n due to Bonnafe, Iancu, Lam and the applicant.
Semistable resolutions of local models
Project Leader: Ulrich Görtz (Duisburg-Essen)
The goal of this project is the investigation of a topic in arithmetic algebraic geometry by algorithmic and experimental methods. Local models describe the étale-local structure of integral models of certain Shimura varieties, and therefore, as well as for other reasons, are of great interest in arithmetic geometry. However, in general their singularities are so complicated that it would be desirable to pass to a model with less severe singularities, in the best case to a semistable model. In general it is not known whether such a model exists. This is what we will investigate by explicit computations. In cases of "small rank" computations (by the principal investigator, among others) have shown that a semistable resolution exists. In the general case there are candidates for semistable resolutions, for example by Genestier and Faltings, but so far (without using computers) their semistability could not be proved. In addition, this and similar questions can also be investigated for other classes of schemes, for instance for certain degenerations of quiver Grassmannians.
Complex Multiplication: Class invariants and cryptographic applications
Project Leader: Florian Heß (Oldenburg)
With the emergence of computer algebra and the need for explicit calculations, the theory of complex multiplication has become subject to algorithmic investigations with a view towards applications in algorithmic algebraic number theory and cryptography. Among the applications are of particular interest primarily proving, explicit classified theory, and curve and pairing based cryptography. A central aspect of algorithmic CM theory is the interplay between numerical and symbolic computations describing discrete objects by analytic means. This project investigates the following three main topics: Class invariants for quadratic and quartic CM-fields, pairing based cryptography and aspects of algorithmic number theory.
Polyhedral Fan Structures in Toric and Tropical Geometry
Project Leader: Michael Joswig (TU Berlin)
A polyhedral fan is formed of polyhedral cones which meet face to face. Prominent examples include the normal fan of a polytope (which encodes everything there is to say about that polytope from a linear optimization point of view), the secondary fan of a point configuration (which stratifies the regular subdivisions of the convex hull, using the given points), and the Gröbner fan of an ideal in a polynomial ring (which describes all possible Gröbner bases for that idea. The key objects in tropical and toric geometry belong here as well. Projective toric varieties can be described in terms of the normal fans (or dually, the face fans) of lattice polytopes. Tropical varieties occur as subfans of Gröbner fans. This shows that polyhedral fans are fundamental in several areas in mathematics and their applications. In this project we want to study a variety of combinatorial problems in toric and tropical geometry by focusing on a number of different polyhedral fan structures. Putting the fans first will allow to share the methods, in particular, algorithms and software. Specifically, we want to study the secondary fans of smooth Fano polytopes, the Dressians of matroids, combinatorial aspects of polyhedral divisors on toric varieties as well as Minkowski cones and fans. There is a number of connections between these topics.
Units in integral group rings
Project Leader: Wolfgang Kimmerle (Stuttgart)
Study of the structure of the unit group of integral group rings with the aid of computer algebra, development of new algorithms as well as extensions of existing ones. Application to open research problems, in particular the Zassenhaus Conjecture for torsion units and the constructive description of the unit group.
Standard basis methods for path algebra quotients
Project Leader: Simon King (Jena)
The projected implementation of the non-commutative F5 algorithm, e.g., in the Letterplace algebra, is of general interest. An extension of the theory to infinite dimensional path algebra quotients would conceivably be applicable to the computation of Loewy layers. In homological algebra, an efficient non- commutative F5 implementation can be used to extend existing packages for the computation of modular group cohomology. Cohomology computations shall thus become possible in previously untractable examples, as well as testing conjectures on modular cohomology. I plan to study Ian Hambleton's conjecture that the modular cohomology of finite groups is detected on metabelian p-groups. In connection with isomorphism tests for graded algebras, I intend to investigate Bettina Eick's conjecture on cohomology and coclass of p-groups.I will also compute Ext-algebras of groups and basic algebras. Non-commutative standard bases not only play a role in the computation of resolutions, but also in the computation of the ring structure. Such computations require a large background of software packages, ranging from linear algebra over GAP and Singular to new software. The new software shall be published as part of the Sage standard library. Data bases shall be created for Sage and Gap. In addition, I'll try to extend known degree bounds of cohomology rings to Ext-algebras.
Computational Galois Theory for Local Fields
Project Leader: Jürgen Klüners (Paderborn)
Galois groups are fundamental mathematical objects, which provide information about the solvability of polynomials by radicals. The applicant has gained respectable progress in computing intermediate fields and Galois groups over rational numbers in the past few years. While the recent implementations provides computations of Galois groups for polynomials up to high double-digit degree, these computations are difficult to perform efficiently, and it is unknown if these algorithms can have polynomial time complexity. For the computation of intermediate fields, the applicant developed a new algorithm, which de-livers a system of generating subfields in polynomial complexity. Then any arbitrary subfield can be described as a suitable intersection of the generating subfields. Furthermore, the running time for computing all subfields is proportional to the number of subfields. For this project at hand, we aim to develop and implement nontrivial algorithms for the computation of subfields and Galois groups over local fields, i.e. over p-adic fields and local function fields. It is fair to hope that these algorithms provide improvements and better understanding for the respective algorithms over global fields. This project requires a very detailed investigation of the local fields' structure, and a fine intuition for retrieving effectiveness for computation over local fields. This yields a nice interaction of theory and computer algebra applications. The computation of intermediate fields leads back to factorisation of polynomials and solutions of linear systems of equations. Hereby, recent implementations of factorisation algorithms over local fields only provide approximations, and as these are the input of the linear system of equations, we have to consider precision problems like in numerical analysis. The main problem for the computation of Galois groups over local fields is that we do not have easy access to the zeros and their approximations, which does not allow the transformation of known algorithms for global fields. We would like to attack the computation of Galois group via the knowledge of the absolute Galois group and local class field theory. The applicant administrates a database for number fields filled with over 2 million polynomials. This database shall be extended and be expanded by local function fields with small characteristic. These data are very important to find and understand interesting examples for conjectures within geometry and number theory. Furthermore, big tables are useful to make and test conjectures about the asymptotics of such objects.
Experiments with cellular structures
Project Leader: Steffen König (Stuttgart)
Brauer algebras are the protoypes of diagram algebras; these are combinatorially defined algebras, which are used for instance in invariant theory and representation theory of classical groups, combinatorics, knot theory and statistical mechanics. This project aims at providing computable tools and experimental data to clarify the ring structure of these algebras and of some of their representations. The main ingredients are cellular (or quasi- hereditary) bases and permutation modules. There are five closely related sub-projects:
1. Schur algebras of Brauer algebras are endomorphism rings of permutation modules; they provide- through their combinatorial bases - a computable approach to invariant theory and hopefully also to representation theory of orthogonal and simplistic (algebraic) groups.
2. The q-Brauer algebras are a new quantization of Brauer algebras, in some respects better than the frequently used Birman-Murakami-Wenzl algebras. They have to be made accessible for computations, in particular by providing and using a cellular basis.
3. The permutation modules of Brauer algebras - whose endomorphism rings are the Schur algebras of the first sub-project - have favorable abstract properties (as long as the characteristic is different from two and three). An explicit and practical construction that works for related algebras too has to be found and to be carried out.
4. Brauer algebras, and related algebras, are closely connected to group algebras of symmetric groups, by (non-unital) maps and functors whose nature still has to be clarified. The appropriate context appears to be that of universal localizations, which have to be made accessible and computable.
5. The framework of cellular algebras, made for finite-dimensional algebras, has now been extended to infinite-dimensional algebras. It is going to be applied to affine Hecke algebras and to Khovanov-Lauda-Rouquier algebras. For affine Hecke algebras the connection to number theory and in particular the intersection with the local Langland's programme needs to be clarified by comparing parameters of simple representations.
Computational aspects of block theory of finite groups
Project Leader: Jürgen Müller (Jena)
Representation theory of finite groups provides unified mathematical models for symmetry phenomena, by investigating linear group actions on finite- dimensional vector spaces. While the theory is fairly well-understood over fields of characteristic 0, this by far does no longer hold in the modular case, that is, over fields of prime characteristic p. Here, understanding the representation theory of a finite group G over a field k is equivalent to understanding the representation theory of its blocks, that is, the indecomposable direct factors of the group algebra kG. In particular, one of the key questions is to what extent the 'global' representation theory of a block of G is already controlled by 'local' data, that is, representations of non-trivial p-subgroups of G and their normalizers. Block theory of finite groups has been extremely active and rich in fascinating developments in recent years, but still is full of questions and open conjectures. The aim of this project is to contribute to this area, by developing computational techniques to handle the algebraic objects featuring prominently in modern block theory of finite groups, implementing them as efficient, widely applicable tools, and applying them to substantial interesting examples.
Arithmetic methods for finitely generated matrix groups
Project Leader: Gabi Nebe (RWTH Aachen)
The membership problem is in general undecidable for finitely generated matrix groups over infinite fields. Nevertheless, certain, naturally arising matrix groups can be handled algorithmically. Examples are given by normalizers of finite matrix group, automorphism groups of hyperbolic lattices and groups generated by a certain family of maximal finite matrix groups. The latter naturally act on Bruhat-Tits buildings of p-adic classical groups which can be used to obtain a structural description of the group as well as algorithmic methods, e.g. a membership test. To analyse subgroups of PSL2 one may apply the natural action on hyperbolic spaces. We want to develop general purpose algorithms for a geometric reduction a la Aschbacher also for infinite fields. Arithmetic methods (invariant lattices, enveloping orders) will lead to the construction of invariants of finitely generated matrix groups, like finite factor groups and p-adic completions.
Syzygies, experiments in algebraic geometry and unirationality questions for moduli spaces
Project Leader: Frank-Olaf Schreyer (Saarbrücken)
Computer Algebra allows searching and constructing points in moduli spaces, whose further properties can help to establish properties of these moduli spaces or of maps between them. Key to a construction and to properties is often a detailed understanding how the defining equations behave, for example, which syzygies they have. In this project we plan to develop our experimental techniques to attack such questions further.
Algorithmic methods in the modular representation theory of diagram algebras
Project Leader: Armin Shalile (Stuttgart)
The main goal of this project is to develop algorithmic and computational methods in the study of Brauer algebras. More precisely, the object of study are blocks and decomposition numbers over fields of finite characteristic which are closely related to the corresponding problems for symmetric, orthogonal and symplectic groups. The outcome will be a freely available GAP package which contains an efficient algorithm to compute blocks and decomposition numbers for a wide class of special cases. Furthermore, it will contain many other features such as multiplication of diagrams, computation of matrix representations of cell modules, bases of the center, etc. The approach is inspired by the theory of so called Jucys-Murphy elements for symmetric groups. These are a central tool in the study of symmetric groups and play, for example, a major role in recent results on categorification and grading's. The PI has shown in previous work that analogues of these elements also determine decomposition numbers of Brauer algebras in the case when the characteristic of the field is either 0 or large compared to the degree of the Brauer algebra. The aim is to refine this result to fields of smaller characteristic, extend it to other related algebras such as the BMW- or partition algebra and determine the blocks of the Brauer algebra by using similar methods. This will also allow us to better understand the role of Jucys-Murphy elements in potential grading and categorification results for the Brauer algebra.
Computational methods for abelian varieties over number fields with complex multiplication
Project Leaders: Andreas Stein (Oldenburg), Annegret Weng (HS f. Technik, Stuttgart)
Computational arithmetic geometry and its related areas generalize considerably both importance and techniques of classical computational number theory. The introduction of algebraic curves to cryptography emphasized that arithmetic geometry possesses not only an extremely interesting theoretical value that is rapidly growing; it also provides us with an exciting computational side. Many questions are still unsolved and need more investigation. This project is concerned with explicit algorithmic problems in the arithmetic of abelian varieties over number fields with complex multiplication. There are a multitude of recent numerical results for dimension one abelian varieties with complex multiplication, also motivated from applications to cryptography. We wish to solve various problems for low dimensional abelian varieties with complex multiplication, both algorithmically and theoretically. This includes the following topics: Torsion points of abelian varieties with CM over finite fields, small invariants and explicit class field theory, construction of curves for pairing-based cryptography, investigation of the Igusa-invariants, efficient algorithms and explicit implementation of new methods.
The Generalized Fermat Equation with exponents 2, 3, n
Project Leader: Michael Stoll (Bayreuth)
The Generalized Fermat Equation asks whether the rth power of an integer can be equal to the sum of a pth power and a qth power. There are good reasons to require the three integers to be without common prime divisor. The solution of the original Fermat Equation (where all three exponents are equal), is given by the statement of 'Fermat's Last Theorem', whose proof took over 300 years and has driven the development of several areas within mathematics whose results have many applications within mathematics, even though the original question does not seem to have interesting applications. The Generalized Fermat Equation (whose complete solution is still open) has served in a similar way as a motivation for the extension of existent and the development of new solution methods. This is what also this project tries to achieve: with the goal of a complete solution of the Generalized Fermat Equation with exponents 2, 3, n as concrete motivation, we plan to develop and extend methods that then will also have applications to many other problems. This is related quite generally to the solution of polynomial equations in two variables in integers or rational numbers. It is an important open question, wether this is algorithmically possible in general. The project is meant to bring us closer to a (hopefully positive) answer.
Monodromy Algorithms in Singular
Project Leader: Duco van Straten (Mainz)
The aim of the proposal is to develop and implement algorithms to compute and analyse the monodromy representation arising in the cohomology of a family of varieties depending on a parameter. Rather than striving at complete generality, we propose to start families of hyper surfaces with small cohomology and use special features like the appearance of special singularities in a fibre. The proposed algorithms combine Grübner-basis calculations in polynomial rings and localisations, algorithms for primary decomposition,Grübner-basis calculations in Weyl-algebras, normal form algorithms, numerical techniques and algorithms from algorithmic group theory.
Effective methods for spectrahedra in real and convex algebraic geometry
Project Leader: Thorsten Theobald (Frankfurt a.M.)
Spectrahedra are the feasible sets of semidefinite programming and are meanwhile widely recognized as a very versatile geometric structure which forms a central link between (real) algebraic geometry and convex optimization. While recent years have provided tremendous progress in the use of semidefinite programming and spectrahedra in approaching real-algebraic problems of various types, effective handling of spectrahedra is still a rather challenging issue. Building upon the state of the art, the goal of the current project is to advance the understanding and handling of spectrahedra. In parti-cular, we shall explore effective methods for tackling computational problems of amoebas (the logarithmic images of al-gebraic varieties), spectrahedral approaches and relaxations in real algebraic geometry and optimization of polynomials, spectrahedra and complete positivity, as well as stability issues in handling spectrahedra.
Toroidal methods for computing zeta functions of groups and rings
Project Leader: Christopher Voll (Bielefeld)
Originally introduced in the 1980s in the area of subgroup growth, the study of zeta functions of groups and rings has since evolved into a deep theory that combines methods from algebra, combinatorics, algebraic geometry, and other areas of mathematics. The explicit computation of such zeta functions, however, remains extremely challenging. The main objective of this project is to develop toroidal methods for computing and analyzing zeta functions of groups and rings. More precisely, the zeta functions that we consider admit Euler product factorisations into local zeta functions indexed by primes and we seek to compute these local factors. Our first main goal is to develop and implement an algorithm for computing such local zeta functions under non-degeneracy assumptions with respect to certain associated Newton polyhedra. Our algorithm will combine algebro-geometric computations and methods from convex geometry. Our second main goal is to develop methods for studying analytic properties of local zeta functions of groups and rings, again under non-degeneracy assumptions. In particular, we will develop methods for studying the local pole spectra of such zeta functions. The third main goal of our project is to apply our methods to study zeta functions of interesting and challenging classes of groups and rings. These computations will both stimulate further developments of our algorithms and they will provide a testing ground for conjectures in the area. All software and databases developed as part of this project will be made freely available.
Coordinator Project
Project Leader: Wolfram Decker (TU Kaiserslautern)
The goal of the DFG Priority Programme SPP1489 is to further the algorithmic and experimental methods in different areas of mathematics, to combine the methods where needed, and to apply the resulting algorithms to central questions of theoretical and practical interest. This requires the close cooperation of the different groups, the consistent training of young researchers, and the effective transfer of knowledge. The coordinator project fosters the individual efforts of the members of the programme and brings these efforts together. It is, thus, of importance for the priority programme as a whole. In detail, the project includes the administration of the programme, the dissemination of results, the set-up and maintenance of a webserver, the mobility of participants, the invitation of guest researchers, and the arrangement of a balanced system of schools, workshops, and conferences. A unique feature of SPP1489 is the advancement of computer algebra systems, with particular emphasis on the interaction of both whole systems and smaller packages specializing in different areas. For this, a certain amount of central software development and expert help is indispensable. The project proposes to coordinate the efforts of interconnecting the different systems and packages, to extend and optimize the common platform for developing and distributing mathematical software which has been created during the first term of SPP1489, to provide guidance and support to developers and users, and to centrally address challenges in software design such as parallelization, which require expertise from computer science, but are crucial for large-scale mathematical applications.