# Find number of binary operations on $S$

Let $S=\{1,2,\ldots,11\}$. Find number of binary operations $\circ:S\times S\rightarrow S$ such that $\circ$ is commutative, associative, and $$a\circ b=a\circ c\Rightarrow b=c,$$ $$ab\leq11\Rightarrow a\circ b=ab.$$

I can only approach this problem by listing all $ab>11$, which becomes undoably tedious, so I'm stuck. I'm wondering if there is any theorem or technique that I can apply to this problem.

• It's associative, has an identity element ($1\circ a=a$ for all $a$), and has cancellation. Can it be anything other than the group operation on a group of 11 elements? – Gerry Myerson Sep 7 '16 at 13:27
• There is a result that the number of different binary operations defined on a finite set $S$ such that $|S|=n$ is $n^{n^2}$ and the number of commutative binary operations on $S$ is $n^{\frac{n(n+1)}{2}}$. – StubbornAtom Sep 7 '16 at 13:31
• @StubbornAtom But there are two other restrictions. How do I do this then? – Colescu Sep 7 '16 at 13:38
• That is what we have to think about. – StubbornAtom Sep 7 '16 at 13:40
• @YuxiaoXie: Look at Gerry Myerson’s hint: he practically told you the answer. – Brian M. Scott Sep 7 '16 at 17:36

Maybe there's an elegant solution, but this is messier than I expected it to be. If I haven't missed any cases, I get 14 different binary operations satisfying the required property. (Of course, there's only one solution up to isomorphism, but that's not what the problem asked for.)

First observe that $\langle S, \circ\rangle$ is an Abelian group. We already know that it's associative and commutative. The rule that $ab\leq11\Rightarrow a\circ b=ab$ implies that $1$ is an identity. So all that's left to show that $S$ is an Abelian group is that every element has an inverse.

But if $a$ is any element of $S,$ then the cancellation law tells us that the function $x \to a \circ x$ is one-to-one. Any one-to-one function from a finite set to itself must be onto. So there exists some $x\in S$ such that $a\circ x = 1.$ By commutativity, $x$ is an inverse of $a.$

So $S$ is an Abelian group. Since it's of prime order, it must be cyclic.

If $G$ and $H$ are any two cyclic groups of prime order, and if $a\in G$ and $b \in H$ are not the identity (in their respective groups), then there is a unique isomorphism $f \colon G \to H$ such that $f(a)=b,$ given by $f(a^n)=b^n$ for all integers $n.$

So there is a unique isomorphism $f \colon \langle S,\circ \rangle \to \langle \mathbb{Z}_{11},+ \rangle$ such that $f(2)=1.$

We have:

$$f(1)=0$$

$$f(2)=1$$

$$f(4)= 2$$

$$f(8) = 3$$

The remaining values $f(x)$ for $x=3, 5, 6, 7, 9, 10, 11$ must be $4, 5, 6, 7, 8, 9, 10,$ in some order (and so must be distinct).

We have

$$f(6)=f(3 \circ 2) = f(3)+f(2) = f(3)+1 \,(\operatorname{mod} 11)$$

$$f(9)= f(3\circ 3) = 2 f(3)\,(\operatorname{mod} 11)$$

Now, $f(3)$ can't be $6$ or $7,$ since then $f(9)$ would be $1$ or $3.$ Also, $f(3)$ can't be $10,$ since then $f(6)$ would be $0.$ So here is a table of possible values for $f(3), f(6),$ and $f(9)\!:$

\begin{array} &f(3) & f(6) &f(9) \\ \hline 4&5&8 \\5&6&10 \\8&9&5 \\9&10&7 \end{array}

We also know that $f(10)=f(5)+1.$ For each possible value of $f(3),$ we can enumerate the values for $f(5)$ and $f(10)$ that work:

\begin{array} &f(3) & f(6) & f(9) & f(5) & f(10) \\ \hline 4&5&8 &6&7 \\ 4&5&8 &9&10 \\5&6&10 &7&8 \\5&6&10 &8&9 \\8&9&5 &6&7 \\9&10&7 &4&5 \\9&10&7 &5&6 \end{array}

The remaining two possibilities in each row must be $f(7)$ and $f(11)\!:$

\begin{array} &f(3) & f(6) & f(9) & f(5) & f(10) &f(7)\text{ and }f(11)\text{ in either order} \\ \hline 4&5&8 &6&7 &9\text{ and }10 \\ 4&5&8 &9&10 &6\text{ and }7 \\5&6&10 &7&8 &4\text{ and }9 \\5&6&10 &8&9 &4\text{ and }7 \\8&9&5 &6&7 &4\text{ and }10 \\9&10&7 &4&5 &6\text{ and }8 \\9&10&7 &5&6 &4\text{ and }8 \end{array}

So this gives 14 possible isomorphisms $f,$ two for each row, depending on whether $f(7)$ and $f(11)$ are as written in the table above or reversed.

In fact, each such function $f$ is a bijection that induces a binary operation $\circ_f$ on $S$ which satisfies the criterion -- specifically, $x \circ_f y = f^{-1}((f(x) + f(y)) \,(\operatorname{mod} 11)).$ The function $f \colon \langle S,\circ_f \rangle \to \langle \mathbb{Z}_{11}, + \rangle$ is an isomorphism.

Finally, if $f$ and $g$ are distinct functions as above, then $\circ_f \ne \circ_g,$ since otherwise $f \circ g^{-1}$ would be an isomorphism of $\mathbb{Z}_{11}$ with itself which maps the (non-zero) element $1$ to the element $1,$ but which is not the identity.

It follows that there are 14 binary operations with the required properties.