Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Which are all the associative binary operations on natural numbers ? Certain results in this regard can be found in arxiv:math/0508215. It appears that such associative operations cannot grow too fast. Or perhaps, there are also those which have to grow very fast. It is easy to prove that there are infinitely many such associative operations. And in fact, uncountably many, as shown in the mentioned paper. Amusingly, under rather simple natural conditions, the usual addition and multiplication are the only associative binary operations on natural numbers, as wes proved back in 1981, and cited in the mentioned paper. This fact is the motivation for the above question, namely, what happens if we do not ask any conditions on such associative binary operations ? The whole story arose from the observation that certain minimal algebraic and topological axioms determine uniquely the sets on which they hold. An example is the theorem of Pontriaghin proved in the 1930s that the only commutative and algebraically closed field which is not discrete and it is complete is that of complex numbers. And then, one can turn the issue around and ask whether there are simplest infinite sets which determine uniquely some of the algebraic, topological, or other structures on them ? Well, it turns out the the set of natural integers just about determines uniquely addition and multiplication.

share|improve this question
Why not first write down a bijection from the natural numbers to itself that "grows too fast" (e.g. write down a sequence $a_n$ that grows faster than any computable sequence, and then define a bijection swapping 1 and $a_1$, 2 and $a_2$ etc, but not swapping $n$ and $a_n$ if $n$ was $a_m$ for some smaller $m$) and then look at the map on the natural numbers induced by addition, i.e. $a*b=\pi^{-1}(\pi(a)+\pi(b))$ with $\pi$ the bijection$. I don't see any reasonable way of classifying all associative binary ops on the natural numbers. –  Kevin Buzzard Jul 9 '10 at 12:45
The construction you suggest is in the mentioned paper. It seems that my question was not clear enough. So that, let me reformulate it again, this time as an open problem : Characterize all associative binary operations on the natural integers. Or equivalently, characterize all monoidal structures on the natural integers. In the mentioned paper, the two theorems characterize addition in this way. For instance, addition is the only associative binary operation whose iterate is commutative. Or, addition is the only right regular associative operation whose iterate is associative. –  Elemer E Rosinger Jul 9 '10 at 13:15
Some exotic associative operations are listed <a href="math.uni-bielefeld.de/~sillke/PUZZLES/… here</a>. My favorite (with $\phi=(1+\sqrt{5})/2$) is $a\ast b = ab - a\lfloor b \phi\rfloor - b \lfloor a \phi \rfloor$, due to Fraenkel, Stolarsky and Porta. –  Kevin O'Bryant Jul 9 '10 at 13:27
I don't understand. This question is the same as "classify all countable monoids", which is surely an unreasonable question. –  David Speyer Jul 9 '10 at 14:05
Elemer, I think you are trying to ask two different questions. I think we can all agree that there is probably no reasonable classification of countable monoids. But the fact that you keep saying "the natural numbers" instead of "a countable set" indicates to me that you have a different question in mind, which is something like "classify all monoidal structures which interact nicely with some natural structure on the natural numbers," where you have yet to define either "nicely" or "natural structure on the natural numbers." So... which is it? –  Qiaochu Yuan Jul 9 '10 at 20:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.