Arithmetic in group extensions using a partial automation
Date
2010
Authors
Ziliak, Ellen, author
Hulpke, Alexander, advisor
Achter, Jeff, committee member
Betten, Anton, committee member
McConnell, Ross, committee member
Journal Title
Journal ISSN
Volume Title
Abstract
The purpose of this paper is to describe the structure of an extension group G which has a normal subgroup K and a quotient group Q = G/K . To describe the structure of G concretely, we want to be able to do arithmetic in G based on the arithmetic done in both the normal subgroup K and the quotient group Q. We will begin by looking at the 2-cohomology group which is the standard approach for working on this problem. This will lead us to questions concerning storage which we would like to reduce. Therefore we will consider the case where our groups arc finitely presented and see how storage may be reduced. During this reduction we will see that it will be necessary to be able to rewrite words in a free group as a product of generators of the normal subgroup K. We begin by looking at current approaches to this problem, which requires computing an (augmented) coset table. If we will let Q be a finite group for which we also have a presentation < S\R >, (i.c. Q = F/N with F —< S > and N the normal closure of R in F). We assume that Q does not have a confluent rewriting system. We want to rewrite a word in S, representing the identity in Q as a product of conjugates in R. Such rewriting can be done using an (augmented) coset table for N in F which can be visualized in a graph by a coset automaton, also called the full Cayley Graph. Tracing in the graph through words in F will allow us to rewrite these words as a product of generators of N. The difficulty that arises in this approach lies in storing and constructing the augmented coset table. Instead we will construct an object called a partial automaton which is a subgraph of the coset automaton. The partial automaton will have the property that it contains a loop for every relator in R. We will first show that this graph can be used to reconstruct the coset automaton, which means it contains the same information as the coset automaton even though it is much smaller. Our next step will be to use the partial automaton to rewrite words in N as a product of conjugates in R. Since the partial automaton is much smaller than the coset automaton, and it does not contain doubly labeled edges as an augmented coset automaton would it require substantially less memory to store. A word in N is represented by a loop in the coset automaton, therefore if we wish to rewrite this word as a product of conjugates of relators, we essentially want to describe this larger loop as a product of smaller loops. Where we will restrict our smaller loops to be loops in the partial automaton. To do this rewriting we place the partial automaton locally at different states in the coset automaton until we cover the entire loop. By placing the partial automaton at different states in the graph we will then the conjugate of relators. Unfortunately we cannot just place the partial automaton arbitrarily at different states, because we would have many different choices of the conjugates of relators we could choose. Instead we must use one further tool, which is the fact that our normal subgroup N is itself a free group. Therefore N has a free generating set, where the generators of N are conjugates of relators. With this generating set we can rewrite words in N uniquely as a product of the generators. We will therefore, use the partial automaton to compute the generators of the free generating set for N and then use these generators to rewrite our word in N as a product of conjugate of relators. By using the partial automaton to do this rewriting we can quickly do rewriting in much larger examples. This algorithm has been implemented in GAP and to suggest the improvement we rewrote several words in the group PSp^ which is a group of order 1,451, 520. The partial automaton had 145 states and after some initial set up which will be described in the paper the run time for this rewriting took less than a half a second per word.
Description
Covers not scanned.
Print version deaccessioned 2022.
Print version deaccessioned 2022.
Rights Access
Subject
Finite groups
Group extensions (Mathematics)
Cayley graphs