h1

TY  - THES
AU  - Rober, Friedrich
TI  - Wreath product decompositions
PB  - RWTH Aachen University
VL  - Dissertation
CY  - Aachen
M1  - RWTH-2025-08026
SP  - 1 Online-Ressource : Illustrationen
PY  - 2025
N1  - Veröffentlicht auf dem Publikationsserver der RWTH Aachen University
N1  - Dissertation, RWTH Aachen University, 2025
AB  - 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.
LB  - PUB:(DE-HGF)11
DO  - DOI:10.18154/RWTH-2025-08026
UR  - https://publications.rwth-aachen.de/record/1018873
ER  -