How many binary operations are associative? - MathOverflow

How many binary operations are associative?

2012-10-21T03:30:54Z

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:

How many of the $n^{n^2}$ binary operations are associative, i.e., $(x \odot y) \odot z = x \odot (y \odot z)$?

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

I would be interested in the asymptotic growth rate. Surely this is all well known...? Thanks for pointers!

Update. Following MSE link provided by Darij, I reached (via Gerry Myerson's pointer) the OEIS sequence A023814. The $n=4$ number I couldn't easily compute is $3492$.

Answer by Michael Biro for How many binary operations are associative?

2012-10-21T03:58:27Z

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.

The Number of Semigroups of Order $n$

Answer by Andrej Bauer for How many binary operations are associative?

2012-10-21T04:41:01Z

For questions like these you can try out alg. 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 OEIS for you to check the sequence it got.

The theory of an associative operation looks like this:

Theory associative.
Binary *.
Axiom: (x * y) * z = x * (y * z).

The output says:

./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

The point is, you can easily experiment (of course someone has counted these things before me).

Answer by Benjamin Steinberg for How many binary operations are associative?

2012-10-21T23:18:15Z

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 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p51. I think they also count the number of such multiplication tables.

Answer by Gerhard Paseman for How many binary operations are associative?

2012-10-22T00:22:00Z

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.

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.

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.

I'll let someone else tighten up the numerics. For strengthening Joseph's intuition, I hope this will suffice.

Gerhard "Ask Me About 2-Deficient Groupoids" Paseman, 2012.10.21

Answer by Aaron Meyerowitz for How many binary operations are associative?

2012-10-22T05:57:44Z

A few curious observations from a very small case:

Define the associativity 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$

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

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.

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