Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers 4

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.

share|improve this answer
    
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. –  Hurkyl 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
add comment

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

share|improve this answer
    
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
3  
not to the best of my knowledge. –  Ittay Weiss Feb 8 '13 at 11:50
1  
@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. –  B. S. Feb 8 '13 at 15:14
add comment

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)$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.