31
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ math.stackexchange.com/questions/45648/… confirms your 113. $\endgroup$ Oct 21, 2012 at 3:57
  • 2
    $\begingroup$ 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 $\endgroup$ Oct 21, 2012 at 3:58
  • $\begingroup$ 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 $\endgroup$ Oct 21, 2012 at 4:04
  • $\begingroup$ 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. $\endgroup$ Oct 21, 2012 at 4:08
  • 3
    $\begingroup$ Also in the line is oeis.org/A023814, which gives values up to $n = 7$. $\endgroup$ Oct 21, 2012 at 4:10

5 Answers 5

5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @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! $\endgroup$ Oct 22, 2012 at 0:54
15
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I did not know about alg. Thanks! $\endgroup$ Oct 21, 2012 at 14:10
  • $\begingroup$ If you get stuck compiling and using it, let me know. $\endgroup$ Oct 21, 2012 at 23:25
6
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Oct 21, 2012 at 23:37
  • $\begingroup$ 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 $\endgroup$ Oct 21, 2012 at 23:47
  • $\begingroup$ 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. $\endgroup$ Oct 22, 2012 at 1:46
  • $\begingroup$ @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? $\endgroup$
    – boumol
    Oct 22, 2012 at 13:19
  • 2
    $\begingroup$ 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 $\endgroup$ Oct 22, 2012 at 13:33
4
$\begingroup$

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$

$\endgroup$
0
1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ If you did even partialsats for n=4, I would find that of interest. I am most intrigued by the columns that have equal counts (1212 and 121l. It makes me wonder if there is a special morphism at work. Gerhard "Ask Me About Numerical Coincidence" Paseman, 2012.10.22 $\endgroup$ Oct 22, 2012 at 17:31
  • $\begingroup$ Oops. Partial Stats. Gerhard "Should Read What I Write" Paseman, 2012.10.22 $\endgroup$ Oct 22, 2012 at 17:32
  • $\begingroup$ Some extended stats are 14, 1212, 101, [[12, 101]] AND 17, 1212, 112, [[6, 22], [12, 90]] Meaning that the associativity 14 laws are in 101 orbits each of size 12 while the associativity 17 laws are in 112 orbits, 22 of size 6 and the rest of size 12. $\endgroup$ Oct 22, 2012 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.