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