Number of Cayley tables on {0,1,...,n-1}

Question

My question is very simple: How many Cayley tables are there on {0,1,...,n-1}?

I tried coming up with a solution for smaller numbers and then to generalize my findings but am not even sure how to approach this question..

So I would really appreciate your help! Thanks a lot in advance!

Answer 1

If you consider Cayley tables as the set of functions $f:\{0,\dots,n-1\}^2\rightarrow \{0,\dots,n-1\}$ such that $f$ is associative, i.e. for all $i,j,k$, $f(f(i,j),k)=f(i,f(j,k))$ ; there exists a neutral element (let us fix it to be $0$) i.e. for all $i$ $f(i,0)=i=f(0,i)$ and any element admits an inverse i.e. for all $i$ there exists $i'$ such that $f(i,i')=0=f(i',i)$ then you are "somehow" asking how many finite groups of order $n$ there is, which is known to have no "accurate" answer. However, one may say a few things about this problem.

1. To any group $G$ (of order $n$) we can associate a Cayley table $f$ of order $n$ (with $0$ being associated to the neutral element). Indeed it suffices to define a bijection $\phi$ between $G$ and $\{0,\dots,n-1\}$ sending $1_G$ to $0$ and then define the Cayley table :

$$f(i,j):=\phi(\phi^{-1}(i)\cdot_G\phi^{-1}(j)) $$

2. To any Cayley table $f$, we can construct a group law on $\{0,\dots,n-1\}$ such that, there exists a permutation $\sigma$ of $\{0,\dots,n-1\}$ for which the construction of $1$ gives you the initial $f$. Indeed define the group law by $i\cdot j:=f(i,j)$ then $\sigma=Id$ clearly gives (through the construction of 1) the inital Cayley table $f$.

After this preliminary remark, we see that there should be a strong correspondance between isomorphism classes of group of order $n$ and Cayley tables on $\{,0,\dots,n-1\}$. However, it is well known that, to the same group, we can associate different Cayley tables (by varying the bijection $\phi$ chosen in 1).

One can make this correspondence very precise.

3. Let $f$ and $g$ be two Cayley tables of order $n$. Then $f$ and $g$ can be constructed as the Cayley table of the same group $G$ if and only if there exists a permutation $\sigma$ of $\{0,\dots,n-1\}$ fixing $0$ such that for all $i,j$ :

$$g(i,j)=\sigma(f(\sigma^{-1}(i),\sigma^{-1}(j))) $$

4. Actually if $\mathcal{C}_n$ denotes the set of Cayley tables of order $n$, we see that we have an action of $\mathfrak{S}_{n-1}$ (the set of permutations of $\{0,\dots,n-1\}$ fixing $0$) on $\mathcal{C}_n$ given by :

$$(\sigma\cdot f)(i,j)=\sigma(f(\sigma^{-1}(i),\sigma^{-1}(j))) $$

As a result (from 1,2 and 3) we see that there are as many isomorphism classes of groups of order $n$ as the number of orbits in $\mathcal{C}_n$ by this action of $\mathfrak{S}_{n-1}$.

We also remark :

5. Let $f$ be a Cayley table of order $n$ and $G_f$ be the group associated (by 2) to $f$ then for the action of $\mathfrak{S}_{n-1}$ on $\mathcal{C}_n$, we get that $Stab(f)$ is isomorphic to $Aut(G)$.

6. As a result, if you want to compute the number of Cayley tables of order $n$, you need to compute :

$$\sum_{i=1}^{r_n}\frac{(n-1)!}{|Aut(G_i)|} $$

where $r_n$ is the number of isomorphism classes of groups of order $n$ and $G_1,\dots,G_{r_n}$ are the $r_n$ different (up to isomorphism) groups of order $n$.

As a result :

There exists only $(p-2)!$ Cayley tables of order $p$ if $p$ is prime.

Proof :

There exists (up to isomorphism) one group of order $p$ (the cyclic one). It is well known that the automorphism group of a cyclic group of order $p$ has order $p-1$. It follows that the number of Cayley tables of order $p$ is $(p-1)!/(p-1)=(p-2)!$.

Another thing :

There are 2760 Cayley tables of order $8$.

Proof :

You have five groups of order $8$. The cyclic one $G_1$ whose automorphism groups is of order $4$. The group $\mathbb{Z}/2\times \mathbb{Z}/4$ whose automorphism group is of order $8$. The group $(\mathbb{Z}/2)^3$ whose automorphism group is of order $168$. The dihedral group $\mathbb{D}_4$ whose automorphism group is of order $8$ and the quaternionic group of order $8$ whose automorphism group is of order $24$. Making the computation (with the formula of 6), you finally get $2760$ Cayley tables of order $8$.