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

Question

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.

Answer 1

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)$.

Answer 2

Higman and Sims showed that the number of groups of order p^m is somewhere around p^2m3/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.

Answer 3

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.