In this thesis, expanded groups and the Subpower Intersection Problem for direct powers of groups will be discussed and then implemented in GAP.
The first chapter is an introduction to universal algebra and GAP. Algebraic structures, especially groups, expanded groups, direct powers and some conceptsare defined as belonging to algebraic structures. Then an introduction to the programming language GAP, which was developed for computations in algebra, is given and GAP is used for proving a theorem about polynomial functions on groups of order 8.
In the second chapter the theory of expanded groups, especially how to find the universe of an expanded group given by generators is explored. After that a data structure for computing with expanded groups in GAP and use this data structure for proving that not every normal subgroup of an expanded group is also an ideal and for counting the binary polynomials of a concrete expanded group is develeoped.
The last chapter is about the Subpower Intersection Problem for direct powers of groups. First, the concept of strong generators for direct powers of groups is dintroduced and then it is discused how to find strong generators of the intersection of direct powers of groups. Finally, the algorithms for solving the problem in GAP and discuss compatible functions asan application of the Subpower Intersection Problem are implemented.
Contents
1 Universal Algebra and GAP
1.1 Algebras
1.2 GAP
1.3 An Example Combining Theory and GAP
2 Expanded Groups
2.1 Generators of Expanded Groups
2.2 Functions with Finite Degree
2.3 Direct Powers and Ideals of Expanded Groups
2.4 A Data Structure for Expanded Groups in GAP
2.5 Computing in Expanded Groups with GAP
3 Subpower Intersection Problem
3.1 Strong Generators of Groups
3.2 The Subpower Intersection Problem
3.3 Implementation in GAP
3.4 Counting Compatible Functions
Research Objectives and Core Topics
This master thesis explores the mathematical theory of expanded groups and develops algorithms to solve the Subpower Intersection Problem for direct powers of groups, with a focus on practical implementation within the GAP computer algebra system.
- Theoretical foundation of universal algebra and expanded groups.
- Development of robust data structures for expanded groups in GAP.
- Implementation and analysis of algorithms for strong generators.
- Solving the Subpower Intersection Problem using algorithmic approach.
- Practical application in counting compatible functions on groups.
Excerpt from the Thesis
1.3 An Example Combining Theory and GAP
As we saw in the last section, a polynomial function is a composition of projection functions and constant functions. Consider a group G = ⟨G, ·, −1 , 1⟩. We want to compute all binary polynomial functions f of G and check whether one of them fulfills the group properties:
(G1) ∀x, y, z ∈ G: f(x, f(y, z)) = f(f(x, y), z) (associativity)
(G2) ∀x ∈ G: f(1, x) = f(x, 1) = 1 (neutral element)
(G3) ∀x ∈ G&exists;y ∈ G: f(x, y) = 1 (inverse element)
Clearly the original group operation · and its opposite (x, y) → y·x are group operations in Pol2(G). We are interested in whether there are any more. In this example we will concentrate on the groups of order 8 up to isomorphism which are: (i) ℤ8, +, −, 0; (ii) ℤ4 × ℤ2, +, −, 0; (iii) ℤ2 × ℤ2 × ℤ2, +, −, 0; (iv) D8, the dihedral group with 8 elements; (v) Q8, the quaternion group with 8 elements. For more information about those groups see [11] or every other good book about group theory. While D8 and Q8 are not abelian, the other three groups are abelian groups. We also will check if the polynomials are commutative, i.e. (G4) ∀x, y ∈ G: f(x, y) = f(y, x).
Summary of Chapters
1 Universal Algebra and GAP: This chapter introduces fundamental concepts of universal algebra and provides an introduction to the GAP programming language.
2 Expanded Groups: This section details the theory of expanded groups, defines generators for them, and implements a dedicated data structure within GAP for computational purposes.
3 Subpower Intersection Problem: The final chapter addresses the Subpower Intersection Problem by introducing strong generators and providing a concrete implementation for solving these problems in GAP.
Keywords
Universal Algebra, Expanded Groups, Group Theory, GAP, Subpower Intersection Problem, Strong Generators, Polynomial Functions, Direct Products, Computational Algebra, Permutation Groups, Algorithm Implementation, Subpower Membership Problem, Compatible Functions, Normal Subgroups.
Frequently Asked Questions
What is the primary focus of this work?
The thesis focuses on the computational aspects of expanded groups and direct powers of groups, specifically aiming to solve the Subpower Intersection Problem using the GAP system.
What are the main thematic areas covered?
The work covers universal algebra, the theory of expanded groups, algorithmic implementation of strong generators, and applications like the Subpower Membership and Intersection Problems.
What is the core research objective?
The primary goal is to implement and analyze efficient algorithms for handling direct powers of expanded groups and their subpower properties within the GAP software environment.
Which scientific methodology is employed?
The methodology combines mathematical proof for algebraic theorems with algorithmic implementation and empirical verification through computational experiments in GAP.
What topics are discussed in the main part of the thesis?
The main part covers the theory of expanded groups, the construction of specific data structures for these objects, and the development of algorithms for strong generators and the intersection of subgroups.
How would you characterize this thesis with keywords?
Key terms include Universal Algebra, Expanded Groups, GAP, Subpower Intersection Problem, and Computational Algebra.
How is the Subpower Intersection Problem addressed?
The problem is addressed by constructing transversals (strong generators) using specialized sifting algorithms and closing these sets under product operations.
Why are expanded groups important in this research?
Expanded groups serve as the primary mathematical structure for studying more complex properties like polynomial equivalence and ideal structures beyond simple group operations.
What is the significance of the implemented GAP functions?
They enable the automated calculation of properties that are otherwise too complex to compute by hand, such as determining all binary polynomial functions for groups of order 8.
- Quote paper
- Stephan Zweckinger (Author), 2013, Computing in Direct Powers of Expanded Groups. A Discussion of the Subpower Intersection Problem, Munich, GRIN Verlag, https://www.grin.com/document/469947
