# Counting the Groups of Order n Weighted by 1/|Aut(G)|

Idle question:

Let $g(n)$ be the sum, over all isomorphism classes of groups of order $n$, of $\frac{1}{|Aut(G)|}$ where $G$ is a group in the class. Thus $g(n)n!$ is the number of group laws on a fixed set of size $n$. Is anything known about the asymptotic behavior of this quantity? I could easily believe that abelian groups account for most of it. If we only count abelian groups, calling the analogous number $a(n)$, then the function $a$ is clearly multiplicative in the sense that $a(mn)=a(m)a(n)$ when $m$ an $n$ are relatively prime, and I believe that the function $a(p^k)$ can be written as an explicit function of $k\ge 0$ and the prime $p$: $a(p)=\frac{1}{p-1}$, $a(p^2)=\frac{p}{(p-1)(p^2-1)}$, $a(p^3)=\frac{p^3}{(p-1)(p^2-1)(p^3-1)}$.

ADDED: So it looks like $a(p^k)=p^{\frac{(k(k-1)}{2}}\prod_{1\le j\le k}(p^j-1)^{-1}$. (I checked it up to $k=4$.) If you let $m\ge k$ and use the fact that every abelian group of order $p^k$ is isomorphic to a subgroup of $(\mathbb Z/p^m)^k$ and the fact that every isomorphism between two such subgroups is induced by an automorphism of $(\mathbb Z/p^m)^k$, you can interpret this as saying that the sum, over all automorphisms $g$ of $(\mathbb Z/p^m)^k$, of the number of subgroups of order $p^k$ in the fixed set of $g$, is a certain power of $p$. But I can't think of a reason why that should be true.

-
There seem to be some relevant comments and information at mathoverflow.net/questions/21265/… –  Joel David Hamkins Jul 3 '10 at 21:25
A basic sanity check: It is true that $\sum_{k \geq 0} p^{k(k-1)/2} \prod_{1 \leq j \leq k} (p^j-1)^{-1} = \prod(1-p^{-n})^{-1}$. Proof: The left hand summand can be rewritten as $p^{-k} / \prod_{1 \leq j \leq k} (1-p^{-j})$, which is well known to be the generating function for partitions with precisely $k$ parts. The right hand side, of course, is the generating function for all partitions. –  David Speyer Jul 7 '10 at 15:06
Your conjecture is true. See the proof of Theorem 2.1.2 in math.uni-sb.de/ag/gekeler/PERSONEN/Lengler/… for a combinatorial proof. I have an idea for a conceptual proof (continued...) –  David Speyer Aug 24 '10 at 23:04
Recall that, if we choose a random $k \times k$ matrix of $p$-adics then, as $k$ goes to $\infty$, the probability that the cokernel is isomorphic to $G$ approaches $\prod_{n=1}^{\infty} (1-p^{-n}) |\mathrm{Aut}(G)|^{-1}$. Your conjecture is that the probability that the determinant is $p^k(\mathrm{unit})$ is $p^{-k} \prod_{n > k} (1-p^{-n})$. Equivalently, the probability that the determinant is not $0$ modulo $p^k$ is $\prod_{n \geq k} (1-p^{-n})$. Don't know how to prove this, but it sounds simpler. –  David Speyer Aug 24 '10 at 23:08

Regarding the abelian case, fix a prime $p$. Philip Hall (A partition formula connected with Abelian groups, Commentarii Mathematici Helvetici 11 (1938), 126–129) proved the "curious formula" $$\sum_G \frac{1}{|G|} = \sum_G \frac{1}{|\mathrm{Aut}\ G|},$$ where the sum ranges over all non-isomorphic finite abelian $p$-groups. The left-hand side is clearly $\prod_{n\geq 1}(1-p^{-n})^{-1}$. See also http://www.springerlink.com/content/052624l251072312/fulltext.pdf. It should be possible from these papers to give a formula for $a(p^n)$.

-

Higman and Sims showed that the number of groups of order pm is somewhere around p2m3/27, up to some smallish correction that I cant remember offhand. This is vastly bigger than the size of the typical automorphism group of such groups, so dividing by the automorphism group does not make much significant difference to this number.

The number of groups of order at most N is dominated by those of order a power of 2. (The next most common are those of order 3 times a power of 2). The number of groups of given order N has been worked out exactly for N up to about 2000.

-
And the sequence listing the number of groups of given order N up to 2047 is the very first sequence in Sloane's database oeis.org/A000001 the longer list being this oeis.org/b000001.txt –  Thomas Sauvaget Aug 9 '10 at 17:51

Computational evidence suggests $g(n)$ varies wildly with $n$. When $n$ is a power of a prime, or has lots of small factors, $g(n)$ can be very large (I would guess $g(2^k)$ is superexponential in $k$), and $a(n)$ contributes negligibly. In particular, for the prime power case, three-step nilpotent groups seem to dominate, and a good theoretical reason for this is that they asymptotically dominate in number of isomorphism types by a huge factor.

If $n$ has only a few factors, then $g(n)$ is a little bigger than $1/n$. In this case, $a(n)$ contributes nontrivially.

For those of you who are interested in groups of order $2^n$ (and who isn't?), I've computed a decomposition of $g(2^k), k \leq 7$ by nilpotence class, so the class one columns on the left indicate $a(2^k)$, the abelian contribution.

g(2) = a(2) = 1.

nilpotence class |   1
isom. types      |   1
weighted count   |   1

$g(4) = a(4) = 2/3 \sim 0.67$.

nilpotence class |   1
isom. types      |   2
weighted count   |  2/3

$g(8) = 23/42 \sim 0.55$

nilpotence class |     1      |     2
isom. types      |  3 (60%)   |  2 (40%)
weighted count   | 8/21 (70%) |  1/6 (30%) 

$g(16) = 1247/2520 \sim 0.49$

nilpotence class |       1      |     2     |   3
isom. types      |    5 (36%)   |  6 (43%)  |   3 (21%)
weighted count   | 64/315 (41%) | 1/6 (34%) | 1/8 (25%) 

$g(32) = 149297/312480 \sim 0.48$

nilpotence class |        1        |       2      |      3     |   4
isom. types      |     7 (14%)     |   26 (51%)   |  15 (29%)  |  3 (6%)
weighted count   | 1024/9765 (22%) | 37/240 (32%) | 3/16 (39%) | 1/32 (7%) 

$g(64) = 48611383/78744960 \sim 0.62$

$\begin{array}{rccccc} \text{nilpotence class} & 1 & 2 & 3 & 4 & 5 \\ \text{isomorphism types} & 11\, (4\%) & 117\, (44\%) & 114 \, (43\%) & 22\, (8\%) & 3\, (1\%) \\ \text{weighted count} & \frac{32768}{615195} \, (9\%) & \frac{3}{20} \, (24\%) & \frac{5}{16} \, (51\%) & \frac{3}{32} \, (15\%)& \frac{1}{128} \, (1\%) \end{array}$

$g(128) = 8999449693/8000487936 \sim 1.12$

$\begin{array}{rccccc} \text{nilpotence class} & 1 & 2 & 3 & 4 & 5 & 6 \\ \text{isomorphism types} & 15 \, (1\%) & 947 \, (41\%) & 1137 \, (49\%) & 197 \, (8\%) & 29 \, (1\%) & 3 \, (0\%) \\ \text{weighted count} & \frac{2097152}{78129765} \, (2\%) & \frac{275929}{1451520} \, (17\%) & \frac{2295}{3584} \, (57\%) & \frac{7}{32} \, (19\%) & \frac{3}{64} \, (4\%) & \frac{1}{512}\, (0\%) \end{array}$

The groups of order 64 took about 15 minutes on my ancient computer running GAP, and the groups of order 128 took about 40 hours. I'll leave the question of groups of order 256 to someone else, since a modern desktop computer should be able to work it out in a little under a year.

You might be curious about the three isomorphism types of nilpotence class $k-1$ for $k \geq 4$. They are the dihedral, quasidihedral, and quaternion groups.

-