# Complexity of testing if a binary operation is a group

Given a binary operation specified as an $n \times n$ Cayley table, what is the complexity of the best deterministic algorithm for testing if the binary operation is a group?

There's a fairly simple deterministic $O(n^2 \log n)$ algorithm which works as follows. We can check if the binary operation is a quasigroup in $O(n^2)$ time by verifying the Latin square property. It is also easy to determine if the group has an identity element in $O(n^2)$ time. Quasigroups have generating sets of size at most $\log_2 n$ and such a generating set can be found in $O(n^2)$ time using a simple greedy algorithm. Applying Light's associativity test then allows us to test associativity in $O(n^2 \log n)$ time.

An obvious lower bound is $\Omega(n^2)$. According to wikipedia, there is a randomized BPP algorithm for testing associativity in $O(n^2)$, so this bound is tight for BPP algorithms.

Is there a deterministic $O(n^2)$ algorithm as well?

• The input is $n^2\log n$ bits - so you're asking for a sublinear algorithm? I couldn't access the Rajagopalan-Schulman BPP algorithm paper so don't know what their computational model is.
– Dap
Nov 10, 2017 at 8:03
• @Dap No, it would be a linear time algorithm. In this model, one typically assumes group operations and things like equity testing can be done in constant time. Think of each group element as using one unit of memory. Nov 10, 2017 at 8:10

It was shown only recently that testing whether a Latin Square is a group takes time $$O(n^{2} \log^{c} n) = \tilde{O}(n^2)$$ (the $$\tilde{O}$$ hides the polylogarithmic factor).
• That is an interesting paper but I don't think it is directely relevant to the question above. The algorithm that the authors give is in the Turing machine model whereas here I am considering the more usual RAM machine model. Presumably, this difference is the reason for the extra log factors in the paper. Also , I guess you meant $\tilde{O}(n^2)$ instead of $\tilde{O}(n)$. May 15 at 6:39