Wreath product decompositions

Rober, Friedrich; Niemeyer, Alice Catherine; O'Brien, Eamonn

doi:44695

Wreath product decompositions

Rober, Friedrich^RWTH*

2025

Verantwortlichkeitsangabevorgelegt von Friedrich Rober, M. Sc.

ImpressumAachen : RWTH Aachen University 2025

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2025

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Niemeyer, Alice Catherine (Thesis advisor)^RWTH* ; O'Brien, Eamonn (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2025-07-24

Online
DOI: 10.18154/RWTH-2025-08026
URL: https://publications.rwth-aachen.de/record/1018873/files/1018873.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
2-part order (frei) ; Computergruppentheorie (frei) ; Kranzprodukte (frei) ; Monte-Carlo (frei) ; Proportion von Prä-Involutionen (frei) ; algorithmische Gruppentheorie (frei) ; alternating groups (frei) ; alternierende Gruppen (frei) ; black box (frei) ; classical groups (frei) ; computational group theory (frei) ; constructive recognition (frei) ; klassische Gruppen (frei) ; konstruktive Erkennung (frei) ; primitive Gruppen vom Typ (PA) (frei) ; primitive groups of type (PA) (frei) ; product action (frei) ; proportion of pre-involutions (frei) ; wreath products (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Diese Arbeit ist Teil eines aktiven Forschungsbereichs, der als Computergruppentheorie bekannt ist. Dieses relativ junge Forschungsgebiet hat eine umfassende Bibliothek mit effizienten Algorithmen für die Arbeit mit Gruppen auf einem Computer erzeugt. Für einige Probleme der computergestützten Gruppentheorie sind jedoch keine polynomiallen Algorithmen für endliche Gruppen bekannt, und sie können für unendliche Gruppen unentscheidbar werden. Daher wird es notwendig, bei der Entwicklung von Algorithmen Randomisierung zu verwenden. Die in dieser Arbeit vorgestellten randomisierten Algorithmen sind Monte-Carlo-Algorithmen, die zufällige Elemente der Eingabegruppe verwenden. Die Ausgabe eines Monte-Carlo-Algorithmus kann mit einer kleinen Fehlerwahrscheinlichkeit falsch sein, die vom Benutzer bestimmt wird. Eine abstrakte Gruppe kann auf verschiedene Weise auf einem Computer dargestellt werden, und die Komplexität der Probleme hängt von der gewählten Darstellung ab. Zwei der bekanntesten Darstellungen sind Permutations- und Matrixgruppen. Eine Black-Box-Gruppe ist ein theoretisches Modell, mit dem alle Darstellungen einer endlichen Gruppe gleichzeitig behandelt werden können. Algorithmen, die für Black-Box-Gruppen entwickelt werden, funktionieren auch für Gruppen in beliebigen Darstellungen. Unser Ziel ist es, Algorithmen für das folgende Problem zu entwickeln und zu untersuchen: Gegeben eine Black-Box-Gruppe G, die isomorph zu einer (Untergruppe eines) Kranzprodukts W = K ≀ H mit nicht-trivialer oberer Komponente ist, zerlege G explizit in seine Kranzprodukt-Komponenten. Nutze eine solche Zerlegung, um Probleme über G auf einfachere Probleme über die Komponenten K und H zu reduzieren. Unser erstes Hauptergebnis bezieht sich auf die Berechnung einer solchen Kranzprodukt- Zerlegung: Gegeben eine Black-Box-Gruppe G, berechne eine Einbettung φ : G → W in ein natürliches Kranzprodukt W = K ≀ H, in dem die Elemente komponentenweise kodiert sind. Sei A die Familie der nicht-abelschen einfachen Gruppen, die Alt(n) und PSL(d, q), PSU(d, q), PSp(2d, q) für q ungerade enthalten. Sei B die Familie, die die Gruppen in A, sowie zusätzlich Sym(n) mit n ≥ 5 und Aut(Alt(6)) enthält. Unter der Voraussetzung eines Orakels für die Erzeugung zufälliger Elemente, eines Orakels für das Bestimmen von Elementordnungen, und eines konstruktiven Erkennungsalgorithmus für die Gruppen in A, gibt es einen polynomiellen Monte-Carlo-Algorithmus zur Berechnung einer Kranzprodukt-Zerlegung einer Black-Box-Gruppe G isomorph zu einer Untergruppe U eines Kranzprodukts W = K ≀ Sym(m), wobei K ∈ B, Soc(U) = Soc(K)^m, und U durch Konjugation transitiv auf den Sockelfaktoren wirkt. Als Nebenprodukt der zugehörigen Wahrscheinlichkeitsanalyse präsentieren wir unser zweites Hauptergebnis bezüglich der Proportionen von Gruppenelementen. Für alle T ∈ A ist der Anteil der Elemente in T gerader Ordnung von unten durch eine explizite Konstante beschränkt. Außerdem ist für alle T ∈ A der Anteil der Elemente in T × T , deren Komponenten unterschiedliche 2-Ordnungen haben, ebenfalls von unten her durch eine explizite Konstante beschränkt. Die Hauptergebnisse sind durch Permutationsgruppen motiviert, und verwenden eine Methodik die durch Algorithmen für Matrixgruppen inspiriert sind. Für viele Probleme in endlichen Permutationsgruppen sind effiziente Monte-Carlo-Algorithmen mit nahezu-linearer Laufzeit für Gruppen mit kleiner Basis bekannt. Gruppen mit großer Basis stellen jedoch eine Herausforderung für einen Computer dar. Die primitiven Gruppen mit großer Basis können als Untergruppen bestimmter Kranzprodukte beschrieben werden, die in Produktwirkung auf l^m Punkte gegeben sind. Eine Strategie für den Umgang mit solchen Gruppen besteht darin, die Gruppe in ein Kranzprodukt der imprimitiven Wirkung auf (l · m) Punkten zu übersetzen. Law, Niemeyer, Praeger und Seress entwickelten 2006 den Jellyfish-Algorithmus, einen einseitigen Monte-Carlo-Algorithmus, der eine gegebene primitive Permutationsgruppe mit großer Basis in eine isomorphe Gruppe mit imprimitiver Wirkung übersetzt. Unser drittes Hauptergebnis ist ein analoger Algorithmus, der für eine größere Klasse von Kranzprodukten funktioniert und Black-Box-Gruppen als Eingabe akzeptiert. Unsere Methoden sind inspiriert von dem Projekt zur Erkennung von Matrixgruppen, das einen Rahmen für das Rechnen mit großen Matrixgruppen bietet. Mit Hilfe einer Kranzprodukt-Zerlegung reduzieren wir das Problem der konstruktiven Erkennung bestimmter Kranzprodukte auf das Problem der konstruktiven Erkennung ihrer Komponenten. Insbesondere für die primitiven Gruppen vom Typ (PA) liefert unser Ergebnis einen neuen Ansatz, der den Jellyfish-Algorithmus verallgemeinert. Unser viertes Hauptergebnis nutzt eine Kranzprodukt-Zerlegung aus. Wir parametrisieren explizit die Konjugationsklassen und Zentralisatoren für Kranzprodukte, bei denen die Basisgruppe eine beliebige Gruppe ist und die obere Komponente treu auf einer endlichen Menge operiert. Die Parametrisierungen sind inspiriert von Ideen, die ursprünglich von Ore und Specht entwickelt wurden. Unsere Ergebnisse führen zu effizienten Algorithmen, um konjugierende Elemente, Konjugationsklassen und Zentralisatoren in endlichen Kranzprodukten zu berechnen. Der allgemeine Ansatz besteht darin, diese Probleme für ein Kranzprodukt W = K ≀ H auf verwandte Probleme in den Komponenten K und H zu reduzieren. Die Algorithmen sind im GAP-Paket WPE implementiert.

This work forms part of an active research field known as computational group theory. This relatively young area of research has established a comprehensive library of efficient algorithms for working with groups on a computer. But some problems in computational group theory have no known polynomial time solutions for finite groups and may become intractable for infinite groups. Therefore, it becomes necessary to use randomisation when designing algorithms. The randomised algorithms presented in this thesis are Monte-Carlo which employ random elements of the input group. The output of a Monte-Carlo algorithm is allowed to be incorrect with a small error probability specified by the user. An abstract group can be represented in various ways on a computer, and the complexity of computational problems depends on the chosen representation. Two of the most prominent representations are as a permutation or a matrix group. A black box group is a theoretical model to deal with all representations of a finite group simultaneously. In particular, algorithms developed for black box groups work on groups in arbitrary representations. Our goal is to develop and investigate algorithms for the following problem: Given a black box group G isomorphic to a (subgroup of a) wreath product W = K ≀ H with non-trivial top component, decompose G explicitly into its wreath product components. Exploit such a decomposition to reduce computational problems about G to easier problems about the components K and H. Our first main result is related to computing such a wreath product decomposition: given a black box group G, compute an embedding φ : G → W into a natural wreath product W = K ≀ H where elements are encoded component-wise. Let A be the collection of non-abelian simple groups containing Alt(n) and PSL(d, q), PSU(d, q), PSp(2d, q) for q odd. Let B be the collection consisting of the groups in T, and additionally the symmetric groups Sym(n) with n ≥ 5 and Aut(Alt(6)). Subject to a random element oracle, an element order oracle, and a constructive recognition algorithm for the groups in A, there exists a polynomial time Monte-Carlo algorithm to compute a wreath product decomposition of a black box group G isomorphic to a subgroup U of a wreath product W = K ≀ Sym(m), where K ∈ B, Soc(U) = Soc(K)^m, and U acts transitively on the socle factors by conjugation. As a by-product of the associated probability analysis, we present our second main result concerning proportions of group elements. For all T ∈ A, the proportion of elements of T of even order is bounded from below by an explicit constant. Moreover, for all T ∈ A, the proportion of elements of T × T whose components have different 2-part orders is also bounded from below by an explicit constant. The main results are motivated by permutation groups, but draw inspiration from computational methods for matrix groups. For many problems in finite permutation groups, efficient Monte-Carlo algorithms are known with nearly-linear runtime for small-base groups. However, large-base groups pose a challenge for a computer. The large-base primitive groups can be described as subgroups of certain wreath products given in product action on l^m points. A strategy to deal with such groups is to translate the group into a wreath product of imprimitive action on (l · m) points. Law, Niemeyer, Praeger and Seress developed in 2006 the jellyfish algorithm, a truth-biased Monte-Carlo algorithm that, given as input a large-base primitive permutation group G, rewrites G in its imprimitive action. Our third main result is an analogous algorithm that works for a larger class of wreath products and accepts black box groups as input. Our methods draw inspiration from the matrix group recognition project, which provides a framework for computing with large matrix groups. Using a wreath product decomposition, we reduce the problem of recognising certain wreath products constructively to the task of recognising its components constructively. In particular, for the primitive groups of type (PA) our result yields a new approach that generalises the jellyfish algorithm. Our fourth main result exploits a wreath product decomposition. We explicitly parametrise the conjugacy classes and centralisers for wreath products where the base group is any group and the top group acts faithfully on a finite set. The parametrisations are inspired by ideas originally developed by Ore and Specht. Our results yield efficient algorithms to find conjugating elements, conjugacy classes, and centralisers in finite wreath products. The general approach is to reduce these problems for a wreath product W = K ≀ H to related problems in the components K and H. The algorithms are implemented in the GAP package WPE.

OpenAccess:
PDF
(additional files)