Communication complexity for deciding associativity

Question

Let $S=${$0,...,n-1$} and $\circ : S \times S \rightarrow S$. I want to compute the communication complexity of deciding whether $\circ$ is associative.

The model is the following. $\circ$ is given as a matrix $M$. Alice (resp. Bob) is given half the entries of the matrix at random (same for Bob). I want to compute the worst case number of entries that Alice must send to Bob so that Bob can decide on the associativity of $\circ$.

In fact, it is simple to reduce the problem of deciding the equality of two bit strings of size $\Omega(n)$ to the problem of deciding the associativity of $\circ$ over $S$. This means that the communication complexity of the associativity is lower bounded by $\Omega(n)$. However, I suspect that this LB is not tight. Being defined on an input of size $n^{2}$, I would have prefer to find a communication complexity of $\Omega(n^{2})$.

Is there a known result on this problem ? Is the answer is $n^{2}$ for an obvious reason I am not seeing ?

Answer 1

There are $n^{n^2}$ binary operations on $S$. The question is how many of them are associative. Kleitman, Rothschild and Spencer give an asymptotic counting formula for this problem in their paper The number of semigroups of order $n$. It has a relatively simple form in what they call the "non-rare instances" where the peak of $f(t)$ dominates so the other terms can be neglected without affecting the asymptotics. You should be able to give a lower bound for your question by cranking through the math with this formula.