Implementation of the Todd-Coxeter Algorithm to Finitely Presented Groups

Abstract

This work presents the notion of free groups and the definition of a group using generators and relations. We use the Todd-Coxeter Algorithm in order to solve the coset enumeration problem for the finitely presented groups: $D_4,\, A_4,\, A_5,\, S_3,\, S_4,\, S_5,\, PSL_2(7),\, PSL_2(9)$. Then we use these presentations in order to prove the exceptional isomorphisms $A_5\cong PSL_2(5) \cong SL_2(4)$, $PSL_2(9)\cong A_6$ and $SL_3(2)\cong PSL_2(7)$.

Popular Abstract

Symmetry is something humans comprehended thousands of years ago. It appears in all aspects of our lives; in art, architecture, poetry, carpets and rugs, music and nature. The human eye is attracted to symmetry and objects that look symmetric. The perfect mirror image and the order, we cannot resist it.

If we would like to take the notion of symmetry, and define it mathematically, how can we do that? It was the ingenuity of the French mathematician Évariste Galois, who invented a language which is needed for showing that a polynomial of degree five and above does not possess a "nice'' solution using the mathematical operations we know from school (addition, subtraction, multiplication, division, and taking the $n$th root). The new language that emerged is what we have today as "group theory''. In some sense, Galois studied the "symmetry of the equations", and the reason such a solution is not possible is because the equations have "the wrong kind of symmetry" as Ian Stewart says in \cite{stewart2008why}. It is necessary to say that mathematicians before Galois had already got results in group theory, but Galois was the one to understand the structure and to use it for his attack on the problem of polynomial solutions. As Israel Herstein writes in \cite{herstein1964topics}:
\begin{quotation}
Very often in mathematics the crucial problem is to recognize and to discover what are the relevant concepts; once this is accomplished the job may be more than half done.
\end{quotation}

Group theory is the language of mathematics to describe and measure the notion of symmetry. We all have the understanding of what symmetry is, but a concrete, down to earth, way of describing it is:
\begin{quotation}
Symmetry is not a number or a shape, it is a \textit{transformation} - a way to move an object. If the object looks the same after being transformed, then the transformation concerned is a symmetry.\\
\cite{stewart2008why}
\end{quotation}
Think about a square. Now rotate the square 90 degrees counterclockwise. Do it again. Is there any visual difference between what we have started with and what we finished with? Hopefully you answer this questions with "no". The rotation of 90 degrees counterclockwise you did is called a transformation. The object looks the same after the transformation. So the transformation concerned is a symmetry. In a similar way, we can draw an imaginary horizontal line right in the middle of the square. If we take the upper half of the square and the lower half of the square and switch their places, we will get the same figure of a square. This is again a symmetry.

The group structure in mathematics allows us to study objects in which symmetry is built into them. In some sense, this is the simplest structure we have. We take a set of objects (does not need to be numbers or functions. It can be anything, including puppies and kittens), and allowing one operation on the elements of the set, such that they satisfy some axioms. This is very simple and yields a beautiful theory.

It turns out that group theory has a deep connection with other physical sciences. For example, in chemistry, symmetry is used in order to classify molecules by their shape. Moreover, chemists use symmetry in studying crystals (See Dan Shechtman, awarded the 2011 Nobel Prize in Chemistry). Physicists also use group theory, for example, in quantum mechanics. Biologists use group theory in molecular systems biology.

While there is a formal mathematical definition for the group structure, usually it is the case where we need to show that a certain structure is a group. However, in some cases we would like to take an arbitrary set of objects and from them \textbf{to build} a group in which some elements may or may not satisfy conditions we dictate. So how do we do it? Here comes the phrase "presentation of a group". Presentation of a group is exactly the way to solve this problem. We take elements that we want to generate (to "create") the group and adding (if we want) some prescribed conditions on these elements. Of course, it requires more details to build it which can be found in this work.

• author: Reed, Tomas
• supervisor: Arne Meurman
• organization: Mathematics (Faculty of Sciences)
• course: MATK01 20172
• year: 2018
• type: M2 - Bachelor Degree
• subject: Mathematics and Statistics
• keywords: Group Theory, Free Groups, Finitely Presented Groups, Todd-Coxeter Algorithm, Combinatorial Group Theory
• publication/series: Bachelor's Theses in Mathematical Sciences
• report number: LUNFMA-4069-2018
• ISSN: 1654-6229
• other publication id: 2018:K6
• language: English
• id: 8936517
• date added to LUP: 2018-02-27 14:53:25
• date last changed: 2018-02-27 14:53:25