# For which cases with $2$ or $3$ prime factors do formulas for $gnu(n)$ exist?

Denote : $gnu(n)=$number of groups of order $n$

For squarefree $n$, there is a closed formula for $gnu(n)$. Prime powers upto $p^7$ are also completely solved and I found a formula for the case $p^2q$.

In GAP, the cube-free case is solved. My limitied GAP-version works upto $n=50,000$ in this case. But even for $p^2q^2$, I nowhere found an explicit formula.

My GAP-version is already doomed with numbers like $9317=7\times 11^3$

Do formulas exists for the cases $p^2q^2$ and $p^3q$ ? I read somewhere in this forum that these cases have been done, but I nowhere found a formula.

Which cases are completely solved, if $n$ has at most $3$ distinct prime factors ? The easiest non-cube-free-case is $p^3q$ ? Again, formulas would be very welcome.

Finally, does anyone know $gnu(n)$ or at least a sharp upper bound for the following n ? $$[2052,2058,2064,2072,2079,2080,2088,2106]$$ These are the smallest values beyond $2048$, for which my GAP-version is doomed.

• Tight upper bounds instead of formulas are also welcome. – Peter Dec 26 '15 at 13:12
• I warned you that your minimal GAP installation has limited functionality. With GrpConst package, ConstructAllGroups(9317) returns a list of 6 groups instantly. If you need to explore the problem further, you may do one or more of the following: ask someone with a fast connection to download GAP for you; try to add packages one by one; ask me to add more functionality to the GAP SCSCP server to be able to call it remotely. – Alexander Konovalov Dec 26 '15 at 15:29
• @Alexander Konovalov Or, you create a file with the values you can get, upto, lets say, $200,000$, if you want to $1,000,000$ and produce a link to that file. The gnu-problem obviously is one of the most difficult combinatorical problems. Or, at least, you can give the values $n$ with $gnu(n)\ge n$ or unknown by GAP. – Peter Dec 26 '15 at 17:17
• @Alexander Konovalov Is there a possibility to manipulate GAP, such that it returns $0$, if it cannot determine $gnu(n)$ instead of an error ? MAGMA has such a command (it can test, whether $n$ is in the small-group-database). – Peter Dec 26 '15 at 17:18
• Hi @Peter! The coming soon public release of GAP 4.8 will have CallWithTimeout - see the pre-release announcement here. I will check the workspace question - not sure at the moment. Please remind me next week if I will not get back to you earlier. – Alexander Konovalov Jan 7 '16 at 21:04

I believe the following gives the answer for $|G| = p^2q^2$, where $p,q$ are prime and $p < q$. I will use $f(p,q)$ to denote the number of groups of order $p^2q^2$.

a) $p=2$ and $q=3$: $f(p,q) = 14$.

b) $p=2$ and $q > 3, q = 3 \mod 4$: $f(p,q) = 12$.

c) $p=2$ and $q = 1 \mod 4$: $f(p,q) = 16$.

d) $p>2$ and $p \nmid q^2 - 1$: $f(p,q) = 4$.

e) $p>2$ and $p \mid q+1, p^2 \nmid q+1$: $f(p,q) = 6$.

f) $p > 2$ and $p^2 \mid q+1$: $f(p,q) = 7$.

g) $p > 2$ and $p \mid q-1, p^2 \nmid q-1$: $f(p,q) = p + 10$.

h) $p > 2$ and $p^2 \mid q-1$: $f(p,q) = \frac{p^2+3p+24}{2}$.

Here's how I came up with these formulas:

Let $S_p$ and $S_q$ be $p$-Sylow and $q$-Sylow subgroups of $G$, respectively. Note that, except in the case $p=2$ and $q=3$, we have $q \nmid p^2-1$, so the group $S_q$ will be normal.

b) I: $S_q = \mathbb{Z}_{q^2}$

$\text{Aut}(S_q) = \mathbb{Z}_{q^2}^* \approx \mathbb{Z}_{q^2-q}$, and $q^2-q$ is divisible by $2$ but not $4$. If $S_p = \mathbb{Z}_4$ then we can either have a generator of $S_p$ act on $S_q$ via the unique involution, or it can act trivially, resulting in two groups. If $S_p = \mathbb{Z}_2 \times \mathbb{Z}_2$, then either two of the elements of $S_p$ can act on $S_q$ via the involution and two act trivially, or they can all act trivially, resulting in another two groups.

II: $S_q = \mathbb{Z}_q \times \mathbb{Z}_q$

$\text{Aut}{(S_q)} = \text{GL}_2 (F_q)$, which is a group of order $q(q+1)(q-1)^2$. If $S_p = \mathbb{Z}_4$, let $g$ be a generator of $S_p$. There are elements of order $q+1$ in $\text{GL}_2 (F_q)$, and $q+1$ is divisible by $4$, so we can map $g$ to an automorphism of order $4$. It turns out that this yields a unique group up to isomorphism. Otherwise, the action of $g$ on $S_q$ will have two eigenvectors $u$ and $v$. The action on $u$ will be an action on the subgroup $\mathbb{Z}_q$ generated by $u$; since $q-1$ is not divisible by $4$, the action must be the unique involution or the trivial action. So the action of $g$ can either act nontrivially on both of $u$ and $v$, just one, or neither, adding another three groups. (To see that acting on both vectors yields a different group than acting on one, observe that the first fixes only the identity, whereas the latter fixes either $u$ or $v$.) If $S_p = \mathbb{Z}_2 \times \mathbb{Z}_2$, then we have two independent vectors $a$ and $b$ in $S_p$, and for each we have three different possible actions. Suppose at least one acts trivially; then the other has three possible actions, yielding three more groups. Finally, if no nonidentity element of $S_p$ acts trivially, then there is one possibility: one element acts nontrivially on $u$, one on $v$, and one on both $u$ and $v$. This yields the final group.

All told there are 12 groups up to isomorphism.

a) We have $p=2$ and $q=3$. The 12 groups described above all exist in this case as well, but there is also the possibility that $S_q$ is not normal, since $q \mid p^2-1$. One can show that if $S_q$ is not normal, than $S_p$ will be. If $S_p = \mathbb{Z}_4$, then $\text{Aut}(S_p) = \mathbb{Z}_2$, so $S_q$ cannot act nontrivially, so it would be normal. So we must have $S_p = \mathbb{Z}_2 \times \mathbb{Z}_2$. In this case we have $\text{Aut}(S_p) = S_3$ (the symmetry group on three elements, in this case the three nonidentity elements of $S_p$). If we have $S_q = \mathbb{Z}_9$, then we a unique group where $S_q$ acts nontrivially on $S_p$. Similarly for $S_q = \mathbb{Z}_3 \times \mathbb{Z}_3$. The reason is that $S_q$ must map to the subgroup $\mathbb{Z}_3$ of $\text{Aut}(S_p)$, and in both cases there is only one way to make such a mapping up to isomorphism.

This adds two more groups for a total of 14.

c) $p=2$ and $q = 1 \mod 4$. Again we have the 12 groups described in section b). We also get additional groups in the case $S_p = \mathbb{Z}_4$. When $S_q = \mathbb{Z}_{q^2}$, we get one group where a generator for $S_p$ maps to an automorphism of $S_q$ of order $4$; this exists since $4 \mid q^2-q$. When $S_q = \mathbb{Z}_q \times \mathbb{Z}_q$, one of the basis vectors for $S_p$ can map to an automorphism of order $4$ (guaranteeing new groups) and the other can map to automorphism of either order $1,2,$ or $4$, yielding 3 new groups.

This adds four groups for a total of 16.

d) If $p \nmid q^2 - 1$ and $q \nmid p^2 - 1$, then both Sylow subgroups are normal, and the group is just the direct product of the two. There are two possibilities for each Sylow subgroup, yielding 4 groups in total.

e) If $p \mid q+1$ but $p^2 \nmid q+1$, then we still have the $4$ groups from d). We get no new groups when $S_q = \mathbb{Z}_{q^2}$, since $p \nmid q^2 - q$, however if $S_q = \mathbb{Z}_q \times \mathbb{Z}_q$ then we get $p \mid |\text{Aut}(S_q)| = q(q+1)(q-1)^2$, so by Cauchy's theorem there are elements of order $p$. So we get one group with $S_p = \mathbb{Z}_{p^2}$, and one group where $S_p = \mathbb{Z}_p \times \mathbb{Z}_p$.

This adds two groups for a total of 6.

f) If $p^2 \mid q+1$, we still have the 6 groups from e), and we also get one group where $S_q = \mathbb{Z}_q \times \mathbb{Z}_q$, and $S_p = \mathbb{Z}_{p^2}$, and a generator for $S_p$ maps to an automorphism of $S_q$ of order $p^2$.

This adds one group for a total of 7.

g) I: $S_q = \mathbb{Z}_{q^2}$.

If $S_p = \mathbb{Z}_{p^2}$, then a generator for $S_p$ can either map to an automorphism of order $p$, or to the identity, yielding two groups. If $S_p = \mathbb{Z}_p \times \mathbb{Z}_p$, then either two of the elements of $S_p$ can map to an automorphism of order $p$ and the other two to the identity, or they all can map to the identity, yielding two more groups.

II: $S_q = \mathbb{Z}_q \times \mathbb{Z}_q$.

If $S_p = \mathbb{Z}_{p^2}$, then a generator for $S_p$ will map to an automorphsim of order $p$ or $1$. Such an automorphism $g$ will have two independent eigenvectors $u$ and $v$. Suppose that $g$ fixes neither $u$ or $v$. If $a$ is an element of order $p$ in $\mathbb{Z}_q^*$, then $g$ will map $u$ to $a^i u$ and $v$ to $a^j v$ for some $I,j$ between $1$ and $p-1$. Then $g^k$ will map $u$ to $a^{ik} u$ and $v$ to $a^{jk} v$, so we can choose $k$ so that $a^{ik} = a$. This will make $g^k$ a mapping from $u$ to $au$ and $v$ to $a^l v$. So there appear to be $p-1$ possibilities. However, we can also choose $k$ so that $a^{jk} = a$, so that $g^k$ maps $u$ to $a^m u$ and $v$ to $av$. This obviously yields an isomorphic group to the case where $g^k$ maps $u$ to $au$ and $v$ to $a^m v$, since we can just switch $u$ and $v$. So we wind up with pairs $(l,m)$ where either choice results in the same group. There are two cases where $m$ and $l$ are the same, namely $m = 1$ and $m = p-1$; the remaining $p-3$ numbers divide up into pairs, resulting in $\frac{p-3}{2}$ different groups, then the cases $m=1$ and $m=p-1$ add two more groups. Finally there is the possibility that $g$ fixes at least one of $u$ or $v$. We can either have $g$ move one, or have $g$ act trivially on both, yielding two more groups for a total of $\frac{p+5}{2}$ under this case.

If $S_p = \mathbb{Z}_p \times \mathbb{Z}_p$, then first consider the case where one of the basis vectors of $S_p$ acts trivially on $S_q$. Then the other cases can act in any of the $\frac{p+5}{2}$ ways above, adding that many new groups. Otherwise, we must have every nontrivial element of $S_p$ act nontrivialy on $S_q$; there is really only one possibility, where one basis vector moves some eigenvector $u$, and the other basis vector moves an independent eigenvector $v$.

In total, there are $p + 10$ different groups.

h) I: $S_q = \mathbb{Z}_{q^2}$.

We get four groups as in g). However, in the case that $S_p = \mathbb{Z}_{p^2}$, we also get a group where a generator for $S_p$ maps to an automorphism of order $p^2$, as $p^2 \mid q^2 - q$.

II: $S_q = \mathbb{Z}_q \times \mathbb{Z}_q$.

First, suppose that $S_p = \mathbb{Z}_p \times \mathbb{Z}_p$. Then we get the same $\frac{p+7}{2}$ groups as listed above in g). Next, suppose that $S_p = \mathbb{Z}_{p^2}$. Again, let $g$ be a generator for $S_p$, and let $u$ and $v$ be independent eigenvectors under the action of $g$. If $g$ maps to an automorphism of order $p$ or $1$, then we will get one of the $\frac{p+5}{2}$ groups listed in g). If $g$ maps to an automorphism of order $p^2$, then it must perform an action of order $p^2$ on either $u$ or $v$; WLOG suppose the action on $u$ is of order $p^2$. We get one group where $g$ acts trivially on $v$. Suppose the action on $v$ is of order $p$; then, if $a$ is an element of order $p^2$ and $b$ an element of order $p$ in $\mathbb{Z}_q^*$, we can choose $k$ so that $g^k$ takes $u$ to $au$ and $v$ to $b^m v$, where $m$ can be any number from $1$ to $p-1$. This leads to $p-1$ different groups. (No pairing this time since we can distinguish $u$ and $v$) Finally, suppose the action on $v$ is of order $p^2$. Then, as we have argued previously, we can choose a $k$ such that $g^k$ maps $u$ to $au$ and $v$ to $a^l v$, where $l$ can be any of the $p^2 - p$ elements of $\mathbb{Z}_{p^2}^*$. As before, the elements will be paired off, except for $l =1$ or $l =p^2-1$. So this results in $\frac{p^2-p+2}{2}$ possible groups.

All told, there will be $\frac{p^2 + 3p + 24}{2}$ different groups.

• That looks good,although I haven't checked it in detail. You don't need to write $q>3$ in f) and g) because $q>p>2$. – Derek Holt Dec 28 '15 at 9:38

I already answered this question in comments to another of your recent question: Where can I find the known values for the number-of-groups-function upto $10,000\$?

To re-iterate, there are a few papers about the cases $p^2q^2$ and $p^3q$, some of them do give formulas, but they seem to be not completely right.

As far as I know, that's the state of the art in the published literature.

EDIT: Some of the orders you mentioned are also easy to deal with in an ad hoc manner. For example 2058 is twice odd. In particular, a group of order 2058 is a semidirect product of a characteristic group of order 1029 with a cyclic group of order 2. So, to count the number of groups of order 2058, you go through the groups of order 1029. For each of them, you compute the automorphism group and, for each conjugacy class of involution, construct the appropriate semidirect product and check for isomorphs. You then sum the whole thing. (You don't have to check for isomorphs between the different groups of order 1029. Don't forget the direct product.)

Same with 2106 for example.

By the way, I'm no expert in this area, but my guess is that whatever techniques Besche, Eick and O'Brien used in their "at most 2000" paper would work easily for most of the orders you mentioned. There is nothing special about 2000, they just had to stop somewhere. As long as there isn't a large power of a prime dividing $n$, they should be able to compute gnu(n) way past 2000.

• ${\texttt{ConstructAllGroups}}$ works on all of the specified orders, although it takes a while on some of them. – Derek Holt Dec 27 '15 at 11:27
• Thanks Derek, I wasn't aware of this feature of GAP. (I mostly use magma and I don't think it has the equivalent.) – verret Dec 27 '15 at 11:45
• @verret The reason that OEIS stopped at $2048$ is because this value is unknown and OEIS seems to avoid gaps in the sequences. Otherwise, the sequence would surely get much further. – Peter Dec 27 '15 at 11:50
• @Derek Holt Unfortunaely, my limited version does not support this. – Peter Dec 27 '15 at 11:51
• @Peter I didn't mention the OEIS... I was talking about the fact that the SmallGroups library (or at least the version in magma) is only exhaustive up to 2000. This was a deliberate but somewhat arbitrary choice. They could have gone on (skipping such orders as 2048). – verret Dec 27 '15 at 11:54