In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, computational group theory is the study of
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
s by means of computers. It is concerned
with designing and analysing
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s and
data structure
In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
s to compute information about groups. The subject
has attracted interest because for many interesting groups
(including most of the
sporadic groups
In the mathematical classification of finite simple groups, there are a number of Group (mathematics), groups which do not fit into any infinite family. These are called the sporadic simple groups, or the sporadic finite groups, or just the spora ...
) it is impractical
to perform calculations by hand.
Important algorithms in computational group theory include:
* the
Schreier–Sims algorithm
The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, determine whether a given permutati ...
for finding the
order
Order, ORDER or Orders may refer to:
* A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
...
of a
permutation group
In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to ...
* the
Todd–Coxeter algorithm
In group theory, the Todd–Coxeter algorithm, created by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group ''G'' by generators and relations and a subgroup ''H'' ...
and
Knuth–Bendix algorithm for
coset enumeration In mathematics, coset enumeration is the problem of counting the cosets of a subgroup ''H'' of a group ''G'' given in terms of a presentation. As a by-product, one obtains a permutation representation for ''G'' on the cosets of ''H''. If ''H'' has a ...
* the
product-replacement algorithm for finding random elements of a group
Two important
computer algebra system
A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...
s (CAS) used for group theory are
GAP and
Magma
Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma (sometimes colloquially but incorrectly referred to as ''lava'') is found beneath the surface of the Earth, and evidence of magmatism has also ...
. Historically, other systems such as CAS (for
character theory
In mathematics, more specifically in group theory, the character of a group representation is a function on the group that associates to each group element the trace of the corresponding matrix. The character carries the essential information a ...
) and
Cayley (a predecessor of Magma) were important.
Some achievements of the field include:
* complete enumeration of
all finite groups of order less than 2000
* computation of
representations for all the
sporadic groups
In the mathematical classification of finite simple groups, there are a number of Group (mathematics), groups which do not fit into any infinite family. These are called the sporadic simple groups, or the sporadic finite groups, or just the spora ...
See also
*
Black box group
References
*
surveyof the subject by Ákos Seress from
Ohio State University
The Ohio State University (Ohio State or OSU) is a public university, public Land-grant university, land-grant research university in Columbus, Ohio, United States. A member of the University System of Ohio, it was founded in 1870. It is one ...
, expanded from an article that appeared in the
Notices of the American Mathematical Society
''Notices of the American Mathematical Society'' is the membership journal of the American Mathematical Society (AMS), published monthly except for the combined June/July issue. The first volume was published in 1953. Each issue of the magazine ...
is available online. There is also
surveyby
Charles Sims from
Rutgers University
Rutgers University ( ), officially Rutgers, The State University of New Jersey, is a Public university, public land-grant research university consisting of three campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's C ...
and a
older surveyby Joachim Neubüser from
RWTH Aachen
RWTH Aachen University (), in German ''Rheinisch-Westfälische Technische Hochschule Aachen'', is a German public research university located in Aachen, North Rhine-Westphalia, Germany. With more than 47,000 students enrolled in 144 study prog ...
.
There are three books covering various parts of the subject:
* Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, "Handbook of computational group theory", Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, Florida, 2005.
*
Charles C. Sims, "Computation with Finitely-presented Groups", Encyclopedia of Mathematics and its Applications, vol 48,
Cambridge University Press
Cambridge University Press was the university press of the University of Cambridge. Granted a letters patent by King Henry VIII in 1534, it was the oldest university press in the world. Cambridge University Press merged with Cambridge Assessme ...
, Cambridge, 1994.
* Ákos Seress, "Permutation group algorithms", Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. {{ISBN, 0-521-66103-X.
Computational fields of study