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.

  • 0
    @Doug: If I got any of your notation wrong, let me know or edit as you see fit.2011-06-16
  • 0
    Looks good, thanks Jack!2011-06-16
  • 9
    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).2011-06-16
  • 4
    @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.2011-06-16
  • 2
    @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.2011-06-16
  • 0
    @Doug: Halmos is describing things as they *are*. If you are wondering why things are one way and not another, then that's *your* wondering, and saying that Halmos doesn't "literally mean what he says", or that "there's something amiss with what he says" is to blame Halmos for reality. As to nonassociative operations being "sought out" I repeat: we *all* deal with nonassociative operations all the time; every time we divide, subtract, or take exponents. Your feeling fails the test of reality in view of $-$ and $\div$.2011-06-16
  • 0
    @Arturo But see, since we all deal with nonassociative operations all the time, contrary to Halmos, one can say that the mathematical community has learned to live with the fact and enjoy the fact that many operations don't associate. Also, since many people use division, subtraction (I here grant the assumption that division and subtraction as binary operations, though one can treat them as unary operations if e. g. a-b means a+-b), and exponentation, violations of the associative law get considered by more people than just specialists. So, Halmos isn't describing a state of reality.2011-06-17
  • 0
    @Doug: Halmos *nowhere* says we don't *deal* with nonassociative operations. He says that their *study* tends to be restricted to specialists. I would urge you to be careful with your reading when you are going to criticize (or is that "denigrate"?) the words of others.2011-06-17
  • 0
    @Doug: No, subtraction is not a unary operation. Subtraction can be dealt with as the *composition* of a unary operation (inversion) and a binary operation (addition), but it is not itself a unary operation. Same with division. Division is a binary operation, though it can be defined as a composition of a unary and a binary operation.2011-06-17
  • 0
    @Arturo Almost everyone who studies classical (non-abstract) algebra *studies* subtraction, division, and exponentation. So, the study of nonassociative operations simply isn't restricted to specialists. I like what you said in your second comment, distinguishing between subtraction and taking the negative (or inversion as you say) of a number makes good sense.2011-06-17
  • 4
    @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...2011-06-17
  • 0
    @Arturo Yes they do study subtraction in the same sense, as they study concrete examples just like how group theorists or ring theorists sometimes study concrete examples.2011-06-17
  • 0
    @Arturo Additionally, Halmos doesn't use the term "study". He says "considered". Non-associative operations do get considered by non-specialists to an appreciable degree.2011-06-17
  • 2
    @Doug: Clearly, you don't understand the point of Halmos's statement, nor do you understand what it means to study or "consider" (in the sense that Halmos uses it) an operation. You are equivocating. As such, your opinions and a subway token will get you a ride in the subway, but not much else.2011-06-17
  • 0
    @Arturo It's by no means clear, since I've disagreed with you on this. You can claim that I don't understand all you like, but you have little more knowledge on my mind-state than that I just disagree with Halmos. The rest of the paragraph goes "Having made the point that the associative law deserves respect, this book will concentrate in the sequel on associative operations only. The next job is to see what other laudable properties such operations can and should possess." In light of the extreme rarity of associative operations in general, I don't see a reason to praise or respect them.2011-06-17
  • 2
    @Doug: I have all the knowledge of your statements, your equivocations, your assertions, and the history of our interactions. Kindly don't project your ignorance on others. You will, I am positive, continue to believe whatever you want to believe regardless of facts, because you have shown this to be the case in the past. I do have to wonder what it is you hope to accomplish here, unless you are hoping people will laud what you think is your keen insight.2011-06-17
  • 1
    @Arturo I would hope what I generally want to accomplish here as readily inferred from what I've written. There exist several things that can get inferred. One of them goes roughly as follows... "If 1. associative operations are in general very, very rare, and if 2. most of the mathematical community concentrates most of its time on studying mathematical systems where associativity holds, then most of the mathematical community concentrates on a very, very small part of mathematical systems." To enjoy more mathematics, it would behoove one to enjoy more non-associative operations.2011-06-17
  • 2
    @Doug It's flabbergasting how you can, in one breath, argue for a broader view, while consistently insisting on reading other people as myopically as possible in order to score empty rhetorical points. As to your final claim, while it is certainly *one* way to enjoy "more mathematics" (in the pedestrian, silly sense of "more"), it is hardly the only way, so your "behooving" is a nonsequitur. I would say: go ahead and enjoy them to your heart's content, but why do you feel the need to get other people to agree with you first?2011-06-17
  • 1
    @Arturo I haven't read Halmos as myopically as possible. You seem to have forgotten that I said "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." The "behooving" part isn't a non-sequitur, since it follows from such a desire and the rarity of non-associative operations. I wouldn't say I feel a need to get other people to agree with me. But, it certainly makes sense to argue for one's position if one has a ground for it, and indicate that such a ground exists.2011-06-17
  • 1
    @Doug It makes little sense to argue for one's position when nobody is arguing against it, unless one is so insecure that one needs express approval. Nobody says you *shouldn't* study nonassociative operations; Halmos is arguing *for* associative ones, not *against* nonassociative ones. If there were a position that someone is arguing against, it would be precisely the position that one should *not* study associative ones (Again, Halmos is justifying his restriction). It is only your myopic reading that suggests otherwise.2011-06-17
  • 1
    @Arturo Also, in light of the rarity of non-associative operations in general (2-element sets seem the only real exception for finite sets), that so many algebraic textbooks seem to make groups, rings, and fields the central structures of algebra seems rather strange, as, in general, so many more algebras aren't even semigroups. Why do I feel the need to point that out? Because by emphasizing the unusual cases of semigroup structures, it almost seems like the exceptional case has become commonplace. But, it hasn't. The forest has gotten missed for one or two trees.2011-06-17
  • 2
    @Doug: Actually, you are the one missing the forest for the trees. To concentrate exclusively on *quantity* without regard for applicability is to miss the forest for the trees; while one can certainly construct lots and lots of ad-hoc nonassociative operations, one naturally encounters a lot of associative ones. By your argument, Number Theory is a waste of time, given the rarity of algebraic numbers as opposed to transcendental ones, completely ignoring the facts on the ground. Your positions simply fail the test of reality, just like your arguments about formal proofs being 'safer'.2011-06-17
  • 0
    @Arturo See, but on what ground does Halmos argument *for* associative operations stand in light of their extreme rarity in general? That the mathematical community studies them more often than nonassociative ones? But, if but one of the implied conjectures of the OP holds, the mathematical community as a whole then can get said to study a very small part of algebra in general. So Halmos doesn't seem to have such a good ground for such an argument in terms of learning algebra in general, since so relatively few algebraic structures satisfy associativity.2011-06-17
  • 0
    @Arturo: Because a *lot* of the operations that naturally occur in the study of physical phenomenon (including composition of functions) *are* associative. Because their study has proven fruitful and useful. Because that's what reality is. But since you only argument seems to be one of *quantity*, it is clear that this is irrelevant to you. Again, by your argument, studying algebraic numbers is a waste of time given their extreme rarity, a silly proposition at best. Again: reality continues to disagree with what you think reality "should" be. But you'll keep your position, regardless.2011-06-17
  • 0
    @Arturo I haven't exclusive concentrated on quantity. Didn't you see that the original post talked about a *ratio*? Such a ratio isn't a quantity, but a relationship between quantities. Yes, one can encounter a lot of associative operations, but I haven't denied such. I've indicated them as rare *relative* to all operations. Though I would deny number theory as a waste of time, given cardinality as an appropriate measure, number theory comes as less important than approximating transcendental numbers. This isn't ignoring the facts, since approximations play a more important role in...2011-06-17
  • 1
    @Doug: And yet again, you engage in myopic reading in order to score empty rhetorical points. Since it seems that all you want is empty pats in the head to tell you how clever and keen you are, have one: it's as worthless as the empty complaints and empty points.2011-06-17
  • 0
    @Arturo applied mathematics. I don't know if I claimed formal proofs as "safer". However, you and I DID resolve something about the formal proof I gave rather quickly, and I managed to patch it up. So, looking at the formal proof ended up more useful, since it seemed to lead to a resolution of the issue faster. A lot of operations occuring in conventional studies of physical phenomenon may indeed associate. However, this says nothing about reality itself. It may well end up that non-associative models used to study reality reveal a lot more about reality than one might expect.2011-06-17
  • 2
    @Doug and it may end up that pigs fly. Nobody is stopping you (or any of the people who do research in magmas and loops, both of which involve nonassociative operation) to studying whatever you want to yours heart's content. But you seem to think that the only way in which you can justify your preferences is by denigrating anyone who does not share them, and *that* is rather sad.2011-06-17
  • 0
    @Arturo You have in no way shown my reading myopic, and merely stated your opinion there. Rhetorical points? I don't see how I've scored any, as it seems I haven't convinced you of anything.2011-06-17
  • 0
    @Arturo I don't see how I've really denigrated anything. I've suggested that objectively speaking semigroup structures happen very rarely relatively speaking in terms of mathematical structures (unless the suggested conjectures of the OP basically don't hold). I doubt many algebra books indicate this. Why wouldn't they? The prevalence of non-associative operations suggests that even if conventional models of reality use associative operations, that far more many models can get worked out which behave otherwise.2011-06-17
  • 0
    @Doug: You engage in myopic reading when you take my statement about "quantity" and say "I refered to ratios of quantities, not quantities themselves". Talking about the ratio is just another way of measuring quantity, and to pretend otherwise is silly; and you pretended otherwise. As for geese and gander, your *opinion* that I have "in no way shown [your] reading to be myopic" is duly noted, as is the fact that you make the statement as if it were a fact while complaining that others do that. Finally, your inability to actually *score* the cheap points does not deny your *attempts* at them.2011-06-17
  • 5
    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.2011-06-17
  • 0
    @Arturo A ratio of associative operations to the total number of operations does not measure the number of associative operations. It measures the proportionality of associative operations to operations in general for an n-element set. It's NOT the same as measuring something which in principle can get determined purely via counting. Talking about a ratio is not just another way of measuring quantity, but a specific type of measuring quantity. Not all quantitative arguments are similar. You keep on projecting on to me that I've tried to score points here, when I haven't.2011-06-17
  • 1
    @Doug Tell you what: continue pretending that you were not making a quantitative argument all you want, and you may even come to believe it some day. I'm out.2011-06-17
  • 1
    @Arturo That sure does seem like a lot of speculative psychological analysis there. Also, if a question isn't simply just an interrogative sentence, what is a question to begin with? Additionally, I don't see why you appear to think that I think that I did something clever when I asked the question about truth tables. The question got voted down, and the answer provided indicated the responder thought it wouldn't have all too much use.2011-06-17
  • 0
    @Arturo Thinking more on this, I do believe I made a quantitative argument. But, I don't believe it the same type of quantitative argument that you thought I was making.2011-06-17
  • 0
    See paper in **International Journal of Essential Sciences** pp 1-8 Vol 5 2011 by Amit Sehgal & Manhohan, Assocative binary operation for three element set2012-03-08

2 Answers 2

25

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.

  • 1
    @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.2011-06-19
  • 2
    @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.2011-06-19
  • 1
    @user6312 Thanks. Nice inequality!2011-06-19
  • 1
    @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!2011-06-19
  • 0
    @user6312 Your inequality implies that $R_{n}$ is greater than $R_{n+1}$ for n greater than 0 (the difference of (2n-1)/n^2 and (2(n+1)-1)/(n+1)^2 is positive). If I've gotten things right, this implies F as monotonically decreasing everywhere but from 0 to 1.2011-06-19
  • 0
    @user6312 Scratch that. That doesn't work.2011-06-19
  • 1
    @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.2011-06-19
6

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.

  • 0
    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!2011-06-16
  • 0
    @Doug, PS stands for PostScript. If you type "opening postscript files" into a search engine it should give you many useful links.2011-06-16
  • 0
    @Doug [GhostScript](http://pages.cs.wisc.edu/~ghost/) should provide everything you need.2011-06-16