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

Sujets

• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2009
• Nombre de lectures: 11
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

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