In many situations of algebraic geometry there exist actions of algebraic tori on objects, morphisms, or families. Algebraically, this is reflected by an (initially maybe invisible) multigrading of rank being the dimension of the torus. In the extension of this rank, this allows one to translate complicated and expensive (in terms of computing effort) algebraic geometry into algorithmically easier combinatorics and discrete/convex geometry. For many years this has been done for full torus actions ("toric varieties"). More recently, this method has also been developed and used for tori of smaller dimension. <br/> To make possible a usage of these theories in praxis, one needs the creation and implementation (in Singular) of algorithmic tools to allow free movement in a combination of algebraic and convex geometry. However, any implementation requires preparation, i.e. a further development of the computer algebra systems in question. Splendid packages exist for both convex and algebraic geometry. But none of these allow one to work with objects of both areas simultaneously.
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).
Exploiting torus actions in algebraic geometry
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. <br/> 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.
Constructive derived equivalences and equivariant vector bundles
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. <br/> 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.
Algorithmic aspects of branch groups
This project is a complement to the algorithmic part of BL 395/3-1 where the Equivariant Tamagawa Number Conjecture (ETNC) of Burns and Flach is studied in the case of Tate motives. In this new project we want to consider ETNC for the base change of an abelian variety A which is defined over Q. Here ETNC is an equivariant refinement of the famous Birch and Swinnerton-Dyer conjecture. More explicitly, ETNC describes the leading terms of twisted Hasse-Weil-L-functions in terms of cohomological data associated to the motive which is attached to A. The aim of the project is to derive explicit formulations of these equivariant conjectures which makes them amenable to numerical verifications and to develop and implement algorithms in order to provide numerical evidence.
The Equivariant Tamagawa Number Conjecture for the base change of an abelian variety
The theory of automorphic forms is one of the core topics of algebraic number theory. It has a long history and is at the same time, with such spectacular successes as the proof of Fermat's last theorem, the Sato-Tate conjecture or the Serre conjecture, one of the most flourishing topics. Presently many new directions are explored. Basic computer algorithms axe an invaluable tool to yield experimental data which further advance the theory. <br/> The present proposal provides one approach to obtain and implement such algorithms. It also explains a number of interesting experiments which we hope to perform. The approach applies to number as well as function fields. Its relation to classical automorphic forms is explained by the Langlands program - and in often conjectural. The intention is to compute Galois representations associated to automorphic via their Hecke eigensystems. <br/> The key tool is the algorithmic computation of quotients of Bruhat-Tits buildings by cocompact arithmetic subgroups. The result is a finite simplicial set and thus a finite combinatorial object. Automorphic forms are sections of local systems on these finite quotients. Their systems of Hecke eigenvalues can be computed combinatorially.
Algorithms for quotients of Bruhat-Tits buildings and automorphic forms
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.
L-functions and other arithmetic invariants of curves of genus greater than or equal to 3
The main theme of the proposed project is to use techniques related to semistable reduction of curves to study resolution of singularities, in particular wild quotient singularities in dimension two. A central case arises from the study of smooth projective curves over a p-adic field. Here we search to relate a suitable semistable model of the curve to a regular model via a quotient construction. This construction gives rise to quotient singularities, and we propose new methods for resolving them. More generally, the goal is to extend this construction also to surfaces in equal characteristic p, and to higher dimension. <br/> We plan to use the results of this study to develop practical algorithms to compute semistable models of curves. We also expect to obtain a better insight into the structure of the quotient singularities arising in our work, and thus be able to algorithmically compute their resolution, in cases that were so far inaccessible to brute force calculation.
Semistable reduction and wild quotient singularities
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.
Algorithms for rational cones and toric geometry
In the era of ubiquitous use of the Internet the questions of privacy and confidentiality play a very important role. Therefore, evaluating cryptographic primitives that provide the above properties has always been crucial for applications like online banking, eCommerce, e-mail communications etc. Block ciphers are well-established building blocks for constructing cryptographic protocols. In this project we address the cryptanalysis of block ciphers. In recent years algebraic cryptanalysis of block ciphers became a rapidly developing area of research. <br/> On the other side, some limitations of the method became apparent over the time. Our goal is, therefore, to pursue a quite recent trend of combining new algebraic and conventional statistical attacks. We will pay a special attention to ciphers that employ modular arithmetic to provide non-linearity: algebraic aspects of such an analysis are novel. Within this project we will develop cryptanalytic methods of combined attacks as well as tools from computer algebra that are absolutely necessary to provide efficient attacks. Fast contradiction finding and system solving in the specific context of algebraic-statistic cryptanalysis is a challenge we address in this project. We believe that united competence and experience of the two applying groups will give a good chance to successfully fulfill the goals of the project.
Algebraic-statistic attacks: Algorithms and tools
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. <br/> 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. <br/> 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. <br/> 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. <br/> 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.
Improving and Combining Gröbner bases and SAT solving techniques for algebraic cryptanalysis
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. <br/> 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. <br/> 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. <br/> 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.
Arrangements of complex reflection groups: Geometry and combinatorics
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.
Combinatorial and geometric structures for reflection groups and groupoids
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.
Explicit Chabauty-Kim theory for the thrice punctured line
The goal of the DFG Priority Programme SPP 1489 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 aims at fostering and bringing together the individual efforts of the members of the programme and will, thus, be of importance for the priority programme as a whole. In detail, we propose <li> to create and maintain an open source platform which allows software from different areas to interact, which creates an infrastructure for enhancing each individual system, and which is custom-made for the research projects of the programme, <li> to arrange a programme-wide system of schools, workshops and conferences which is modeled on the successful activities of European networks in algebraic geometry, and which targets the needs of researchers at different stages of their career, <li> to set up and maintain a webserver whose main goals are to facilitate the management of the programme and to disseminate results, software, and data bases created by the programme.
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.
Coordinator Project
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.
The overall goal of the DFG priority programme SPP1489 is to push forward and combine computer algebra methods from different areas of mathematics, and to apply the resulting algorithms to central problems of theoretical and practical interest. To achieve this goal, the programme aims at creating a free and open source platform for linking computer algebra systems specializing in the areas covered by the programme. First and foremost, however, the individual systems have to be extended in view of the needs of the participating researchers. Our proposal aims at doing this for the system SINGULAR which, as we believe, will be a key player in this context. Our goal is to improve the performance of the most fundamental algorithms for polynomial computations, but also to redesign some of the algorithms for applications in areas such as arithmetic geometry and non-commutative algebra. At the same time, we have a number of advanced computational tools in mind. These include the combination of computational methods in algebraic and convex geometry, with potential applications in toric and tropical geometry, and the computation of cohomology, with potential applications to Deligne–Lusztig varieties and monodromy. Another goal is to link symbolic and numerical algorithms, with particular emphasis on new algorithms for primary decomposition.
Fundamental Algorithms in Singular
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.
Symmetries of singular del Pezzo surfaces in algebraic and arithmetic geometry
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. <br/> The second shall deal with the computation of the monodromy of integrable differential equations (integrable connections) on quasiprojective varieties. <br/> 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.
Geometric Aspects of Differential Equations
Constructions and classifications of group extensions play a central role in many applications of group theory. Computational group theory provides effective methods to construct up to strong isomorphism extensions with an elementary abelian module. This restriction on the module limits the possible applications significantly. <br/> Our aim is to use cohomology theory in the development of a new effective method to construct up to strong isomorphism extensions with an arbitrary finite group as module. Then we will investigate variations of this method. For example, we want to develop an effective method to construct up to isomorphism all extensions in which the module embeds as the Fitting subgroup or as a term of the derived or lower central series. Further, we plan to apply our new algorithms in group and number theory. First, we want to extend the Small Groups Library to all groups of the orders at most 10.000 with few exceptions on the orders. Then, we want to investigate the construction up to isomorphism of the finite metabelian groups with a given derived subgroup and derived quotient. These groups play a role in number theory, as they are related to the Galois groups of unramified extensions of number fields.
Applications of cohomology in group theory and number theory
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.
Classification of nilpotent associative algebras and coclass theory
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.
Syzygies, Hurwitz spaces and Ulrich sheaves
The moduli space of curves M_g is the universal parameter space for algebraic curves (Riemann surfaces) of given genus, in the sense that its points correspond to isomorphism classes of curves of genus g. The study of the geometry and topology of M_g is a central problem in algebraic geometry. A well-known principle, due to Mumford, asserts that all moduli spaces parameterizing curves of genus g >= 2 (with or without marked points or level structures), are varieties of general type, with a finite number of exceptions that occur in relatively small genus, when these varieties tend to be uniruled, or even unirational. A variety X is said to be uniruled, when through a general point x in X there passes a rational curve f : P^1 -> X, whereas X is said to be of general type, when the canonical bundle K_X has the maximum number of sections. From the point of view of classification theory, uniruledness is the opposite of being of general type. <br/> The aim of this project is to compute the Kodaira dimension of various covers of M_g. These include universal Picard varieties and moduli spaces classifying pairs consisting of a curve together with a point of order / in the Jacobian variety respectively. The proofs are expected to rely on syzygy calculations assisted by the Macaulay system.
The study of the birational geometry of various moduli spaces of curves with the help of the computer algebra system Macaulay
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.
Class group computation in large fields
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 methods for arithmetic surfaces and regular, minimal models
The new research field of tropical geometry has recently led to considerable progress in algebraic geometry and particularly enumerative geometry. With the help of tropical geometry, many algebraic or geometric questions can be reduced to combinatorial problems concerning graphs or polyhedral complexes. However, the structure of these combinatorial problems is involved, which makes the theoretical as well as practical use of these results complicated. Therefore, we would like to develop resp. implement algorithms for several of these problems which are of particular interest. Thus, we do not only want to gain new results in tropical and hence algebraic geometry, but we also want to simplify the application of tropical geometry.
Algorithmic Methods in Tropical Geometry
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.
Algorithmic tropical intersection theory on moduli spaces
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: <br/> 1. to contribute to the development of efficient algorithms for "high performance computations" with Coxeter groups and Hecke algebras; <br/> 2. to integrate these algorithms (and related data) in freely available and user-friendly computer algebra systems; <br/> 3. to perform specific experiments which help us clarify major open problems in the general theory. <br/> 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.
Computing with Coxeter groups and Hecke algebras (CHEVIE/PyCox)
Representation theory, in other words the study of symmetries, is an important area of mathematics. For a certain class of "representations" Pierre Deligne and George Lusztig exhibited a close connection between the algebraic notion of representation, and certain geometric objects, now called Deligne-Lusztig varieties. Since then, Deligne-Lusztig varieties have been thoroughly investigated from a representation theoretic point of view. Much less is known about their geometric properties, though. The goal of the proposed project is to improve our understanding of the geometry of Deligne-Lusztig varieties using explicit and algorithmic methods in order to study concrete examples, and hopefully eventually to reach new general results. <br/> Deligne-Lusztig varieties are smooth quasi-projective varieties over finite fields. An important specific question is whether there exist Deligne-Lusztig varieties which are not affine varieties.
Geometry of Deligne-Lusztig varieties
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.
Semistable resolutions of local models
Experience shows that advances in the field of computational homological algebra lead to new theoretical insights, and that theoretical advances in turn result in better computational methods. By combining the work of several authors – including the applicant's previous DFG project on the cohomology of p-groups – we will develop methods and software to compute cohomology rings and Ext-algebras for a variety of groups and basic algebras, using noncommutative Gr¨obner bases to construct minimal resolutions. <br/> This will allow us to compute a series of interesting test cases: both in group cohomology and for conjectures about finite dimensional algebras such as the Strong No Loops conjecture. The software will make use of the systems Gap and Singular, and will be made available as a Sage package. <br/> In addition to the design and implementation of suitable algorithms and the evaluation of the computational results obtained, we will also seek to generalise known degree bounds for cohomology rings to the case of Ext-algebras.
Computational Cohomology for basic algebras
Mori dream spaces are varieties with a finitely generated Cox ring. Examples are the toric varieties and the Fano varieties. Based on the fact that Mori dream spaces are quotients of affne varieties, one obtains a concrete description of them by means of algebraic-combinatorial data. This generalizes the description of toric varieties in terms of lattice fans and makes Mori dream spaces accessible for computations. We intend to study the geometry of Mori dream spaces in terms of their describing data and to develop and implement algorithms for concrete computations.
Mori dream spaces: Theory, algorithms and implementation
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.
Complex Multiplication: Class invariants and cryptographic applications
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.
Polyhedral Fan Structures in Toric and Tropical Geometry
Lattice polytopes are objects at a junction between combinatorics and algebraic geometry. The study of their triangulations, coarsest subdivisions, mixed subdivisions, and other decompositions is motivated by the mutual interaction between these fields as well as by applications in number theory, optimization, statistics, mathematical physics, and algorithmic biology. <br/> Attacking fundamental open problems in this area requires to combine theoretical insight with algorithmic ingenuity and computer experiments. Specific topics addressed in this proposal include the following: unimodular triangulations of lattice polytopes (in particular, matroid polytopes), the relationship between smoothness and normality of a toric variety, combinatorial and geometric interpretations of h^*-polynomials, and symmetric lattice polytopes. Interaction with other researchers in the Priority Program 1489 provides a unique opportunity which makes it likely to make substantial progress.
Triangulations and other decompositions of lattice polytopes in toric and tropical geometry
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.
Units in integral group rings
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.
Standard basis methods for path algebra quotients
The discipline of counting Galois extensions of global fields has been very active in the past years. Gunter Malle conjectured a precise asymptotic behavior of the cardinality of extensions with given Galois group for large discriminants. A recent counterexample draws attention to the case in positive characteristic, in which the group order is divisible by the characteristic. These cases were mostly ignored so far and regard function fields over finite fields of characteristic p and their wildly ramified extensions. <br/> The analysis of the counterexamples shows that a corresponding question on local function fields require investigation as well. By Hasse's Einseinheitensatz we get infinitely many extensions with given Abelian Galois group of order divisible by p and again we may ask for their distribution for large discriminants. <br/> In the proposed project we wish to understand the distribution of wildly ramified extensions of local or global function fields and derive a new conjecture on their asymptotic behavior to close the gap in Malle's conjecture. <br/> Beside theoretical aspects this involves extensive computer algebraic experiments, which should initiate and endorse the new conjecture as well as provide a new database on local function fields.
Asymptotics of wildly ramified Galois extensions of local or global function fields
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.
Computational Galois Theory for Local Fields
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: <br/> 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. <br/> 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. <br/> 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. <br/> 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. <br/> 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.
The objects of this proposal are five classes of algebras of interest in representation theory, knot theory and mathematical physics: <li> Classical Schur algebras (associated with the algebraic group GLn), <li> group algebras of symmetric groups, <li> Brauer algebras, <li> partition algebras, <li> the recently discovered Schur algebras of Brauer algebras. We will focus on a crucial and computationally accessible part of their cellular structure, the multiplication inside cellular subquotients, and on the information about simple modules, semisimplicity and other fundamental properties to be derived from this multiplication. The project consists of three main parts: First, we will develop algorithms and computer programs to calculate the relevant structure constants, even for large examples. Secondly, we will run experiments, especially by varying some of the discrete and of the continuous parameters of the algebras. Thirdly, we will use the output of the experiments to formulate precise conjectures about structure and independence of parameters and to get starting points for proofs of general results.
Experiments with cellular structures
Since the discovery of codes over finite rings which are better than codes over finite fields (it is possible to correct more errors using the same number of bits) there is an increased interest in codes over rings. In the proposed project we want to develop several algorithms to handle such codes. An important step is the computation of a canonical form of a linear code over a finite chain ring. As a byproduct this will also allow us to compute the group of automorphisms of a given code, and it will allow us to check whether two given codes are equivalent. We also want to use these algorithms to study similar objects like cryptographic functions and point-sets in a finite projective geometry. Having at hand a good algorithm we will also be able to classify certain codes, which allows to provide a complete list of all 'different' codes. One further application is the intended database of codes over rings, given in canonical form, as a further contribution to the international tables of error-correcting codes from our group. It extends our classification methods from codes over fields to codes over rings and should comprise the present knowledge on such codes. We want in addition to provide a test on pairwise equivalence to recognize cases where different constructions give isomorphic objects.
Algorithms for the Computation of Canonical Forms and Groups of Automorphisms of Linear Codes over Finite Rings and Related Objects
This project is part of mathematical Computer Algebra. It has applications in Ring Theory, Representation Theory, Computer Science and other disciplines. <br/> 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. <br/> 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. <br/> 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.
Development, implementation and applications of fundamental algorithms, relying on Gröbner bases in free associative algebras
Hecke algebras are a variety of structures playing a central role in algebra, in particular in the theory of finite groups and their representations. Here, we are interested in two classes of Hecke algebras: Iwahori-Hecke algebras and cyclotomic Hecke algebras, both of which are intimately connected to the representation theory of finite groups of Lie type. <br/> Motivated by theoretical questions concerning the structure and representation theory of these algebras, our aim is to develop new computational methods to handle Hecke algebras and their representations. To this end we will make combined use of techniques coming from various branches of computational mathematics, in particular from group theory and commutative algebra. These tools will then be applied to examine substantial interesting, but otherwise inaccessible examples, in order to collect data, to possibly detect previously unknown patterns, and thus to gain structural insights.
Computing with Hecke algebras
A character table encodes concisely and efficiently a lot of information about a particular finite group. In this project we consider generic character tables which describe and parameterize the character tables of certain infinite series of groups. <br/> The series of groups we consider are finite groups of Lie type. The classification of finite simple groups shows that most simple groups are closely related to finite groups of Lie type. <br/> The main aim of the proposed project is to develop a new software package, called GenCharLib, containing generic character tables as well as programs to compute with them. This will be implemented in the computer algebra system GAP. <br/> GenCharLib will serve the needs of specialists in the area by facilitating further extensions and applications. It will also make generic character tables more accessible to mathematicians who are not specialists in this field. Finally, it will enhance existing GAP-functions automatically, by providing missing methods for some computations. <br/> The package GenCharLib will build upon experience with a previous package that was based on the computer algebra system Maple. This is a subproject of the CHEVIE project which provides computational access to the representation theory of finite groups of Lie type and related structures. <br/> The proposed project was already mentioned under point (PB5) of the proposal for the Priority Programme 1489.
Generic Character Tables in GAP
The proposed research concerns the distribution of unramified extensions of number fields. For abelian extensions this is just the distribution of class groups. The applicant has recently found evidence that the Cohen–Lenstra heuristic breaks down for the part of the class group of order not prime to the order of the roots of unity in the base field. One major aim of this project is to obtain concrete numerical predictions from the global function field case. This involves deriving explicit formulas for the number of elements in finite symplectic groups over residue rings with given eigenspaces. <br/> In the non-abelian case we propose to study higher class groups of small derived length from a group theoretical point of view via the corresponding extension problems, and also to obtain first insights on unramified extensions with non-abelian simple Galois group by experimental methods. <br/> Historically, class field theory, the Cohen–Lenstra heuristic and the conjectures by the applicant on distributions of Galois groups and class groups were developed on the basis of examples and tables of statistics for large sets of fields. Correspondingly, besides theoretical parts our project has substantial computational and experimental aspects.
Class groups and unramified extensions of number fields
Since their introduction by Buchberger [1], Gröbner bases play a vital role in algorithmic algebra. However, often their calculation is infeasible for large examples, even though algorithms and computers improved. Thus, it is important to identify classes of ideals for which the calculation of Gröbner bases can be done efficiently, and to further develop known algorithms. <br/> The crucial parameter of Gröbner bases is the maximal degree of their polynomials as can be seen from all known proofs of complexity bounds. Hence, this parameter will be treated for different classes of ideal often occuring in practice (e.g. radical ideals, prime ideals, and toric ideals). The resulting insights shall be applied in order to enhance algorithms computing Gröbner bases and alike.
Degree Bounds for Gröbner Bases of Important Classes of Polynomial Ideals and Efficient Algorithms (GBiC PolyA)
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.
Computational aspects of block theory of finite groups
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.
Arithmetic methods for finitely generated matrix groups
The Thomas decomposition based on a formal triangulation algorithm by J. M. Thomas in the 1930s, now implemented in its full generality for the first time, decomposes the set of solutions of a system of equations and inequations into disjoint subsets corresponding to so called simple systems. The system might be either polynomial or polynomial differential. In the polynomial case one obtains a counting polynomial for the solutions, which depends slightly on the chosen coordinate system. Here the challenge is to study this polynomial for generic and nongeneric coordinates (where methods from representation theory of algebraic groups are to be used), to extract more refined combinatorial information from the Thomas decomposition, and to improve the implementation by getting structural insight into the decomposition. In the differential case the aim is to define counting polynomials for free Taylor coefficients via a common generalization of the algebraic case and Janet's approach to linear PDEs. We also expect applications to the algebraic analysis of numerical methods for solving nonlinear PDEs.
Elimination and Counting via Thomas Decomposition
Coxeter groups are groups of symmetries which form part of many physical theories about the world we live in. Moreover, these groups are frequently found at the heart of deep mathematical theories, most notably Lie theory. This project is concerned with two seemingly unrelated algebras, the Orlik-Solomon algebra and the Descent algebra, both of which describe certain geometric and combinatorial aspects of the underlying Coxeter group. Experimental evidence suggests the existence of surprising connections between these two algebras. These have been formulated as two precise conjectures about decompositions of certain natural representations of these algebras. A proof, even of special cases of these conjectures, will greatly enhance our understanding of Coxeter groups and the algebras associated to them and potentially impact on other theories involving these groups of symmetries.
Computational aspects of the Cohomology of Coxeter arrangements: On Conjectures of Lehrer-Solomon and Felder-Veselov
The proposed research concentrates on the design and development of efficient algorithms to handle complex geometric objects with quality guarantees. Algorithms of this kind constitute an important basis for applications in Computer Aided Design, robotics or computer vision. Our overall philosophy requires that our solutions cope with any input and that the output matches the mathematically exact result. Moreover, we request two-fold efficiency: While we aim at proving low complexity of our algorithms, we also want them to compete with existing non-reliable software on inputs that can be handled by these implementations. That is, the runtime should adaptively depend on the difficulty of the input. <br/> It is a challenge to achieve reliability and efficiency simultaneously. A canonical way to tackle degenerate situations is by means of computer algebra methods (Gröbner bases, resultants, etc.) based on exact symbolic computations. Although constituting powerful tools, their efficiency suffers from several drawbacks such as coefficient blowups during computation, non-adaptiveness and difficulties in parallelizing the computation. <br/> By combining fast approximate with exact symbolic methods we expect adaptiveness as well as a significant speed up of the overall approach. We want to achieve this by the development of adaptive root separation and perturbation bounds for univariate polynomials and polynomial systems based on additional information gained from the approximate computation. Furthermore, the number of costly symbolic computation steps over integers should be reduced or replaced by modular computations.
Design, analysis, and implementation of efficient and reliable algorithms for complex geometric objects
Many challenging problems in geometry concern flow equations like e. g. mean curvature flow or Ricci flow. The behavior of solutions to such flow equations is often controlled as follows: For a geometrically significant quantity, the evolution equation is computed. It is proved that this quantity is monotone, i. e. a Lyapunov function. This allows to control solutions of the flow equation. <br/> The computation of evolution equations for prospective Lyapunov functions is purely algebraic but usually quite tedious. We propose to develop a program that does these algebraic computations in many different situations. We also wish to use algebraic and experimental methods to select prospective Lyapunov functions and to check, whether the resulting evolution equations allow to deduce monotonicities. <br/> Based on these Lyapunov functions we wish to provide a tool to systematically prove new theorems for geometric evolution equations. We want to focus on the behavior of solutions for large times or near singularities.
Computer algebra for geometric evolution equations
An algebraic variety M is unirational, if there exists a dominant P^n -> M. On the other extreme, M is of general type, if the canonical bundle K_M is big. In the first case it is easy to find points on M, in the second case there is no P^1 through a general point of M. <br/> The question whether a variety is of one of these types is especially important for moduli spaces, such as the moduli of curves M_g. If a moduli space M is unirational then we can in principle write down a dominant family depending on free parameters. In case of general type, any set of parameters satisfy a system of algebraic equations. We plan to investigate various refined moduli spaces of curves such as M_{g,d}^r = {(C,g_d^r)} of curves C together with an r-dimensional linear system g_d^r of divisors of degree d on C. In case the moduli space is unirational we want to provide a computer algebra code which chooses points at random, which will be useful for further experimental investigations.
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.
Syzygies, experiments in algebraic geometry and unirationality questions for moduli spaces
We will analyse bifurcations and singularities of algebraic systems of ordinary differential equations with particular emphasis on questions concerning the existence of oscillations. Exploiting previous results that the study of bifurcations for normal systems of ordinary differential equations leads to questions in real algebraic geometry, we will develop efficient algorithmic methods for parametric bifurcation analysis and use them both for experimental mathematical investigations of low dimensional systems and for "real world applications" like the analysis of controllers for humanoid locomotions or the analysis of chemical reaction systems of non-trivial size. Then we will extend these results to non-normal systems, i. e. to differential algebraic equations (DAEs), and study both the effect of singularities on bifurcations and the relationship between bifurcations of DAEs and singularities of associated systems of partial differential equations. Another major goal consists of making all the developed algorithmic methods available in an integrated form in a common software environment.
Bifurcations and Singularities of Algebraic Differential Equations
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.
Algorithmic methods in the modular representation theory of diagram algebras
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.
Computational methods for abelian varieties over number fields with complex multiplication
This proposal contains two projects related in various ways to the arithmetic of algebraic varieties and to the study of their rational points in particular. <br/> The aim of the first project is to devise and implement an algorithm that produces a nice set of equations for a given variety; this is important for doing further computations with it. In many cases, further computations would be infeasible without such a nice model. <br/> The second project is more specifically concerned with rational points on curves of higher genus. It is known that on each such curve there can be only finitely many rational points, but so far there is no algorithm that determines this set explicitly. We will improve and extend existing algorithms covering certain cases. We will then use them to gather statistical information from many curves to get some more precise idea on the behavior of their rational points. On the other hand, we plan to study possible approaches to a general algorithm that finds the set of rational points on any given curve.
Algorithmic and Experimental Arithmetic Geometry
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.
The Generalized Fermat Equation with exponents 2, 3, n
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.
Effective methods for spectrahedra in real and convex algebraic geometry
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.
Toroidal methods for computing zeta functions of groups and rings
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. <br/> The objectives of this proposal concern the investigation of these geometric and arithmetic objects either directly or through the correspondence as well as an extension of the correspondence to new cases. A special emphasis is placed on these aspects over finite fields and modulo prime powers. Concrete questions deal with the modularity as well as level and weight optimisation of Galois representations modulo prime powers and the explicit determination of the local Galois representations attached to classical and Hilbert modular forms at all primes. <br/> 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. These new computer tools will be of service to other researchers as well.
Algorithmic and experimental aspects of modular Galois representations over finite and modulo prime powers
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.
The proposal fits into the DFG priority programme SPP1489, which aims at combining computer algebra methods from different areas of mathematics, and to apply the resulting algorithms to central problems of theoretical and practical interest. <br/> It is our aim to develop and implement algorithms to compute and analyse the monodromy representation for families of varieties depending on a parameter t. Rather than striving for complete generality, we propose to start with hypersurfaces 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. It is our intention to develop these algorithms inside the SINGULAR system.
Monodromy Algorithms in Singular
A list of project descriptions both from phase 1 and phase 2 extracted from the SPP 1489 web site. The person names are added to the CAFG-Intern RDF Graph, the project URIs need further alignment.
SPP 1489 Projects