The associative:commutative crossover is at N=406. Commutatives are more numerous for 3 <= N <= 405. I think N = 1,2 are equinumerous tables; unsure about after-isomorphisms-and-anti-isomorphism-removal case. (This distinction doesn't affect the 406 crossover, since the correction for isomorphisms is roughly to divide both counts by N!. The absense of anti-isos for the comm case (a factor of 2) doesn't move the crossover.) I haven't proved that dull semigroups are 100%-epsilon of all semigroups, but agree with CGB that it's obvious from looking at the lists of tables. I noticed this when I looked at size 7 semigroups. I think that semigroup counters today split out the dull case. A natural measure of "constraint" imposed by an equation like a.bc=ab.c is log_N(# of constrained NxN tables) / N^2. By this measure, commutative tables are .5, and dull semigroups are 1, for large N. Moreover, the same idea works for more complicated equations like ab.cd = ac.bd; the dull construction (CGB sketch below) works with more layers, and surpasses semigroups for large N. I think this is surprising and interesting, but it's a wet blanket when you're hoping universal algebra will turn up interesting new math operations: There's a big pile of trash to discard. Rich ------ Quoting "Christian G. Bower" <bowerc@usa.net>:
Some time ago Rich proposed the concept of "dull semigroup" defined as a(bc) = (de)f for all a,b,c,d,e,f that did a good job of characterizing the asymptotic behavior of semigroups. I'm not sure how to prove it, but it's fairly obvious that # dull semigroups / # semigroups rapidly goes to 1. Rich showed that while commutive initially grows faster than associative, associative eventually outgrows commutative and calculated when. (I think it was somewhat above n=100).
Dull semigroup is essentially where every product of 3 elements is the 0 element. Thus we must have a zero element (0x = x0 = 0 for all x). There is a set of elements Z that produce 0 in any product, i.e. if z in Z zx=xz=0 for all x. All products produce an element of Z.
------ Original Message ------ Received: Tue, 19 Aug 2014 08:49:18 PM PDT From: Henry Baker <hbaker1@pipeline.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Stupid associativity question
Sorry, one additional question:
3. how constraining is associativity, in the sense of reducing the number of different operators? E.g., commutativity cuts out nearly half of the degrees of freedom; what % of the degrees of freedom does associativity cut out ?
At 06:02 PM 8/19/2014, Henry Baker 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