This question already has an answer here:
Given an $n \times n$ multiplication table, can one check if it represents a group in $o(n^3)$ time? All properties can be checked by mindless try-all possibilities loops:
- Whether there is an identity element can be checked in $O(n^2)$ time.
- Whether every element has an inverse can be checked in $O(n^2)$ time.
- And associativity can be checked in $O(n^3)$ time.
My question is:
Q. Is there a faster algorithm for arbitrary tables, a subcubic algorithm?
This hardly needs illustration, but here is a multiplication table that would be $D_4$ if the two highlighted entries were swapped:
There is an identity element $1$, and every element has an inverse, but associativity fails: $$2 \cdot (5 \cdot 3) \neq (2 \cdot 5) \cdot 3$$ $$2 \cdot 4 \neq 6 \cdot 3$$ $$3 \neq 8$$ So this table does not represent a group.