Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1999 | Buch

Sieving Methods for Class Group Computation Kapitel lesen Erstes Kapitel lesen

Algorithmic Algebra and Number Theory

Selected Papers From a Conference Held at the University of Heidelberg in October 1997

herausgegeben von: B. Heinrich Matzat, Gert-Martin Greuel, Gerhard Hiss

Verlag: Springer Berlin Heidelberg

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Ü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 Jr., 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
Metadaten
Titel
Algorithmic Algebra and Number Theory
herausgegeben von
B. Heinrich Matzat
Gert-Martin Greuel
Gerhard Hiss
Copyright-Jahr
1999
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-59932-3
Print ISBN
978-3-540-64670-9
DOI
https://doi.org/10.1007/978-3-642-59932-3