# How many binary operations are associative?

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

-
math.stackexchange.com/questions/45648/… confirms your 113. –  darij grinberg Oct 21 '12 at 3:57
I should be able to recall this, but my memory is rusty. Two papers come to mind: Ralph Freese's Probability in Algebra, circa 1990, where general algebras besides those with one binary operation are considered (as it turns out, once you go beyond binary,there's not much difference numerically), and work of V.L. Murskii from 1975, showing almost all algebras have a finite basis of identities. Essentially, many properties of finite algebras obey a 0-1 law, and I think associatvity tends toward 0 proportionately as n grows. Gerhard "Ask Someone Else About Associativity" Paseman, 2012.10.20 –  Gerhard Paseman Oct 21 '12 at 3:58
Thanks, Gerhard! Perhaps this? Ralph Freese, "On the two kinds of probability in algebra." Algebra Universalis 27 (1990), no. 1, 70--79. math.hawaii.edu/~ralph/papers.html –  Joseph O'Rourke Oct 21 '12 at 4:04
Darij's link leads to "Associative Operations on a Three-Element Set," by Friðrik Diego and Kristín Halla Jónsdóttir, which indeed confirms my count of $113$ for $n=3$, via an inclusion-exclusion argument. –  Joseph O'Rourke Oct 21 '12 at 4:08
Also in the line is oeis.org/A023814, which gives values up to $n = 7$. –  Michael Biro Oct 21 '12 at 4:10
show 1 more comment

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: Examining the diagonal is insightful! Just to spell it out, in your scenario, $aaa$ has two possible values: $(aa)a = ba$ and $a(aa) = ab$. This dispels my perplexity---Thanks! –  Joseph O'Rourke Oct 22 '12 at 0:54

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

-
I did not know about alg. Thanks! –  Joseph O'Rourke Oct 21 '12 at 14:10
If you get stuck compiling and using it, let me know. –  Andrej Bauer Oct 21 '12 at 23:25

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$

-
Thanks, Michael! –  Joseph O'Rourke Oct 21 '12 at 4:10

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.

-
Thanks, especially, for the remark on "huge flexibility." I remain a bit puzzled at the rarity of associative binary relations, but your remarks are a start at lifting the veil of confusion. –  Joseph O'Rourke Oct 21 '12 at 23:37
More specifically, for a large set S, define a small subset Z with z in Z and any member in Z with any member in S has product z. Now in (S- Z)^2, let any two members have product in Z. One can get a lot of semigroups this way, but I am surprised the percentage is so high. Gerhard "I Will Take Ben's Word" Paseman, 2012.10.21 –  Gerhard Paseman Oct 21 '12 at 23:47
Gerhard, in the paper Michael links they prove that the number of semigroup multiplication tables is asymptotic with the number of 3-nilpotent semigroup tables. It is a long standing conjecture that I guess still has never been rigorously proven that this remains true up to isomorphism. –  Benjamin Steinberg Oct 22 '12 at 1:46
@Benjamin: Maybe I am missing something, but it seems obvious to me that the conjecture trivially follows from the result you claim to have been proved in Michael's link. In other words, if most of tables are 3-nilpotent this is also true up to isomorphism. What am I missing? –  boumol Oct 22 '12 at 13:19
Boumol, my guess is that it is not known how rigid 3-nilpotent semigroups are. If enough of them had trivial automorphism group, then it would follow. Freese's paper above suggests this, but he is talking relative to all tables, not comparing one subset to another, so it does not imply the desired result. Gerhard "Ask Me About Hyperassociative Semigroups" Paseman, 2012.10.22 –  Gerhard Paseman Oct 22 '12 at 13:33
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$