Centre for the Mathematics of Symmetry and Computation

Computational Group Theory

Researchers


Further information

An Introduction to Computational Group Theory, by Ákos Seress, published in Notices - July 1997, Volume 44, Number 6. It is available in PDF format [22KB] from the Notices website.

 

Mathematically, symmetry is described by groups.

Traditionally, groups and their properties have been investigated either algebraically or analytically. However, with the advance of modern computers, the exciting possibility of investigating properties of groups on a computer has arisen.

Long before computers came into existence, mathematicians considered the problem whether certain questions regarding groups can be answered by a repeatable sequence of steps, called an algorithm. As early as 1911, Dehn posed a question about groups described by presentations and it was possible to prove that these questions were not solvable by a deterministic algorithm.

Nevertheless group theorists already worked on group theoretic algorithms during the 1940s and implemented programs on computers in the 1950s. During the 1960s and 1970s group theoretic algorithms assisted the Classification of Finite Simple Groups.

Neubüser: An Invitation to Computational Group Theory provides a a summary of the history of Computational Group Theory.

Group Theory

Today, Computational Group Theory is a thriving branch of Group Theory. The subject is concerned with designing algorithms to answer questions about groups to prove the correctness of these algorithms and to determine the cost of running such an algorithm on a group.

Modern algorithms and high speed computers allow mathematicians to investigate very large groups on a computer. In particular, the computer algebra systems GAP and Magma, provide access to most of the state of the art functionality for groups.

Much progress in recent years has been made on designing algorithms for matrix groups. These algorithms take as input a small number of matrices and answer questions about the group defined by these matrices. In general, answering questions about such groups is difficult.

Even two 10 x 10 matrices with entries modulo 5 can have nearly 6.1069 elements.

In 1989, Joachim Neubüser posed the challenge to the computational group theory community: Given a group of matrices defined over a finite field, can we decide whether the group contains the group of all invertible matrices of the same dimension over the same field that have determinant 1?

For example, given the two 3 x 3 matrices with entries modulo 5:

g=(3 4 4, 3 4 2, 1 0 1)
and
h=(0 0 4, 1 3 4, 1 4 4)

do g and h generate a group which contains all invertible 3x3 matrices with entries modulo 5 that have determinant 1?

Questions such as these can now be answered by efficient algorithms on a computer for groups of matrices of dimension up to several hundred.

 

Centre for the Mathematics of Symmetry and Computation

This Page

Last updated:
Thursday, 14 May, 2015 8:05 PM

http://www.cmsc.uwa.edu.au/717111