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

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ math.stackexchange.com/questions/45648/… confirms your 113. $\endgroup$
    – darij grinberg
    Commented 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$
    – Gerhard Paseman
    Commented 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$
    – Joseph O'Rourke
    Commented 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$
    – Joseph O'Rourke
    Commented Oct 21, 2012 at 4:08
  • 3
    $\begingroup$ Also in the line is oeis.org/A023814, which gives values up to $n = 7$. $\endgroup$
    – Michael Biro
    Commented Oct 21, 2012 at 4:10

5 Answers 5

Reset to default
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

Improve this answer
$\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$
    – Joseph O'Rourke
    Commented 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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I did not know about alg. Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Oct 21, 2012 at 14:10
  • $\begingroup$ If you get stuck compiling and using it, let me know. $\endgroup$
    – Andrej Bauer
    Commented 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.

Improve this answer
$\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$
    – Joseph O'Rourke
    Commented 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$
    – Gerhard Paseman
    Commented 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$
    – Benjamin Steinberg
    Commented 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
    Commented 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$
    – Gerhard Paseman
    Commented 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$

Improve this answer
$\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$

Improve this answer
$\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$
    – Gerhard Paseman
    Commented Oct 22, 2012 at 17:31
  • $\begingroup$ Oops. Partial Stats. Gerhard "Should Read What I Write" Paseman, 2012.10.22 $\endgroup$
    – Gerhard Paseman
    Commented 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$
    – Aaron Meyerowitz
    Commented Oct 22, 2012 at 19:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .