Constructive recognition of finite classical groups with stingray elements

Rademacher, Daniel; Niemeyer, Alice Catherine; Praeger, Cheryl E.; Horn, Max

doi:10.18154/RWTH-2024-09688

Constructive recognition of finite classical groups with stingray elements = Konstruktive Erkennung endlicher klassischer Gruppen mit Stingray-Elementen

Rademacher, Daniel^RWTH*

2024

Verantwortlichkeitsangabevorgelegt von Daniel Rademacher, M.Sc.

ImpressumAachen : RWTH Aachen University 2024

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2024

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Niemeyer, Alice Catherine (Thesis advisor)^RWTH* ; Horn, Max (Thesis advisor)^RWTH* ; Praeger, Cheryl E. (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2024-09-25

Online
DOI: 10.18154/RWTH-2024-09688
URL: http://publications.rwth-aachen.de/record/995067/files/995067.pdf

Einrichtungen

Projekte

Inhaltliche Beschreibung (Schlagwörter)
algorithms in group theory (frei) ; computational group theory (frei) ; constructive recognition (frei) ; finite classical groups (frei) ; matrix groups (frei) ; stingray elements (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
In 1988 stellte Joachim Neubüser in Oberwolfach eine Frage zu Matrixgruppen, die 1992 von Peter Neumann und Cheryl E. Praeger beantwortet wurde. Dies initiierte ein internationales Forschungsprojekt, das sogenannte Matrixgruppenerkennungsprojekt, im Bereich der algorithmischen Gruppentheorie mit dem Ziel, grundlegende Fragen über beliebige Matrixgruppen über endlichen Körpern zu beantworten. Eine mögliche Methode ist eine Datenstruktur namens composition tree. In diesem Ansatz werden Berechnungen einer großen Matrixgruppe in Berechnungen für kleinere Matrixgruppen zerlegt, bis dieser Prozess nicht mehr wiederholt werden kann. Die verbleibenden Gruppen in den Blättern sind die endlichen (quasi-)einfachen Gruppen, zu denen die klassischen Gruppen gehören. Daher sind effiziente Algorithmen zur Behandlung von klassischen Gruppen für die Gesamtleistung des composition tree unerlässlich. Ein grundlegendes Ziel besteht darin, einen effizienten Algorithmus zur konstruktiven Erkennung dieser Gruppen zu entwickeln. Diese Arbeit präsentiert einen neuen Algorithmus zur konstruktiven Erkennung von klassischen Gruppen in ihren natürlichen Darstellungen, aufbauend auf vorläufigen Konzepten von Ákos Seress und Max Neunhöffer für spezielle lineare Gruppen. Der Algorithmus besteht aus drei Teilalgorithmen: GoingDown Algorithmus: Steigt rekursiv von der Eingabegruppe $G$ zu einer Untergruppe $U$ ab, die zu einer "Basisfall-gruppe'' isomorph ist, durch die Verwendung von "stingray duos'' und erreicht eine solche Gruppe in deutlich weniger Schritten als traditionelle Methoden. BaseCase Algorithmus: Nutzt eine effiziente Methode zur konstruktiven Erkennung der Basisfall-gruppe $U$, was einen Startpunkt für die Berechnung der Standardgeneratoren von $G$ bildet. GoingUp Algorithmus: Benutzt die Standardgeneratoren von der Untergruppe $U$ um Standardgeneratoren der ursprüngliche Gruppe $G$ zu berechnen, wozu ein neuer Ansatz verwendet wird, welcher Standardgeneratoren für Zwischenuntergruppen berechnet. Diese Forschung trägt zum breiteren Ziel der Verbesserung von Methoden zur Matrixgruppenerkennung bei, wobei ein besonderer Schwerpunkt auf klassischen Gruppen liegt. Sie präsentiert effiziente Algorithmen, die die Leistung der Methode des composition tree verbessern.

In 1988 Joachim Neubüser posed a matrix group related question in Oberwolfach which was answered by Peter Neumann and Cheryl E. Praeger in 1992. This initiated an international research effort, the matrix group recognition project, within the area of computational group theory with the aim of answering fundamental questions about arbitrary matrix groups over finite fields. One possible method is a data structure called composition tree. In this approach, computations of a large matrix group are decomposed into computations for smaller matrix groups until this process cannot be repeated anymore. The remaining leaf groups are the finite (quasi-)simple groups, which include the classical groups. Therefore, efficient algorithms to deal with classical groups are essential for the overall performance of the composition tree. One elementary aim is to develop an efficient algorithm for the constructive recognition of these groups. This thesis presents a novel algorithm for constructively recognising classical groups within their natural representations, building upon preliminary concepts from Ákos Seress and Max Neunhöffer for special linear groups. The algorithm consists of three subalgorithms: GoingDown algorithm: Recursively descends from the input group $G$ to a subgroup $U$ isomorphic to a "base case group'' using stingray duos and reaching such a group in significantly fewer steps than traditional methods. BaseCase algorithm: Utilises an efficient method for constructively recognising the base case group $U$ forming a starting point for the computation of standard generators of $G$. GoingUp Algorithm: Extends standard generators from the subgroup $U$ to the original group $G$, employing an original approach to compute generators for intermediate subgroups. This research contributes to the broader goal of enhancing computational methods for matrix group recognition, with a particular focus on classical groups. It presents efficient algorithms that improve the performance of the composition tree method.

OpenAccess:
PDF
(additional files)