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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.