I am aware of Light's associativity test for Cayley tables, but I am wondering, is there a clever way to deduce associativity from the set's properties / presentation that permits one to not have compute every single product?
I had a problem that involved deducing whether or not a set is associative given its Cayley table, and, upon confirming with my professor that one indeed has to compute every single product (64 of them!?), he mentioned that such a problem can be greatly simplified by observing certain patterns that seem to emerge in the table (i.e. the set's properties). Can someone give me an example of such a case where this happens?
Thanks in advance.
Best Answer
Testing whether a multiplication table defines a group can be done faster in general than just checking it for associativity. This is because you can start by testing whether it is a Latin square. If not then it is not a group, and if so, it makes the tests easier.
Light's associativity test requires $O(n^3)$ checks in the worst case, whereas testing whether it is a group can be done in $O(n^2 \log n)$. See this post for example. I believe it is unknown whether you can improve on $O(n^2 \log n)$, and the problem clearly requires you to read the input, so $\Omega(n^2)$ is a lower bound.