Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Algorithmic analysis of presentations of groups and modules [Elektronische Ressource] / vorgelegt von Anna Wiktoria Fabianska

184 pages
Algorithmic analysis of presentationsof groups and modulesVonderFakultätfürMathematik,InformatikundNaturwissenschaftenderRWTHAachenUniversityzurErlangungdesakademischenGradeseinerDoktorindergenehmigteDissertationvorgelegtvonM.Sc.AnnaWiktoriaFabianska´ausDanzig(Gdansk,´ Polen)Berichter: UniversitätsprofessorDr. WilhelmPleskengen. WiggerUnivDr. EvaZerzTagdermündlichenPrüfung: 31. Juli2009DieseDissertationistaufdenInternetseitenderHochschulbibliothekonlineverfügbar.ContentsIntroduction 51 Ideals inZ[x ,...,x ] 91 n1.1 Janet’s algorithm overZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2 Computation of a maximal ideal containing a given ideal . . . . . . . . . . . . . . . . . 121.3 Minimal associated prime ideals inZ[x ,...,x ] . . . . . . . . . . . . . . . . . . . . . 161 n2 An algorithm for the Quillen Suslin Theorem 252.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.2 Heuristic methods over an arbitrary ring . . . . . . . . . . . . . . . . . . . . . . . . . . 272.2.1 (p−1)×p unimodular matrices over an arbitrary ring . . . . . . . . . . . . . . 282.2.2 1×p unimodular rows over an arbitrary ring . . . . . . . . . . . . . . . . . . . 282.3 A QS algorithm for commutative polynomial rings . . . . . . . . . . . . . . . . . . . . 302.3.1 Normalization Step: Monic polynomials . . . . . . . . . . . . . . . . . . . . . . 312.3.2 Local Step: Horrocks’ Theorem . . . . . . . . . .
Voir plus Voir moins

Algorithmic analysis of presentations
of groups and modules
VonderFakultätfürMathematik,InformatikundNaturwissenschaften
derRWTHAachenUniversity
zurErlangungdesakademischenGradeseinerDoktorinder
genehmigteDissertation
vorgelegtvon
M.Sc.
AnnaWiktoriaFabianska´
ausDanzig(Gdansk,´ Polen)
Berichter: UniversitätsprofessorDr. WilhelmPleskengen. Wigger
UnivDr. EvaZerz
TagdermündlichenPrüfung: 31. Juli2009
DieseDissertationistaufdenInternetseitenderHochschulbibliothekonlineverfügbar.Contents
Introduction 5
1 Ideals inZ[x ,...,x ] 91 n
1.1 Janet’s algorithm overZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Computation of a maximal ideal containing a given ideal . . . . . . . . . . . . . . . . . 12
1.3 Minimal associated prime ideals inZ[x ,...,x ] . . . . . . . . . . . . . . . . . . . . . 161 n
2 An algorithm for the Quillen Suslin Theorem 25
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Heuristic methods over an arbitrary ring . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.1 (p−1)×p unimodular matrices over an arbitrary ring . . . . . . . . . . . . . . 28
2.2.2 1×p unimodular rows over an arbitrary ring . . . . . . . . . . . . . . . . . . . 28
2.3 A QS algorithm for commutative polynomial rings . . . . . . . . . . . . . . . . . . . . 30
2.3.1 Normalization Step: Monic polynomials . . . . . . . . . . . . . . . . . . . . . . 31
2.3.2 Local Step: Horrocks’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3.3 Patching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.4.1 Computing bases of finitely presented modules over polynomial rings . . . . . . 37
2.4.2 Application to multidimensional systems theory . . . . . . . . . . . . . . . . . . 39
2.4.3 Applications to algebraic geometry . . . . . . . . . . . . . . . . . . . . . . . . 40
2.5 The QUILLENSUSLIN package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 AnL quotient algorithm 452
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 Computing ring relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.1 Representation intoPSL(2,R) viaSL(2,R): sign systems . . . . . . . . . . . . 47
3.3.2 Group relations to ring relations: representation ideals . . . . . . . . . . . . . . 50
3.3.3 Trace calculus and trace representation ideals . . . . . . . . . . . . . . . . . . . 52
3.4 Subgroup tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4.1 Reducibility of representation . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4.2 Semidirect products of elementar abelianp groups with cyclic group . . . . . . . 65
3.4.3 Dihedral groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.4.4 Groups isomorphic toA ,S ,A . . . . . . . . . . . . . . . . . . . . . . . . . 674 4 5
3.4.5 Recognition ofPGL(2,q) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
12 CONTENTS
3.6 The PSL package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Appendix 89Kurzfassung
In dieser Arbeit wird der Janet Algorithmus zur Behandlung von Polynomsystemen zur Lösung zweier
algebraischer Probleme angewandt:
1. der expliziten Konstruktion einer Basis eines freien Modules über Polynomringen im Sinne des
Satzes von Quillen und Suslin,
2. der Bestimmung aller endlichenL Faktorgruppen endlich präsentierten Gruppen.2
Der Schwerpunkt der Arbeit liegt in den konstruktiven Aspekten aller betrachteter Probleme und in der
Entwicklung von entsprechenden Methoden und Algorithmen. Zusätzlich zur Theorie werden zwei die
Arbeit begleitende Maple Pakete,QUILLENSUSLIN und PSL, vorgestellt.
Das erste Kapitel behandelt algorithmische Berechnungsmethoden für polynomiale Systeme mit
ganzen Koeffizienten. Zum Beispiel wird hier für ein gegebenes Ideal des Polynomringes überZ die
Konstruktion eines es umfassenden maximalen Ideals sowie die Konstruktion aller minimalen assozierten
Primidealen vorgestellt.
Das zweite Kapitel ist dem Satz von Quillen und Suslin gewidmet. Ein algorithmischer Beweis
dieses Satzes wird gegeben. Insbesondere ein Algorithmus zur Berechnung einer Basis eines freien
Moduls über dem Polynomring mit Koeffizienten in einem Hauptidealbereich wird vorgestellt. Das
Problem wird in der Sprache der unimodularen Matrizen ausgedrückt: Die Bestimmung einer Basis eines
freien Moduls kann als Ergänzung einer unimodularen Matrix zur einer quadratischen invertierbaren
Matrix formuliert werden. Der allgemeine induktive Algorithmus (dessen Entwurf auf [LS 92], [PW 95]
und [G V 02] basiert) wurde mit neuen heuristischen Methoden ausgestattet, die es ermöglichen, den
längeren induktiven Weg in vielen Fällen zu umgehen bzw. zu verkürzen. Die vorgestellten Methoden
wurden in dem Maple PaketQUILLENSUSLIN implementiert.
Zum Schluss werden einige Anwendungen des Satzes von Quillen und Suslin (präziser, der Möglichkeit
eine konstruktive Basisbestimmung für einen freien Modul durchzuführen) in der Systemtheorie sowie in
der algebraischen Geometrie präsentiert. Eine sehr große Sammlung von Beispielen, die die Anwendung
des QUILLENSUSLIN Paketes veranschaulichen, ist im Appendix B enthalten.
Das dritte Kapittel befasst sich mit der Analyse endlich präsentierter Gruppen. Eine der vielen Auf
gaben die man zur einer gegebenen endlich präsentierte Gruppe stellen kann, nämlich die algorithmische
Entscheidung, obG endlich ist, ist bekanntermaßen in Allgemeinen unlösbar.
Diese Arbeit geht von endlich präsentierten GruppenG gegeben auf zwei und drei Erzeuger aus. Ein
Algorithmus (später derL -Algorithmus gennant) zur Bestimmung der Anzahl aller NormalteilerN der2
mit der FaktorgruppeG/N von TypL wird vorgestellt. Dabei heißt eine endliche Gruppe vom TypL2 2
αwenn eine Primzahl p und eine natürliche Zahl α existieren, so dass sie entweder zur PSL(2,p ) oder
αzurPGL(2,p ) isomorph ist.
Die Bedeutung dieses Algorithmes liegt in der Möglichkeit, alle Faktorgruppen von Typ L (also2
aus der großen Klasse endlichen einfachen Gruppen) einzeln zu bennenen. In dem Fall, wenn der Al
gorithmus unendlich viele Normalteiler vom Typ L liefert, hat man für G eine starke Form eines Un 2
endlichkeitsbeweises. Weiterhin, falls unendlich viele Primzahlen involviert sind, kann man sogar eine
nicht auflösbare unendliche Matrixgruppe vom Grad 2 über einem Körper der Charakteristik 0 als ein
epimorphisches Bild vonG angeben. Im Allgemeinen kann man mithilfe des Begriffes Krull Dimension
verschiedene Typen von Unendlichkeit unterscheiden.Introduction
This thesis deals with two new applications of Janet’s algorithm: firstly with an explicite basis construc
tion in the context of the Quillen Suslin Theorem and secondly with an analysis of finite group presen
tations, more precisely enumerating finiteL quotients of finitely presented groups. The emphasis has2
been put on the constructive aspects of all considered issues and on the development of methods and
algorithms. Finally, all algorithms have been implemented in the CAS system Maple in two packages
accompanying this thesis: QUILLENSUSLIN and PSL.
An algorithm for the Quillen Suslin Theorem
Projective modules are an important class of modules generalizing free modules. While projectivity of a
module is relatively easy to test, the freeness is often not. The famous conjecture due to Serre, that the two
notions, projectivity and freeness coincide in the special case of modules over polynomial rings had been
proven independently by Quillen and Suslin in 1976. The development of Gröbner Bases techniques
has initiated algorithmic proofs of this theorem and attempts to compute a free basis of a given free
module. However no working implementation carring out the computation of a basis for free modules
was available up to now. In this thesis the algorithm outlined in [LS 92] has been adopted also to the
case of polynomial rings with integer coefficients and enriched by heuristic methods and accompanied
by an implementation of all the presented algorithms in the Maple packageQUILLENSUSLIN for dealing
with modules over polynomial rings with rational and integer coefficients. Finally, a few applications of
the Quillen Suslin theorem, more precisely of the actual basis computation for a free module to system
theory and to algebraic geometry, which demonstrate the power of the implementation will be presented.
TheL quotient algorithm for finitely presented groups2
The second problem concerns the analysis of finitely presented groups. Among the many questions one
can ask about a given finitely presented group, the algorithmic decision whetherG is finite or not, stands
out as being impossible in general. Often the finiteness of a group can be proved using classical meth
ods such as Todd Coxeter Algorithm, sometimes infiniteness can be proved by exhibiting a subgroup
of finite index with infinite abelianization, to mention the most popular methods. This thesis gives an
algorithm, which can decide (in case the number of generators is smaller than 4) whether the number of
normal subgroupsN ofG with the quotientG/N of typeL is finite or infinite and is therefore called a2
αL -quotient algorithm. Here a finite group is called to be of typeL , if it is isomorphic toPSL(2,p ) or2 2
αtoPGL(2,p ) for some prime numberp and some natural numberα. The significance of the algorithm
56
is that for the first time one can enumerate all factor groups in a big class of finite simple groups. Note,
α αPSL(2,p ) is simple forp >3 and - looking at their orders - most finite simple groups are ofL type.2
In case the computation yields infinitely many normal subgroups of typeL , one has a particularly strong2
form of an infiniteness proof. If many primes are involved one can even exhibit a non soluble
infinite matrix group of degree 2 over a field of characteristic zero as epimorphic image. In general one
can even distinguish certain kinds of infiniteness by using the notion of Krull dimension for commutative
domains.
General methods
The presented ideas, proposed algorithms, and their implementation would not be accessible if the ef
ficient methods for dealing with polynomial systems had not been developed before. In particular the
Janet’s algorithm as a particularly powerful version of Gröbner basis algorithms turned out to be very
profitable. Since for both problems tackled here the issues of computation in polynomial ring with integer
coefficients are essential, the first part of this thesis is devoted to dealing with non invertible coefficients
and in particular to describing algorithms returning maximal ideals or the set of minimal associated prime
ideals for a given ideal inZ[x ,...,x ].1 n
Outline
The thesis is organized as follows: The first chapter is devoted to algorithmic and computational issues
concerning polynomial systems with integer coefficients. In the second chapter an algorithmic proof of
the Quillen Suslin Theorem is given, in particular an algorithm for computing a basis of free module
over a polynomial ring over principle ideal domains together with a discussion of the implementation for
Q andZ as ground rings. At the end some applications are discussed. Chapter 3 describes the method
for computing allL type quotient groups of a finitely presented group. The case of groups with two or2
three generators is treated in detail. At the end of Chapter 2 and Chapter 3 the Maple Packages QUIL-
LENSUSLIN and PSL are briefly presented. Finally, in Appendix A the reader will find a few examples
of phenomena occurring during computations in polynomial rings with integer coefficients, and in Ap
pendix B a very rich library of examples illustrating the use and applications of the QUILLENSUSLIN
package is given.
Some of the results presented in this thesis have been published in [FQ 07] and [PlF 09]. In some
cases, these are only quoted, in others, details missing in the publications are given here. Completely
new in this thesis are the possibility of computing a better basis of a free module, examples for the ap
plication of the Quillen Suslin theorem to the algebraic geometry in Chapter 2, and in Chapter 3 the case
of three generator groups.
Acknowledgments
I would like to express my gratitude to many people. First of all to the dedicated teachers from whom I
could learn during the last few years.
I thank Prof. Dr. W. Plesken for the opportunity to carry out my PhD studies in his research group at
the RWTH Aachen, for his daily guidance, constant interest and constructive criticism which motivated7
me to do my best. In particular, I thank him for introducing me to the very interesting problem of
computing allL quotienst of a finitely presented group and his support during my work on this project.2
I am grateful to Dr. A. Quadrat for collaboration on the topics related to the Quillen Suslin theorem:
for the many fruitful discussions in Aachen and in Sophia Antipolis, many useful suggestions, motivation
and inspiration.
I also thank Prof. Dr. E. Zerz for undertaking the review of this thesis, for her interest and motivating
discussions.
Further, I would like to thank many others, in particular Prof. Dr. J. F. Pommaret for the discussions
on Lin Bose Conjecture, and Prof. Dr. F. Castro Jimenez for examples of applications of Quillen Suslin
theorem to algebraic geometry. I also appreciated the possibility to meet Prof. Dr. J. Gago Vargas and
learn the very interesting example (Example 9, Appendix B). It was finally very motivating for me to
discuss this example and other related problems with Prof. Dr. A. van den Essen personally.
I am very grateful to all - past and present - members of Lehrstuhl B für Mathematik and Lehrstuhl II
für Mathematik for the nice working atmosphere and their willingness to help. In particular I would like
to thank Dr. Mohamed Barakat, Dr. Daniel Robertz and Gehrt Hartjen for their help, many discussions
(on topics related to my research problems as well as on INVOLUTIVE and the philosophy of HOMALG),
their interest in my progress and introducing me to Maple. I wish to express my gratitude also to other
members of the B team: Dr. Arne Lorenz, Sabrina Grande, Thomas Bächler, Markus Lange Hegermann,
Sebastian Jambor and Jan Jongen for sharing with me their ideas and in this way contributing to this
thesis. Finally, I am very grateful to Wolfgang Krass for the proof reading.
Last, but not least, I am very grateful to my friends and family for their never ending patience and
support.8Chapter 1
Ideals inZ[x ,...,x ]n1
The common denominator of the next two chapters is dealing with ideals in the polynomial ring with
integer coefficients. Solving a system of polynomial equations corresponds naturally to computing max
imal ideals (containing the ideal generated by the given relations) in the underlying polynomial ring. In
the settings of this thesis one is especially interested in solving systems of polynomial equations with
integer coefficients. Thus, to be able to compute efficiently with such a polynomial system, we recall first
the notion of Janet bases and an algorithm providing with a basis for a ideal inZ[x ,...,x ].1 n
Further, the problem of computing all maximal ideals containing a given one will be discussed. Finally,
since every maximal ideal containing a given ideal I contains an associated prime of I, we are espe
cially interested in computing all minimal associated prime ideals of a given ideal inZ[x ,...,x ]. The1 n
main difficulty while dealing with those problems is the ring of coefficients: unlikely to the computation
in polynomial rings with coefficients in fields one needs to consider the consequences of existence of
non invertible coefficients.
This chapter is devoted to a few general computational problems arising while dealing with ideals
in the polynomial ringZ[x ,...,x ]. Readers to whom most of these topics are familiar may wish to1 n
proceed directly to Chapter 2 and refer back to this chapter when needed.
α α αn1LetA[x] denote the polynomial ringA[x ,...,x ] andx =x ...x forα=(α ,...,α )∈1 n 1 n 1 n
nN . Assume all considered rings to be integral domains with1.0
1.1 Janet’s algorithm overZ
To deal with polynomial systems, we use a device which constructs bases of ideals in polynomial rings.
For our purposes, we compute Janet bases, which are a special kind of Gröbner bases. This method
was presented by the French mathematician Maurice Janet (for the case of linear partial differential
equations) in the early twenties of the last century, but for unknown reasons this work remained ignored
for more then sixty years, until it was re discovered by Jean François Pommaret. In 1965 the Austrian
mathematician Bruno Buchberger, unaware of the idea of Janet, introduced an alternative method for
computing bases of polynomial ideals. His approach has become very successful and Gröbner bases are
nowadays a well known and a standard tool in theory of modules over polynomial rings.
The two approaches mentioned above are essentially the same. The significant difference between
computing Janet and Gröbner bases is the philosophy of reduction: Contrary to the standard Gröbner
bases algorithm, which allows many ways to reduce a polynomial with respect to the given polynomial
system, the Janet algorithm determines a unique possible reduction (and thus, as in the case of any
Gröbner basis, also a unique normal form of an element with respect to the system). The elements that
9

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin