Computational Group Theory (CGT) is the study of algorithms, theoretical as well as for concrete calculations, for computing with groups. Such algorithms find use both in group theory itself and in areas (such as combinatorics, topology or physics) that use groups to describe symmetries. Colorado State University at Fort Collins — the American center for the development of the system GAP —has an active research group in CGT. You can also find course notes for a recent graduate course here. |
Anton Betten
Justin Hughes (AH joint w. C.Peterson) Josh Maglione (JW) Corrine Previte (AH joint w. C.Peterson)
Soley Jonsdottir (now at DOD) Ellen Ziliak (now at Benedictine U.) Andreea Erciulescu |

Research in Fort Collins covers many aspects of CGT. The following list gives some areas on which work has been done recently or is continuing:

- Short Presentations for Groups of Lie Type. (Collaboration with A.SERESS).
- Development of Trivial-Fitting type algorithms for matrix groups.
- Classification of transitive permutation groups and subgroups of the symmetric group.
- Identification of Galois Groups.
- Improvements to group homomorphism and automorphism group calculations.
- Hybrid group representations and hybrid quotient algorithm. (Collaboration with B.EICK (Braunschweig, Germany) and A.NIEMEYER (Perth, Australia).
- User Support for GAP.
- Maintainance of a multitude of modules for GAP, e.g. permutation groups, finitely presented groups, hybrid algorithms for conjugacy classes and subgroups.
- Development of Teaching material and system improvements to enable use in the undergraduate curriculum.
- Constructive theory of discrete structures. Finite group actions. Orbit problems. Applications in Coding Theory, Design Theory and Finite Geometry.

Some relevant publications can be found here: (Betten), (Hulpke), (Wilson).

Recent and current student and thesis projects include:

- Solving Kakuro Puzzles (Undergraduate Research, A. ERCIULESCU,2010).
- Decomposing identity words as product of conjugates of relators (E. ZILIAK, PhD 2010).
- Induced actions on homology groups (J. HUGHES, MS2010), continuing work for PhD.
- Möbius functions for Symmetric Groups (K. MONKS, MS2008, PhD 2012)
- Algorithms for automorphism groups (S. JONSDOTTIR, MS2004, PhD2008)
- Construction of Polycyclic Generating systems (E. ZILIAK, MS2006).
- Improvements to discrete logarithm (Undergraduate Research S. GAGE, 2003).
- Shortest word expressions for elements (Undergraduate Research N. ROHRBACKER, 2004).

Computational Group Theory uses methods from Algebra and Combinatorics. If you are interested in doing research in this area, be it as undergraduate research, as masters thesis or as a doctoral thesis project, the following list gives some information on courses and prerequisites. Feel free to contact me if you have further questions.

**Graduates:** Typically incoming graduate students will start with the first-year courses on Algebra (M566/567) and Combinatorics (501/502) and continue with the second year courses (offered only every second year) on representation theory (M667). The courses on advanced combinatorics (M601/602), Algebraic Number Theory (M605A) and commutative algebra (M666) are strongly recommended.

If you did not have linear algebra as an undergraduate (or just a short course) you should also consider M560.

Relevant topics courses, offered if there is sufficient student interest (M676), include Computational Group theory and Computer Algebra.

**Prospective Students: **If you are not yet a student at Colorado State University you can find information about our programs on the departmental web pages.

Many projects involve explicit computation. For these, basic knowledge of some programming language is helpful, but is not a prerequisite.

**Potential Projects:** I maintain a list of GAP-related thesis and project topics, but this is not considered exclusive.

While the development of algorithms for groups is the majority of mathematical work (and requires knowledge of graduate level mathematics), the fact that algorithms end up in a distributed system provides a series of challenges that are much closer to computer science and engineering:

- Usability for Mathematicians is the main objective. Purely theoretical concepts are of secondary relevance.
- Having a
**system**is of substantial advantage over a collection of programs. More complicated algorithms only can be built (or even conceived of) if sufficient basic routines are available and usable. - Usability implies reasonable performance. This means that algorithms do not only have to be theoretically good (complexity) but also fast in practice.

A typical example is matrix multiplication over finite fields: For small dimensions the naive*O(n*algorithm performs much better than for example SCHÖNHAGE's^{3})*O(n*algorithm. The break even point seems to be around dimension 1000 over small finite fields. The (even better) algorithm by COOPERSTEIN with complexity^{2.7})*O(n*is not used in practice.^{2.3}) - Operations should incorporate knowledge about
**all**arguments to use the best algorithm possible. This rules out a simple object oriented approach, the approach used could be called “operation oriented”. - The type system should represent
**Mathematical knowledge**. This means that an objects type can change over its life time to incorporate information that has been found out over time. - While the language is interpreted, the implementation of fundamental routines in the system's kernel (in C) gives the convenience of an interpreted language (important for complicated mathematical algorithms) while still preserving much of the speed of a compiled language (“90% or the runtime is spent in 10% of the code'”).
- After years of speed increase with processors, algebraic and combinatorial algorithms now seriously hit the “bandwidth wall”: Issues such as cache access will have to be incorporated into core routines.
- Randomized algorithms might be faster, but care has to be taken of to verify the result.
**Results obtained with the system should have the same level of confidence as a refereed and published mathematical proof**.

`hulpke@math.colostate.edu`

),
January 30, 2014