Home Page of Brett Witty Mathematics PhD

I worked on my PhD in mathematics between February 2003 and September 2006. I was awarded the PhD title on 13th June 2007.

The title of my thesis was "Enumeration of groups of prime-power order", supervised by Prof. Mike F Newman.

For the last hundred years or so, group theorists have been trying to count finite groups of a given size. One method of doing this is fixing your size, generate all the groups of that size (by some taxonomy) and then count how many you have. This can be aided by computers, but soon enough it is too difficult to get results in a reasonable time. The other approach to counting groups of a given size is to use nonconstructive methods. To get a count without creating the groups is called enumeration. To simplify things we often just consider trying to count finite p-groups (that is, groups of prime-power order).

There have been some results of the form "the number of groups of order pn for a particular fixed n and variable p is a function f(n;p)". Here's what's known in this situation:

Number of p-groups for fixed p and variable n
n f(n;p) Notes
1 1 Cyclic groups of prime order. Cayley
2 2 Cyclic group or elementary abelian group. Cayley, Netto.
3 5 Three abelian groups and two nonabelian groups. Cole & Glover; Hölder; Young
4 14, if p=2 Hölder; Young
15, if p > 2
5 51, if p=2
67, if p=3
61 + 2p + 2 gcd(p-1,3) + gcd(p-1,4), otherwise Bagnera

Formulas exist for f(6;p) and f(7;p), which have a similar form to f(5;p).

The question is whether all f(n;p) have the structure of a polynomial in p with gcd-like coefficients (where f(n;p) may have a finite number of "exceptional primes" p' where f(n;p') is constant ). This structure is called "Polynomial on residue classes" (PORC). In 1960, Higman codified this idea and made the first steps towards this conjecture. Although Higman himself doesn't explicitly make the conjecture himself, it is known as Higman's PORC conjecture.

Higman's work on this question showed that a certain class of p-groups (those with exponent-p class two) did have PORC counting functions. He did not furnish any explicit counting functions. The philosophical underpinning of my thesis was that if Higman can prove such a thing, then we can use his proofs as a guide to construct an algorithm to produce explicit answers. I showed that there was an algorithm, and implemented the algorithm in GAP.

The main gist of the algorithm is to convert the p-group counting problem to a problem about counting fixed points under the action of particular matrices. This boils down to creating a classification of all the kinds of conjugacy classes of matrices of a certain structure (over a non-fixed finite field). Everything works (despite the variable size of the finite fields) and you end up with functions in the parameter p. Unfortunately the classification requires that you perform an inclusion-exclusion calculation on a large set of subsets. Even with various tricks, this is a prohibitively large calculation for reasonable values of n.

One method that we came up with was that we could do all the calculations (except the inclusion-exclusion) in reasonable time. We avoid the inclusion-exclusion calculation by interpolating a polynomial, where we know the degree of the polynomial from the information we already have. We can find the value of the polynomial at specific points by an algorithm of E.A. O'Brien found in Magma. Combining these calculations we can determine the PORC function for this particular case without requiring the expensive inclusion-exclusion calculation. We called this method the "hybrid method" as it combined the original algorithm with this interpolation approach.

The GAP code for this machinery is about 5,000 lines long and was not explicitly included in the final thesis.

You can obtain the original code (and my attempt to rewrite it in fast, parallel C++) via the GitHub repository.

My hyperlinked and indexed PhD thesis is available: [PDF]