Associativity for Magma

Say I have the operation table for a magma. I want to know whether or not the operation is associative. However, associativity is defined for an operation on 3 elements, and the operation table deals only with two. So it is not clear to me how to determine whether operation is associative by looking only at the table. Is it possible, or does one just need to try every combination of three elements by brute force?

In the absence of any further information then, yes, you need to check every triple. There is a theorem (due to G. Szasz) which asserts that on any set with at least four elements, there is a binary operation for which there is exactly one non-associative triple. (In fact, there are such operations on three-element sets also; $10$ of them, up to isomorphism.)

A reference for the Szasz theorem is:

@ARTICLE{Szasz1953,
AUTHOR = {G. Szasz},
TITLE = {{D}ie {U}nabh\"{a}ngigkeit der {A}ssoziativit\"{a}tsbedingungen},
JOURNAL = {Acta Sci. Math. Szeged},
VOLUME = {15},
YEAR = {1953},
PAGES = {20--28},
LANGUAGE = {German},
REVIEW = {\MR{56575 (15,95d) 09.1X}},
}


I should add that I've not actually seen this paper. (I've never found it online, and I don't read German anyway.) However, the proof is not difficult. Suppose you have a set $S$ with four distinct elements $a$, $u$, $v$ and $w$. Define the binary operation $\cdot$ on $S$ by putting $a\cdot a = u$, $a\cdot u = v$, and $x\cdot y = w$, for all pairs $(x,y)$ other than $(a,a)$ and $(a,u)$. Then it is easy to see that $(a\cdot a)\cdot a\neq a\cdot(a\cdot a)$. It is then tedious, but completely elementary to check (case by case, as it were) that every other triple does associate.

• I'd be really interested in a link or other reference. – Eric Stucky Feb 8 '13 at 17:43
• @EricStucky I've added a reference to the Szasz paper, and the guts of the proof. – James Feb 8 '13 at 18:08
• If you know $((ab) c) d = (ab)(cd)$, $a((bc)d) = (a(bc))d$, $b(cd) = (bc)d$, and $(ab)c = a(bc)$, then it automatically follows that $a(b(cd)) = (ab)(cd)$. So, in principle, you don't have to check every triple if you can arrange to check equations that imply other equations. – user14972 Mar 28 '13 at 8:07
• @EricStucky There is also a proof in Rajagopalan and Schulman "Verification of Identities" (1997). – MJD Nov 27 '13 at 16:28
• @Hurkyl The apparent discrepancy to Szasz's result is explained by the fact that he essentially uses only a black box that can check for any triple $(x,y,z)\in S^3$ whether or not $x(yz)=(xy)z$ without looking at the intermediate results. Your remarks goes in the direction of Light's test with a generating set. – Hagen von Eitzen Dec 11 '13 at 16:00

Generally, checking for associativity can be computationally very difficult. There are no easy visual criteria on the multiplication table to discern associativity.

• Thanks. Do you know if there are conditions for non-associativity. Where you can see from the table that it's definitely not associative? – Matthew Matic Feb 8 '13 at 11:45
• not to the best of my knowledge. – Ittay Weiss Feb 8 '13 at 11:50
• @MatthewMatic:If your structure is finite, so maybe there is a way to check the associativity by using GAP. If you'd like, give me that structure. Perhaps, I can make a code to verify it. – mrs Feb 8 '13 at 15:14
• @IttayWeiss, there is a geometric interpretation via commutativity on Stasheff polytopes aka en.wikipedia.org/wiki/Associahedron – alancalvitti Dec 6 '14 at 14:19
• @alancalvitti what does the associahedron have to do with any of this??? – Ittay Weiss Dec 6 '14 at 18:39

In Rajagopalan and Schulman "Verification of Identities" (1997), an algorithm is given that probabilistically checks whether a given operation $\circ$ on a set $S$ is associative. If the operation is nonassociative, the test detects this fact with with any desired probability $\delta$ in $$O(\kappa n^2\log\delta^{-1})$$ time, where $n=|S|$ and$\kappa$ is the time to calculate $\circ$ for one pair of arguments. A variant of the algorithm will generate a specific triple $\langle a,b,c\rangle$ for which $(a\circ b)\circ c\ne a\circ (b\circ c)$, when one exists, in time $$O(\kappa n^2\log n\log \delta^{-1}).$$

This algorithm works for arbitrary operations. Unlike Light's test, it works even for "noncancellative" operations, where the equations $x\circ a = b$ and $a\circ x = b$ may not have solutions for all given $a,b$.

The paper also shows that if the operation $\circ$ is cancellative, one can compute a small ($O(\log n)$)set that generates it in time $O(n^2)$, and then apply Light's test to deterministically verify associativity in total time $O(\kappa n^2\log n)$.

A method to structure the checking of associativity is Light's associativity test. It doesn't improve the speed of the algorithm (nor can it, as James' answer shows), but it should make you less cross-eyed.

More on this subject can be found in this answer.

As somebody already wrote, there are some tests that can be done (this wikipedia page links to the same other one cited by @yatima2975).

Personally, I am interested in these matters but I only know sufficient conditions over the Cayley table, for associativity.

If it may help, this is a simple draft of Matlab script to check associativity by brute force (see @James's answer also):

disp('ASSOCIATIVITY TEST FOR A FINITE MAGMA OF ORDER n, WITH ELEMENTS 1,2,...,n, WHOSE CAYLEY TABLE IS GIVEN.');
n=input('Insert the order of the groupoid, n: ');
A=zeros(n);
for i=1:n
r=zeros(1,n);
r=input('Insert Cayley table line as [a_1,...,a_n]: ');
A(i,:)=r;
end
disp('The Cayley table is:');
disp(A);
B=zeros(n,n,n);
for i=1:n
for j=1:n
for k=1:n
if A(A(i,j),k)==A(i,A(j,k))
B(i,j,k)=1;
end
end
end
end
if B==ones(n,n,n)
disp('*** THIS MAGMA IS A SEMIGROUP ***');
else
disp('*** THIS MAGMA IS NOT A SEMIGROUP ***');
end