I seem to recall that there is a relatively easy method for determining the associativity of an operation by using its Cayley table. What is it?


marked as duplicate by user1729, Carl Mummert, Xander Henderson, Lord Shark the Unknown, Chinnapparaj R Oct 28 '18 at 6:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I disagree that this question should give context or other detail - it admits a well-defined and interesting answer. The "context" is given: "can you help me remember something?" If the answer was not well defined then I can see an issue, but as it is well-defined... $\endgroup$ – user1729 Oct 24 '18 at 12:38
  • $\begingroup$ Please look through How to ask a good question for advice on writing good questions on this site. In particular, a post should go beyond merely stating a problem: the motivation and background should be included, to the extent you are familiar. Posts that merely state a problem without context are often put on hold. $\endgroup$ – Carl Mummert Oct 28 '18 at 1:06

It is called Light's associativity test which I found on Wikipedia.


  1. Pick out the generators of the operation.
  2. If $g$ is a generator define two new operations $x \circ y = (xg)y $ and $x*y=x(gy)$.
  3. Form the Cayley tables of $\circ$ and $*$ for $g$.
  4. If the two tables for $g$ are not identical, the original operation is NOT associative.
  5. If the two tables are identical for all generators $g$, the original operation IS associative.

Notwithstanding the first comment, the link above works now, Nov 7, thanks to a kind editor.

  • $\begingroup$ The URL you give doesn't work. The method you describe doesn't save much work unless it's easy to find a set of generators that is much smaller than the number of elements in the structure. $\endgroup$ – Rob Arthan Nov 7 '17 at 22:39
  • $\begingroup$ @RobArthan You can always find a generating set of size at most $\log_2 n$ in $O(n^2)$ time for a group of $n$ elements described by a Cayley table. This takes less time than the test itself. $\endgroup$ – Qudit Nov 7 '17 at 23:06
  • $\begingroup$ @Qudit: that's interesting, but I was thinking more of hand calculation for small magmas (say with less 10 elements) rather than the asymptotic complexity of the method. It's easy to come up with an $n$-element magma that has no generating set with less than $n$ elements, so I don't see how your observation about generating sets of groups helps in either case (if you know the magma is a group, then you already know it's associative.). $\endgroup$ – Rob Arthan Nov 7 '17 at 23:29
  • $\begingroup$ @RobArthan That's true. I suppose that in the case where you were testing for associativity in order to check if it is a group, you could try to find a generating set of size at most $\log_2 n$. If the procedure fails to find one in $O(n^2)$ time, then you know that it is not a group so you don't care if it is associative. Otherwise, you can proceed with the test. $\endgroup$ – Qudit Nov 7 '17 at 23:38
  • $\begingroup$ @Qudit: but the question (and Light's test) is about testing for associativity, not testing for all the group properties: people often do care about the associativity of operations that are not group operations. In any case, I think you need to modify your update to the Wikipedia page. $\endgroup$ – Rob Arthan Nov 7 '17 at 23:46

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