# Is there order to the number of groups of different orders?

I was always struck by how uncharacteristically erratic the behavior of the following function is: $f: \mathbb{N} \rightarrow \mathbb{N}$ given by $f(n):=$ number of isomorphism classes of groups of order $n$.

I blame this on the introduction of the unnatural idea of looking at the size of the group. Why would we? The same is true in Algebraic Geometry: curves are nicer than surfaces for an arbitrary reason. Looking at the dimension introduces an unnatural agent in the mix.

My question is this:

What is the most "natural" statement (and less preferably: viewpoint) you've ever seen about this $f$? I bar asymptotic statements as inherently unnatural (unless you can convince me otherwise). To open the floor the widest, I'll put a CW stamp on this question.

-
In what way are asymptotic statements inherently unnatural? Asymptotics are an important way of ignoring extraneous information in a problem to concentrate on the most important aspects of it, and arguably the whole realm of infinitary analysis is just about what happens when you focus only on the asymptotics (as epsilon goes to zero) and ignore the error terms. –  Qiaochu Yuan Oct 13 '10 at 18:36
What's unnatural about the prime number theorem? –  Yemon Choi Oct 13 '10 at 19:22
Of course, f only seems erratic if you think about numbers sequentially, as opposed to in terms of divisibility. –  Ben Webster Oct 13 '10 at 19:37
The behavior of the function $F: \mathbb{N}^\infty \to \mathbb{N}$, where $F(x_2, x_3, x_5, x_7, \ldots) = f(2^{x_2} 3^{x_3} 5^{x_5} 7^{x_7} \ldots)$, is perhaps less erratic. (In other words, $f(n)$ really depends on the prime factorization of $n$.) –  Michael Lugo Oct 13 '10 at 21:59
A natural-though-not-exceedingly-informative statement is that if $m$ divides $n$ then $f(m)\le f(n)$. –  Gerry Myerson Oct 13 '10 at 23:34

Even though it is CW, the main part of the question is fairly narrow: What interesting structure is there in the exact values of the function $f(n)$, the number of groups of order $n$? As Michael Lugo and Ben Webster pointed out in their remarks, it's much better to re-parametrize the domain using unique factorization: $$F(x_2,x_3,x_5,x_7,\ldots) = f(2^{x_2}3^{x_3}5^{x_5}7^{x_7}\ldots).$$ Presented in this form, I found a nifty review of the group-counting function. Here is a summary of some of the results: $$f(p) = 1 \quad f(p^2) = 2 \quad f(p^3) = 5 \quad f(2^4) = 14 \quad f(p^4) = 15 \;\;\text{(p odd)}$$ $$f(pq) = 2 \;\;\text{(if p|q-1)} \quad f(pq) = 1 \;\;\text{otherwise} \quad \ldots$$ It seems (I'm not sure if there is a precise theorem) that if you fix the arguments of $F$ but let the primes vary, then its values are always some polynomials in those primes, stitched together with congruences.

As for asymptotic formulas, I don't really know what the word "natural" means, but certainly an asymptotic estimate of the number of groups is extremely important in computational group theory. It's more important than the exact number. Consider the obvious computational model of the group $G = \text{GL}(n,p)$. You can, uniformly in $n$ and $p$, describe, multiply, and invert group elements in any of these groups in polynomial time in $\log |G|$. Extending this model to all finite groups (or to a sequence of finite groups that includes every finite group at least once) is a major open problem in computational group theory. As a first step, it would not be possible if there were too many finite groups, so it is an important theorem that there are $2^{O(n^3)}$ groups of order $2^{O(n)}$. After that, you would like a computationally effective listing of these groups, not just any listing that gives you a bound. No one can exhibit a specific sequence of groups in which the group law is difficult. The problem seems to lie entirely in the fact that a complete list of them is unwieldy.

-
The missing' group of order 16 jumps out of that list. My guess is that there are two methods of making groups of order p^4 that are accidentally isomorphic' when p=2, but nothing on the list in the link jumps out as a candidate. Does anyone know if this can be made precise? –  Greg Muller Oct 19 '10 at 13:22

The most general statement that I have seen is due to Holder and gives the following result: if $n$ is squarefree, and if $f_p(n)$ is the number of primes $q$ with $q \mid n$ and $p \mid q-1$, then the number of groups of order $n$ is given by $$g(n) = \sum_{d\mid n}\prod_{p\mid d,\;d > 1} \frac{p^{f_p(n/d)}-1}{p-1}.$$

This formula is nic ein that it is exact; of course, the asymptotics here are very hard to extract, and given that there tend to be more groups of non-squarefree order than of squarefree order it is not terribly useful in asymptotic estimates.

-

You might be interested by the paper "Counting groups: gnus, moas and other exotica" by Conway, Dietrich and O'Brien, Math. Intelligencer 30, 6--15, 2008, and other work on p-groups by O'Brien, and/or Eick and her collaborators.

-
You also might want to take a look at MR2382539 (2009c:20041) Blackburn, Simon R.; Neumann, Peter M.; Venkataraman, Geetha Enumeration of finite groups. Cambridge Tracts in Mathematics, 173. Cambridge University Press, Cambridge, 2007. xii+281 pp. –  Primoz Oct 19 '10 at 10:09