# Testing for associativity using the multiplication table (Cayley Table) of an operation. [duplicate]

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 ROct 28 '18 at 6:39

• 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... – user1729 Oct 24 '18 at 12:38
• 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. – Carl Mummert Oct 28 '18 at 1:06

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

Basically,

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.

• 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. – Rob Arthan Nov 7 '17 at 22:39
• @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. – Qudit Nov 7 '17 at 23:06
• @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.). – Rob Arthan Nov 7 '17 at 23:29
• @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. – Qudit Nov 7 '17 at 23:38
• @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. – Rob Arthan Nov 7 '17 at 23:46