Skip to main content
main-content

Über dieses Buch

This book contains 22 lectures presented at the final conference of the Ger­ man research program (Schwerpunktprogramm) Algorithmic Number The­ ory and Algebra 1991-1997, sponsored by the Deutsche Forschungsgemein­ schaft. The purpose of this research program and of the meeting was to bring together developers of computer algebra software and researchers using com­ putational methods to gain insight into experimental problems and theoret­ ical questions in algebra and number theory. The book gives an overview on algorithmic methods and on results ob­ tained during this period. This includes survey articles on the main research projects within the program: • algorithmic number theory emphasizing class field theory, constructive Galois theory, computational aspects of modular forms and of Drinfeld modules • computational algebraic geometry including real quantifier elimination and real algebraic geometry, and invariant theory of finite groups • computational aspects of presentations and representations of groups, especially finite groups of Lie type and their Heeke algebras, and of the isomorphism problem in group theory. Some of the articles illustrate the current state of computer algebra sys­ tems and program packages developed with support by the research pro­ gram, such as KANT and LiDIA for algebraic number theory, SINGULAR, RED LOG and INVAR for commutative algebra and invariant theory respec­ tively, and GAP, SYSYPHOS and CHEVIE for group theory and representation theory.

Inhaltsverzeichnis

Frontmatter

Algorithmic Algebraic Number Theory

Frontmatter

Sieving Methods for Class Group Computation

Abstract
Computing the class group and regulator of an algebraic number field K are two major tasks of algorithmic algebraic number theory. The asymptotically fastest method known has conjectured sub-exponential running time and was proposed in [5]. In this paper we show how sieving methods developed for factoring algorithms can be used to speed up this algorithm in practice. We present numerical experiments which demonstrate the efficiency of our new strategy. For example, we are able to compute the class group of an imaginary quadratic field with a discriminant of 55 digits 20 times as fast as S. Düllmann in an earlier record-setting implementation ([1]) which did not use sieving techniques. We also present class numbers of large cubic fields.
Johannes Buchmann, Michael J. Jacobson, Stefan Neis, Patrick Theobald, Damian Weber

Arithmetic of Modular Curves and Applications

Abstract
The aim of this article is to describe a computational approach to the study of the arithmetic of modular curves Xo(N)and to give applications of these computations.
Gerhard Frey, Michael Müller

Local and Global Ramification Properties of Elliptic Curves

Abstract
As is well-known, the arithmetic of elliptic curves E in characteristics two and three shows some special features peculiar to these characteristics.
Ernst-Ulrich Gekeler

Techniques for the Computation of Galois Groups

Abstract
Galois theory stands at the cradle of modern algebra and interacts with many areas of mathematics. The problem of determining Galois groups therefore is of interest not only from the point of view of number theory (for example see the article [39] in this volume), but leads to many questions in other areas of mathematics. An example is its application in computer algebra when simplifying radical expressions [32].
Alexander Hulpke

Fortschritte in der inversen Galoistheorie

Abstract
Dieser Bericht setzt die mit Matzat (1988,1991b) begonnene Reihe von Ubersichtsartikeln tiber konstruktive Galoistheorie fort und gibt einen Uberblick tiber seither erreichte neue Resultate. Da inzwischen mehrere einftihrende Texte in Buchform von Matzat (1987), Serre (1992), V6lklein (1996) sowie Ishkhanov, Lure und Faddeev (1997) vorhanden sind, kann ich mich bei der Zusammenstellung der Grundlagen sehr kurz fassen. Eine ausftihrliche Darstellung mit Beweisen der meisten der hier zusammengestellten Resultate wird im Ergebnisbericht Malle, Matzat (1998) enthalten sein.
B. Heinrich Matzat

From Class Groups to Class Fields

Abstract
Since the first printing of the book [35] by H. Zassenhaus and the author in 1989 algorithmic algebraic number theory has attracted rapidly increasing interest. This is documented, for example, by a regular meeting ANTS (algebraic number theory symposium) every two years whose proceedings [1], [6] give a good survey about ongoing research. Also there are several computer algebra packages concentrating on number theoretical computations. At present the most prominent ones, which are available for free, are Kant [12], Pari [2] and Simath [27]. Kant comes with a data base for algebraic number fields, already containing more than a million fields of small degree. Kant is developed by the research group of the author at Berlin and will be presented in some detail in section 5. We note that almost all of Kant and Pari is also contained in the Magma system [4].
Michael E. Pohst

A Gross-Zagier Formula for Function Fields

Abstract
In their famous article [7], Gross and Zagier proved a formula relating heights of Heegner points on modular curves and derivatives of L-series of cusp forms.
Hans-Georg Rück, Ulrich Tipp

Extremal Lattices

Abstract
Extremal lattices (in the sense of integral quadratic forms) have been introduced in the unimodular case by C.L. Mallows, A.M. Odlyzko and N.J.A. Sloane in 1975; a finiteness result dealing with the hypothetical theta series of such lattices was given. Recently, H.-G. Quebbemann has extended the notion to so called modular even lattices of levels 2, 3, 5, 7, 11 and 23, and part of the genera of levels 6, 14 and 15 containing strongly modular lattices. In the present paper, the above mentioned finiteness result is generalized to all genera of lattices considered by Quebbemann. For minimal norms at most 8, a detailed overview on the existence and uniqueness of extremal lattices is given, including some information about hermitian stuctures on such lattices. Using an obvious generalization of the notion of extremality, similar results are obtained for other genera of levels 6, 14 and 15, and for the levels 10 and 21 not considered before. For the construction of lattices, a computer implementation of Kneser’s neighbor method is an important tool.
Rudolf Scharlau, Rainer Schulze-Pillot

Algorithmic Commutative Algebra and Algebraic Geometry

Frontmatter

On the Real Nullstellensatz

Abstract
We give a survey of three implemented real quantifier elimination methods: partial cylindrical algebraic decomposition, virtual substitution of test terms, and a combination of Grabner basis computations with multivariate real root counting. We examine the scope of these implementations for applications in various fields of science, engineering, and economics.
Eberhard Becker, Joachim Schmid

Primary Decomposition: Algorithms and Comparisons

Abstract
The Hilbert series and degree bounds play significant roles in computational invariant theory. In the modular case, neither of these tools is avrulable in general. In this article three results are obtruned, which provide partial remedies for these shortcomings. First, it is shown that the so-called extended Hilbert series, which can always be calculated by a MoHen type formula, yields strong constraints on the degrees of primary invariants. Then it is shown that for a trivial source module the (ordinary) Hilbert series coincides with that of a lift to characteristic 0 and can hence be calculated by MoHen’s formula. The last result is a generalization of Goöbel’s degree bound to the case of monomial representations.
Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister

Real Quantifier Elimination in Practice

Abstract
We consider polynomials and rational functions which are invariant under the action of a finite linear group. The aim is to give a survey over the knowledge on some structural properties of such rings and fields of invariants. Particular emphasis lies on the modular case, where the characteristic of the ground field divides the group order.
Andreas Dolzmann, Thomas Sturm, Volker Weispfenning

Hilbert Series and Degree Bounds in Invariant Theory

Abstract
The algorithm for computing a miniversal deformation of an isolated singularity using Massey products and its implementation in SINGULAR is explained. For completeness the cotangent cohomology and the obstruction calculus is described in concrete terms as well.
Gregor Kemper

Invariant Rings and Fields of Finite Groups

Abstract
This article gives an overview over recent developments of algorithms for computing free resolutions based on Grobner basis techniques. These developments realize the following main ideas: 1. Minimization of resolutions are integrated as much as possible into the standard basis algorithm. 2. Hilbert functions are used to avoid reductions of useless pairs. 3. Special orderings and strategies are used to increase the computational efficiency.
Gregor Kemper, Gunter Malle

Computing Versal Deformations with Singular

Abstract
This article is a survey on the Real Nullstellensatz and related topics. Special emphasis is put on computational aspects.
Bernd Martin

Algorithms for the Computation of Free Resolutions

Abstract
R. Brauer posed in his famous lectures on modern mathematics 1963 more than 40 problems, questions and conjectures about the representation theory of finite groups, cf. [10]. These questions have had a big influence on the development of the theory since then. Most of the problems may be summarized under the following central question.
Thomas Siebert

Algorithmic Group and Representation Theory

Frontmatter

Computational Aspects of the Isomorphism Problem

Abstract
The aim of this article is to lead the reader on a journey through the representation theory of finite groups of Lie type and Hecke algebras. We will present some basic results obtained in recent years, explain the ideas behind them, and give lots of examples; proofs are usually omitted but we provide explicit references to an extensive bibliography.
Frauke M. Bleher, Wolfgang Kimmerle, Klaus W. Roggenkamp, Martin Wursthor

Representations of Heeke Algebras and Finite Groups of Lie Type

Abstract
R. Brauer posed in his famous lectures on modern mathematics 1963 more than 40 problems, questions and conjectures about the representation theory of finite groups, cf. [10]. These questions have had a big influence on the development of the theory since then. Most of the problems may be summarized under the following central question.
Richard Dipper, Meinolf Geck, Gerhard Hiss, Gunter Malle

The Groups of Order 512

Abstract
Recent progress in computational representation theory is surveyed. As an application of some methods for constructing ordinary character tables Brauer pairs among 2-groups of order up to 28 are determined. Furthermore the present status of the library of the tables of marks for simple groups which is available in GAPis described. Finally the state of the art of computational modular representation theory is summarized, by listing not only results on Brauer character tables of finite simple groups, which have been computed since the appearance of the first part of this paper, but also recent advances in the algorithms for dealing with representations over finite fields as well as Brauer characters. Also results concerning the structure of the module category of the group algebra of a finite simple group are reviewed.
Bettina Eick, E. A. O’Brien

Computational Aspects of Representation Theory of Finite Groups II

Abstract
The classification of the finite simple groups is one of the important achievements of the mathematicians in this century. According to p. 3 of the recent book [16] by Gorenstein, Lyons and Solomon “The existing proof of the classification of the finite simple groups runs to somewhere between 10 000 and 15 000 journal pages, spread across some 500 separate articles by more than 100 mathematicians .... As a result of these various factors, it is extremely difficult for even the most diligent mathematician to obtain a comprehensive picture of the proof by examining the existing literature.” On p. 45 of [16] these authors write: “The most serious problem concerns the sporadic groups, whose development at the time of the completion of the classification theorem was far from satisfactory. The existence and uniqueness of the sporadic groups and the development of their properties form a very elaborate chapter of simple group theory, spread across a large number of journal articles. Moreover, some of the results are unpublished (e.g. Sims’ computer calculations establishing the existence and uniqueness of the Lyons group Ly).Furthermore, until very recently, the two principal sources for properties of the sporadic groups were [5] and [15], Part 1, §5 consisting only of statements of results without proofs.”
Klaus Lux, Herbert Pahlings

High Performance Computations in Group Representation Theory

Abstract
The finite subgroups of GLn(Q) are classified up to dimension n = 31 by giving a system of representatives for the conjugacy classes of the maximal finite ones ([12], [9], [15],[16], [17]) cf. [11] for a survey on this and interrelations between these groups. Recently the classification has been extended to the one of absolutely irreducible maximal finite subgroups G of GLnCD),where V is a totally definite quaternion algebra and n. dimQ(V) ::; 40. As usual a subgroup G ::; GLn(V) is called absolutely irreducible, if the enveloping Q-algebra Q:i := {EgEG agg I ag E Q} ~ vnxn is the whole matrix ring vnxn (cf. [8]). The classification of these groups yields a partial classification of the rational maximal finite matrix groups in the new dimensions 32, 36, and 40 on one hand and on the other hand it gives nice Hermitian structures for interesting lattices. For example one finds eleven quaternionic structures of the Leech lattice as a Hermitian lattice of rank n > 1 over a maximal order in a definite quaternion algebra Vwith absolutely irreducible maximal finite automorphism group as displayed in Table 1. Rather than giving a survey of the classification results this note is devoted to a general structure theorem (cf. Theorem 4 below).
Gerhard O. Michler

The Structure of Maximal Finite Primitive Matrix Groups

Abstract
Solving equations belongs to the oldest problems in mathematics. In a wider sense, analyzing a group presentation belongs to this class of problems, because one wants to know the most general solutions of the defining relations. It is well known that there is no general procedure to solve the word problem by the famous Novikov-Boone Theorem, cf. [30] Chapter 13 for an exposition. Even deciding the question whether G is finite or infinite cannot be solved in general. Nevertheless, one can try to prove that G is infinite, if one suspects this, by solving the equations given by the relators in some group, where one can compute, for example in a matrix group. In case of success this produces an epimorphic image of G which might be infinite. And even if it is finite, one might use the representations of the finite quotient to produce bigger epimorphic images. Various techniques for carrying out these ideas have been developed over the last years. They will be described in the next few chapters.
Gabriele Nebe

Presentations and Representations of Groups

Abstract
Primary decomposition of an ideal in a polynomial ring over a field belongs to the indispensable theoretical tools in commutative algebra and algebraic geometry. Geometrically it corresponds to the decomposition of an affine variety into irreducible components and is, therefore, also an important geometric concept.
W. Plesken

Backmatter

Weitere Informationen