40
$\begingroup$

Most properties of a single binary operation can be easily read of from the operation's table. For example, given $$\begin{array}{c|ccccc} \cdot & a & b & c & d & e\\\hline a & e & d & b & a & c\\ b & d & c & e & b & a\\ c & b & e & a & c & d\\ d & a & b & c & d & e\\ e & c & a & d & e & b \end{array}$$ it is easy to check that it is closed (no elements occur in the table which don't occur as row or column index), commutative (the table is symmetric), has a neutral element (the row and column of $d$ are copies of the index row/column), and has an inverse element for each element (there's a $d$ in each row and column). In other words, almost all important properties can immediately be seen. The only part missing is associativity.

Therefore my question: Is there a simple way to see directly from the operation's table (i.e. without doing explicitly all the calculations) if an operation is associative?

$\endgroup$
25
$\begingroup$

Have you seen Light's associativity test? According to Wikipedia, "Direct verification of the associativity of a binary operation specified by a Cayley table is cumbersome and tedious. Light's associativity test greatly simplifies the task."

If nothing else, the existence of Light's algorithm seems to rule out the possibility that anyone knows an easy way to do it just by looking at the original Cayley table.

Note also that, in general, one cannot do better than the obvious method of just checking all $n^3$ identities of the form $(a\ast b)\ast c = a\ast (b\ast c)$. This is because it is possible that the operation could be completely associative except for one bad triple $\langle a,b,c\rangle$. So any method that purports to do better than this must only be able to do so in limited circumstances.

$\endgroup$
  • 3
    $\begingroup$ This is not a valid proof that checking $n^3$ identities individually is the only valid algorithm. There may be an algorithm that checks multiple identities at once by using the Cayley table in some smart way. $\endgroup$ – exfret Nov 20 '18 at 21:34
17
$\begingroup$

Using the original $n\times n$ table seems bleak - this is essentially a problem of arity-dimension three, but the Cayley table only gives us two dimensions. However, Light's Associativity Test shows how to systematically reduce the problem of comparing $n$ pairs of Cayley tables. Note that the procedure can be greatly simplified by considering only operations derived from the underlying structure's generators.

$\endgroup$
  • $\begingroup$ Thank you (and also the others). This test works in a mechanical way (copying rows/columns around and comparing tables), so it's alreafy quite close to actually "seeing" the result (one might argue that the only reason why one cannot directly see the result of this test is that the short-time memory of the human brain has not enough capacity). I've chosen to accept your answer because it was slightly earlier than Mark's (which would also have qualified as the accepted answer, but I had to choose one). $\endgroup$ – celtschk Jul 9 '12 at 16:40
  • $\begingroup$ @celtschk Thanks - if that is really your criterion for acceptance, you should accept Mark's answer; his timestamp reads two minutes earlier. $\endgroup$ – user17794 Jul 9 '12 at 16:48
  • $\begingroup$ Ah, I indeed misread the time stamps. Given that you got more votes anyway, and that you yourself suggested changing the accept, I'll change it accordingly (although using the older one was more or less a tie-breaker because I simply cannot accept two answers :-)). $\endgroup$ – celtschk Jul 9 '12 at 17:02
9
$\begingroup$

First of all, let my make a personal reflexion on this matter. Light's associativity test (as others have noted) provides a characterization, but (at least from my point of view) it is not really helpful. Indeed, I like to consider this difficulty to check whether a table is associative as the main reason why it is better to introduce associative operations (in particular groups) through presentations. Then, you trivially get associativity since your "object" is by definition a quotient of the free one.

Now, let me note that in the particular case that the operation is commutative (like the example you have written) then it is known an alternative method which is affordable to be done using a pencil. This (quite unkown in my opinion) method is due to S. KAMAL ABDALI and was introduced in his paper "Verification of Associativity of a Binary Operation" http://www.jstor.org/stable/3613856

I have never seen this method explained in a book, so it is worth to take a look at this paper (in case you can go through the publisher firewall).

$\endgroup$
  • $\begingroup$ Thanks for the reference. Unfortunately the paper is not accessible for me. $\endgroup$ – celtschk Jul 9 '12 at 17:07
  • $\begingroup$ Thank you. You can just add @web.de to by user name to get my email address. However I guess for other interested visitors who will also not be able to access it, a short description of the method would be more helpful. $\endgroup$ – celtschk Jul 9 '12 at 17:25
  • $\begingroup$ Paper sent. Right now I am too busy to write down the details of this method. If you go through the paper I suggest you add the details in an answer to your own post. $\endgroup$ – boumol Jul 9 '12 at 17:29
  • $\begingroup$ Thank you. Since only humans and not spiders can use that comment to determine my email address, I don't see the need to delete it. $\endgroup$ – celtschk Jul 9 '12 at 17:33
  • $\begingroup$ This only seems to reduce the work needed by a constant factor. How is this really any better than just checking each triple individually? $\endgroup$ – exfret Nov 20 '18 at 21:44
6
$\begingroup$

There is a randomized algorithm solving this problem in time proportional to the input size. Specifically, the runtime is $O\left(n^2 \log\frac1\delta\right)$ for an $n \times n$ table and error probability $\delta$. See Rajagopalan and Schulman, FOCS 1996, SICOMP 2000. http://dx.doi.org/10.1137/S0097539797325387

Free download here.

$\endgroup$
  • $\begingroup$ I read and enjoyed this paper. Thanks very much for the reference. $\endgroup$ – MJD Oct 18 '13 at 2:55
  • $\begingroup$ lecture note $\endgroup$ – miracle173 Jul 27 '16 at 21:29
1
$\begingroup$

If I remember correctly, this is explained in W. Keith Nicholson's Introduction to Abstract Algebra. I don't have a copy with me in my office, but I will double-check when I get home.

Edit: I believe that what is being described in the book cited above is exactly Light's Associativity Test, which is mentioned in the other answers.

$\endgroup$
-3
$\begingroup$

A set with an operation used to build a four-dimensional multiplication table with entries $X_{abcd} = (A(BC))D$ is associativ iff $X_{abc1} = X_{1abc}$, with 1 being unity. So it would be a certain three-dimensional symmetry of a four-dimensional table.

$\endgroup$
  • 1
    $\begingroup$ In this notation the above cited test for commutative operations from S. Kamal Abdali cheks the symmetry of the 3D table: $X_{abc} = A(BC)$. It is checked if $X_{abc} = X_{cba}$, and just using only a lower diagonal due to commutative symmetry. For non-commutative operations, one needs to go to the above stated symmetry of a 4D table. $\endgroup$ – Rudi_Birnbaum Nov 5 '15 at 21:29

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.