Associativity test for a 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?
 A: 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: Generally, checking for associativity can be computationally very difficult. There are no easy visual criteria on the multiplication table to discern associativity. 
A: 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.
A: 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.
A: 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

