3
$\begingroup$

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?

$\endgroup$

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
1
$\begingroup$

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.

$\endgroup$
  • $\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.