% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@PHDTHESIS{Rober:1018873,
author = {Rober, Friedrich},
othercontributors = {Niemeyer, Alice Catherine and O'Brien, Eamonn},
title = {{W}reath product decompositions},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
publisher = {RWTH Aachen University},
reportid = {RWTH-2025-08026},
pages = {1 Online-Ressource : Illustrationen},
year = {2025},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University; Dissertation, RWTH Aachen University, 2025},
abstract = {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.},
cin = {115320 / 110000},
ddc = {510},
cid = {$I:(DE-82)115320_20140620$ / $I:(DE-82)110000_20140620$},
typ = {PUB:(DE-HGF)11},
doi = {10.18154/RWTH-2025-08026},
url = {https://publications.rwth-aachen.de/record/1018873},
}
guest ::