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

Question

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.

Answer 1

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 ^_^

Answer 2

Partial answer. (I suspect there is no good answer.)

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