# Given a random binary operation $\varphi$ on a finite set $G$, what is the probability that $(G,\varphi)$ is a group?

I recently learned about the 5/8 theorem, which states that if the probability that any two random elements in a group commute exceeds 5/8, then the group must be abelian. I think its interesting seeing probability and group theory together, which led me to think of this question.

This is my work so far, which has a good possibility of being flawed. First, consider all binary operations $$\varphi : G\times G \to G$$, which given $$|G|=n$$ we can count as $$|G|^{|G\times G|^2} = n^{n^2}$$.

Next, consider all binary operations that fail to have an identity $$e \in G$$. If $$\varphi(g,e)\neq g$$ (or $$\varphi(e,g)\neq g$$) for any single $$g \in G$$, we can throw out all other possible functions given by the other elements in $$G- \{g\}$$, which is given by $$(n-1)^{(n-1)^2}$$ operations. There are $$n^2$$ elements in $$|G\times G|$$ that each have $$(n-1)$$ ways to fail, so the number of binary operations that fail to have an identity element should be given by $$n^2(n-1)(n-1)^{(n-1)^2}=n^2(n-1)^{(n-1)^2+1}$$ Hence, we can get an upper bound for how many binary operations can form groups as $$n^{n^2}-n^2(n-1)^{(n-1)^2+1}$$ For inverses, I think the same argument can be made as the above, hence an upper bound after considering inverses is given by $$n^{n^2}-2n^2(n-1)^{(n-1)^2+1}$$ I have no idea how to even get started with associativity! Further, I have never been fantastic at counting problems, so I am sure I made a flaw in my argument thus far. Any progress or criticisms are very much welcome.

• Related. Jun 8, 2021 at 11:53

Fleshing out my comment on Ethan's answer, and assuming the conjecture that "most groups are $$2$$-groups", we can get an asymptotic upper bound as well.

In this answer we see that $$\mu(p,n)$$, the number of groups of order $$p^n$$, grows like

$$\mu(p,n) = p^{\left ( \frac{2}{27} + O(n^{-1/3}) \right ) n^3}.$$

So when $$p = 2$$, if we set $$N = 2^n$$ we find there are roughly

$$\frac{N! \ 2^{\left ( \frac{2}{27} + O(\log(N)^{-1/3}) \right ) \log(N)^3}}{N^{N^2}}$$

which, for $$n \gg 1$$ (so we can quietly ignore the $$O(n^{-1/3})$$ term), is even more roughly

$$\frac{N! \ N^{\frac{2}{27} \log(N)^2}}{N^{N^2}}.$$

Since this is conjectured to be as big as possible, if we combine with Ethan's answer (which is obviously the smallest possible) we find

$$\frac{N!}{N^{N^2}} \leq \text{ the fraction of group operations on a set of size N } \leq \frac{N! \ N^{\frac{2}{27} \log(N)^2}}{N^{N^2}}.$$

Since $$N! \approx \left ( \frac{N}{e} \right )^N$$, which dominates the $$N^{\log(N)^2}$$ term that we've picked up, these bounds are deceptively close together (especially when placed next to the $$N^{N^2}$$ term).

I hope this helps ^_^

The probability will be quite small. If $$n$$ is prime there are just $$n!$$ ways to define a binary operation that yields a group, since the only group of prime order is cyclic. All you can do is rename the elements.
As you note, there are $$n^{n^2}$$ binary operations. $$\frac{n!}{n^{n^2}} \text{ is very small }.$$
• I also suspect there is no good answer, but this is necessarily the "worst case." I would be fascinated to see any similar result on $2$-groups, but I would guess even that is unknown. Jun 8, 2021 at 1:21
• On the other side of the spectrum, we suspect "most groups" have size $2^n$ for some $n$. We know there are 49,487,365,422 groups of order $1024$, and if we multiply by $1024!$ to get all the operations (rather than just the isomorphism type) we have the best chance of getting a large fraction of operations to be groups. But according to sage this is roughly $1.38 \times 10^{-3153878}$. So even in the best case, we get something "very small". Jun 8, 2021 at 1:23
• This is a great observation! Another idea is that if $n = p_1^{k_1}p_2^{k_2}\dots p_m^{k_m}$ counting abelian groups is given by the product of partitions of each $k_i$, so the probability that a random binary operation forms an abelian group is $\frac{n^{n^2}}{\prod_{i\leq m}P(k_i)}$ where $P(i)$ counts the partitions. Maybe then one could try to throw out commutativity from this? Jun 8, 2021 at 1:32