How many binary operations are associative? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T06:40:55Z http://mathoverflow.net/feeds/question/110211 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110211/how-many-binary-operations-are-associative How many binary operations are associative? Joseph O'Rourke 2012-10-21T03:30:54Z 2012-10-22T05:57:44Z <p>Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each be filled with one of $n$ elements of $X$. My question is:</p> <blockquote> <p>How many of the $n^{n^2}$ binary operations are associative, i.e., $(x \odot y) \odot z = x \odot (y \odot z)$?</p> </blockquote> <p>Unless I miscomputed this, for $n=2$, exactly half of the $2^4=16$ binary operations are associative. But for $n=3$, only $113$ of the $3^9=19,683$ binary operations are associative, a count I do not trust, because it seems so much smaller than I anticipated. (It is difficult to count among the four billion ($4,294,967,296$) binary operations for $n=4$.)</p> <p>I would be interested in the asymptotic growth rate. Surely this is all well known...? Thanks for pointers!</p> <p><b>Update</b>. Following MSE link provided by Darij, I reached (via Gerry Myerson's pointer) the <a href="http://oeis.org/A023814" rel="nofollow">OEIS sequence A023814</a>. The $n=4$ number I couldn't easily compute is $3492$.</p> http://mathoverflow.net/questions/110211/how-many-binary-operations-are-associative/110212#110212 Answer by Michael Biro for How many binary operations are associative? Michael Biro 2012-10-21T03:58:27Z 2012-10-21T03:58:27Z <p>The are bounds known for the number of semigroups on ${1,2,3,\dots,n}$. This is one reference I found (from 1976), no doubt there are better bounds known by now.</p> <p><a href="http://www.jstor.org/discover/10.2307/2041879?uid=3739920&amp;uid=2134&amp;uid=2&amp;uid=70&amp;uid=4&amp;uid=3739256&amp;sid=21101177017183" rel="nofollow">The Number of Semigroups of Order $n$</a></p> http://mathoverflow.net/questions/110211/how-many-binary-operations-are-associative/110215#110215 Answer by Andrej Bauer for How many binary operations are associative? Andrej Bauer 2012-10-21T04:41:01Z 2012-10-21T04:41:01Z <p>For questions like these you can try out <a href="http://math.andrej.com/2011/01/22/alg/" rel="nofollow">alg</a>. It is a program which takes some axioms (it works best for equations) and outputs, or just counts, non-isomorphic models of a given size. It also provides a link to <a href="http://oeis.org/" rel="nofollow">OEIS</a> for you to check the sequence it got.</p> <p>The theory of an associative operation looks like this:</p> <pre><code>Theory associative. Binary *. Axiom: (x * y) * z = x * (y * z). </code></pre> <p>The output says:</p> <pre><code>./alg.native --size 1-4 --count theories/associative.th # Theory associative Theory associative. Binary *. Axiom: (x * y) * z = x * (y * z). size | count -----|------ 1 | 1 2 | 5 3 | 24 4 | 188 Check the numbers [5, 24, 188](http://oeis.org/search?q=5,24,188) on-line at oeis.org </code></pre> <p>The point is, you can easily experiment (of course someone has counted these things before me).</p> http://mathoverflow.net/questions/110211/how-many-binary-operations-are-associative/110276#110276 Answer by Benjamin Steinberg for How many binary operations are associative? Benjamin Steinberg 2012-10-21T23:18:15Z 2012-10-22T00:43:59Z <p>Semigroups form a bigger chunk than you might think. Basically you call a symbol 0 and declare xyz=0 for all elements (making associativity trivial). You still have a huge flexibility on how to define the remaining products. This is the content of the paper Michael links. In fact 99% of all semigroups up to isomorphism and anti-isomorphism satisfy xyz=0. A recent paper of Distler and Mitchell count the exact number of these guys up to isomorphism <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p51" rel="nofollow">http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p51</a>. I think they also count the number of such multiplication tables.</p> http://mathoverflow.net/questions/110211/how-many-binary-operations-are-associative/110283#110283 Answer by Gerhard Paseman for How many binary operations are associative? Gerhard Paseman 2012-10-22T00:22:00Z 2012-10-22T00:30:33Z <p>Here is a guide to the intuition. I will not swear that the numerics are exact, but I will bet that the numerical truth is not far off.</p> <p>Look at the diagonal for the multiplication table of a (labeled) groupoid on $n>3$ elements. Of the n^n possibilities, only one of them is idempotent, so with one exception aa=b will happen for some a and some b different from a. Now all we need for associativity to fail in this case is that ab and ba are different, which will happen for all but n of the n^2 possibilities. So we are already looking at associativity happening only on a small fraction of all (non-idempotent) tables, especially as there are often several candidates for a, and only one is needed.</p> <p>Even for idempotent groupoids, one finds a,b,c distinct and needs to consider only d=ab, g=bc, and the ways in which dc and ag can fail to be equal. Again in rough terms we are talking about n^(-2), and this is just by fixing a,b, and c in advance, and that for the 1 out of n^n tables that are idempotent.</p> <p>I'll let someone else tighten up the numerics. For strengthening Joseph's intuition, I hope this will suffice.</p> <p>Gerhard "Ask Me About 2-Deficient Groupoids" Paseman, 2012.10.21</p> http://mathoverflow.net/questions/110211/how-many-binary-operations-are-associative/110302#110302 Answer by Aaron Meyerowitz for How many binary operations are associative? Aaron Meyerowitz 2012-10-22T05:57:44Z 2012-10-22T05:57:44Z <p>A few curious observations from a very small case:</p> <p>Define the <em>associativity</em> of a binary operation to be the number of triples $a,b,c$ with $(ab)c=a(bc).$ The counts in the case of $n=3$ elements are $52, 12, 96, 276, 504, 468, 628, 936, 966, 1456, 1290, 1266, 1208$$1350, 1212, 1296, 1008, 1212, 840, 939, 732, 596, 432, 369, 168, 198, 60, 113</p> <p>So there are, as noted, 118 with associativity 27 but only 60 with associativity 26. Also, there are 52 with associativity 0 but only 12 with associativity 1.</p> <p>If we count only up to isomorphism/anti-isomorphism (permute 1,2,3 and/or take the transpose of the table giving the operation) then the counts are.</p> <p>5, 1, 8, 23, 42, 39, 53, 79, 81, 130, 108, 113, 103$$ 121, 101, 121, 84, 112, 70, 89, 61, 56, 36, 40, 14, 21, 5, 18$ </p>