15
$\begingroup$

I started thinking about the number of associative (binary) operations on a set with $n$ elements today. Looking online I found this paper which indicates only $113$ of the possible $19,683$ operations on a three-element set satisfy association. So, $50\%$ of binary operations on a two-element set satisfy association, and less than $0.6\%$ of all binary operations on a three element set satisfy association. For an $n$-element set, where $n$ denotes a natural number, is the ratio $R_{n}=A_{n}/B_{n}$, of the number of associative binary operations $A_{n}$ to the number of all binary operations $B_{n}$, in general small? I don't mean the following questions as equivalent, but since they seem more concretely answerable in principle, does

$$ \lim_{n \to +\infty} \frac{A_{n}}{B_{n}} = 0 ? $$

Also, is $F : n \to R_{n}$ a monotonically decreasing function?

Some Background of the Question: In his Linear Algebra Problem Book 1995 on p. 6 Paul Halmos writes "The commonly accepted attitudes toward the commutative law and the associative law are different. Many real life operations fail to commute; the mathematical community has learned to live with that fact and even to enjoy it. Violations of the associative law, on the other hand, are usually considered by specialists only." For all I know, Halmos might only have written that to motivate the study of Linear Algebra and doesn't quite literally mean what he appears to say. But, if he means what he appears to say, and if $F : n \to R_{n}$ is monotonically decreasing, or $R_{n}$ is generally small, I think there's something amiss with what Halmos says, since non-associative operations seem so common that one may as well enjoy them.

|cite|improve this question
$\endgroup$
  • 9
    $\begingroup$ I disagree with your reading of what Halmos is saying; he is describing a state of affairs about how mathematicians deal with operations, not a statement about "how many" operations are or are not associative. Fact is, while mathematicians in general don't think twice about noncommutativity, and many actively seek it out (rings theorists, for example), few people actively seek out nonassociative operations to study (only specialists generally, e.g. dealing with loops, magmas, etc). Not that they are rare (hell, subtraction and division are not associative). $\endgroup$ – Arturo Magidin Jun 16 '11 at 4:24
  • 4
    $\begingroup$ @Doug, we always prefer the rare to the common. We study the primes, not the composites; the subspaces, not the subsets of a vector space that aren't subspaces; the differentiable functions, the right-angle triangles, etc., etc., ad nauseam. $\endgroup$ – Gerry Myerson Jun 16 '11 at 7:22
  • 2
    $\begingroup$ @Arturo I don't mean to say that Halmos says something about "how many" operations are or are not associative relative to the total number of operations on an n-element set. But, I don't see why would one think twice about studying nonassociative operations or that one wouldn't enjoy them, since they aren't rare. Why aren't nonassociative operations more sought out? I have a feeling it has to do with the ubiquitous selection of an infix notational scheme and little more than that. $\endgroup$ – Doug Spoonwood Jun 16 '11 at 12:18
  • 4
    $\begingroup$ @Doug: People who study classical algebra don't study subtraction in the same sense that a group theorists or a ring theorist does. If you have to rely on equivocation to make your point, perhaps you don't have a point to make... $\endgroup$ – Arturo Magidin Jun 17 '11 at 4:25
  • 5
    $\begingroup$ So far, you have asked 10 questions in the forum. Five have been of the form "Why do people do X, when it is clear from your personal considerations that they should do/say Y instead?" (with a sixth possibly falling in the same category). One other was "X says this. Is that really true?" And one was "I did this clever thing! Does anyone know if I've been scooped?" You don't seem to be asking questions, you seem to be searching for either reassurance or praise. $\endgroup$ – Arturo Magidin Jun 17 '11 at 18:55
25
$\begingroup$

After getting a PhD at Har-cago, Allie got a job setting up the daily Binary Operation Table on the set $\{1,2,\dots, n\}$.

Every day Allie started by choosing $1 \circ 1$ at random, with all choices equally likely. Whatever $1 \circ 1$ turned out to be, say $x$, Allie then chose at random the value of $x \circ 1$ among the legal choices. (Of course, if by luck it turned out that $x=1$, then $x \circ 1$ was already determined.)

It would be pointless to try to describe the rest of Allie's procedure, as it tended to change from day to day. But the first two steps were always as described.

After the first two steps, Allie always checked whether or not the operation was (so far) associative. If the first choice was $1\circ 1=1$ (probability: $1/n$) we have automatic associativity, that is, associativity with probability $1$.

Otherwise (probability: $1-1/n$), if $1\circ 1=x \ne 1$, the operation is associative precisely if $x \circ 1=1\circ x$. For any $x \ne 1$, this probability is $1/n$. So the probability that $(1\circ 1)\circ 1=1\circ(1\circ 1)$ is $$\left(\frac{1}{n}\right)(1) +\left(1-\frac{1}{n}\right)\left(\frac{1}{n}\right)$$ This simplifies to $(2n-1)/n^2$.

But this probability is $\ge A_n/B_n$, where $A_n$ and $B_n$ are defined as in the post. Thus $$\frac{A_n}{B_n} \le \frac{2n-1}{n^2}$$

In particular, $A_n/B_n$ approaches $0$ as $n$ gets large.

The inequality we have obtained is tight at $n=1$, but absurdly weaker than the truth for large $n$. One could produce much improved estimates, and undoubtedly there is even a modest literature on the subject.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ @user6312 I love your creative response how you start with a nice story. But, I simply don't see how 1*1=1 implies associativity automatically. 1*1=1 implies associativity if any one of {x, y, z} in xyzAA and xyAzA, equals 1. But, say we have {1, 2, 3} as the carrier, and omitting the operation A we have 11=1, 12=1, 13=1, 21=1, 22=1, 23=2, 31=1, 32=2, 33=2. Then association fails since 33A2A=22A=1, and 332AA=32A=2. That said, I sincerely hope I've misunderstood you here. $\endgroup$ – Doug Spoonwood Jun 19 '11 at 0:33
  • 2
    $\begingroup$ @Doug Spoonwood: I thought that I made it clear that by associativity I meant "associativity so far," or to put it another way, not yet a breakdown of associativity. I show that associativity breaks down with high probability (exactly $1-(2n-1)/n^2$) by the time we have decided on $1\circ1$ and $x \circ 1$, where $x$ is what we chose for $1\circ 1$. Once associativity has broken down in even one instance, it cannot be rescued by later decisions about $a \circ b$. That is why one can say that with probability $\le (2n-1)/n^2$, a binary operation on a set of $n$ elements is associative. $\endgroup$ – André Nicolas Jun 19 '11 at 0:50
  • 1
    $\begingroup$ @user6312 Thanks. Nice inequality! $\endgroup$ – Doug Spoonwood Jun 19 '11 at 2:52
  • 1
    $\begingroup$ @Doug Spoonwood: Weak inequality! Could do much better by tracing through what happens with $1$ and $2$. There may be the possibility of a nice inclusion-exclusion argument, for a more globally based estimate. So many problems, so little time! $\endgroup$ – André Nicolas Jun 19 '11 at 3:25
  • 1
    $\begingroup$ @Doug Spoonwood: Monotonicity does not follow from the bound on the ratio. Your conjecture about monotonicity is however undoubtedly correct. But it would be more interesting to try to replace the $o(1/n)$ bound with something far stronger. $\endgroup$ – André Nicolas Jun 19 '11 at 19:50
6
$\begingroup$

The number of associative binary operations on an $n$-element set is given at http://oeis.org/A023814

Perhaps you could follow the links at that page and report back to us.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Well, the first link has numbers only for 0-7 element sets (which no doubt still took quite a bit of effort to figure out). 3492/4^16=.000 000 813 according to my calculator, which I don't know exactly how accurate that is, at least indicates a huge drop in the "density" of associative operations (the ratio above) from a 3 element set to a 4-element set. Unfortunately, I haven't figured out how to open a PS file yet. Thanks! $\endgroup$ – Doug Spoonwood Jun 16 '11 at 3:01
  • $\begingroup$ @Doug, PS stands for PostScript. If you type "opening postscript files" into a search engine it should give you many useful links. $\endgroup$ – Gerry Myerson Jun 16 '11 at 3:08
  • $\begingroup$ @Doug GhostScript should provide everything you need. $\endgroup$ – Jack Henahan Jun 16 '11 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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