How Many Group Structures on a Set?

17 Jun 2021

And so ends my first year of grad school. I’m pretty tired, and my mental health has taken a turn for the worse, though it’s hard to piece together if the last few weeks were tiring because my mental health was declining, or if my mental health is in decline because the last few weeks were tiring. Probably a little bit of both. Anyways, I have some free time again and a backlog of ideas for blog posts. Speaking of, now that my life update is out of the way, let’s see a kind of cute computation!

So the other day someone on mse asked:

The answer is, of course, vanishingly small. But it’s interesting to see how vanishingly small. The answer is actually quite memorable!

We can get a lower bound by assuming $|G|=n$ is prime. After all, there is only one group structure that will work in this case, so this is the lowest possible. The only thing we can do is rename the elements, so there are $n!$ many group operations on $G$.

We can get an upper bound if we assume $|G|=2^n$. We also have to assume the (widely believed) conjecture that “most groups are $2$ groups” in order to know that this is an upper bound. At the very least, it is an upper bound for groups of size at most $2000$, since $99\mathrm{\%}$ of these groups have order $1024$.

The same mse question I just linked provides an asymptotic formula for the number of group structures on a set of size $N=2^n$. Multiplying by $N!$ because we are interested in all group structures, not just groups up to isomorphism, we find an upper bound of (very roughly) $N!N^{\frac{2}{27}\log (N{)}^2}$

Putting our upper and lower bounds together, we see

$$N!\le \text{ \# group structures on a set of size }N\le N!N^{\frac{2}{27}\log (N{)}^2}$$

But by approximating $N!\approx {\left(\frac{N}{e}\right)}^N$, we get

$$e^{-N}{N}^N\le \text{ \# group structures on a set of size }N\le e^{-N}{N}^{N+\frac{2}{27}\log (N{)}^2}$$

logging everything in sight shows the number of group structures is $\mathrm{\Theta }(N\log (N))$. We can write this as the (rather memorable)

$$\text{\# group structures on a set of size }N=N^{\mathrm{\Theta }(N)}$$

and to finally answer the problem, there are $N^{N^2}$ many distinct binary operations on a set of size $N$. So the probability that a random one is a group operation decays like $N^{-\mathrm{\Theta }(N^2)}$, which is vanishingly small, as promised.