The algorithm of Rajagoplan and Schulman is easy to describe. It has one-sided error: that is we fix and epsilon > 0. The algorithm runs in time log(1/epsilon)*n^2 (where n is the size of S), and will only fail with probability < epsilon (using random choices). Here's the algorithm: Repeat the following log(1/epsilon) times: Pick 3 independent formal combinations of elements of S with coefficients in Z mod 2. Call them a, b, c. Verify that a(bc) = (ab)c, where the multiplication is done via formal linear combinations. If S isn't associative, with probability at least (1-epsilon)^log(1/epsilon) it will detect it this way. Victor On Tue, Aug 19, 2014 at 7:41 PM, Victor Miller <victorsmiller@gmail.com> wrote:
It looks like "Verification of Identities" by Rajagoplan and Schulman seems to be the best algorithm known:
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A29F9C99B65004A490D...
On Tue, Aug 19, 2014 at 7:21 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
The word you want is semigroup: http://en.wikipedia.org/wiki/Semigroup
Well, there is this: http://en.wikipedia.org/wiki/Light's_associativity_test
And you might find something of interest in the reference to this OEIS entry: number of semigroups of order n http://oeis.org/A001423
On Tue, Aug 19, 2014 at 9:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun