Prove that nim multiplication is associative and distributive

Question

Let $\oplus$ represent nim-addition, and let $\otimes$ represent nim-multiplication. We define nim-addition as bitwise exclusive or. We define nim-multiplication recursively as follows:

$$ x\otimes y=\text{mex}\{(a\otimes x)\oplus (b\otimes y)\oplus (a\otimes b):0\leq a<x, 0\leq b<y\}, $$ where the $\text{mex}$ of a set $S$ is the minimum nonnegative integer that is not in $S$.

Prove that

• $(x\otimes y)\otimes z=x\otimes(y\otimes z)$ for all $x,y,z$; and
• $x\otimes(y\oplus z)=(x\otimes) y\oplus (x\otimes z)$ for all $x,y,z$.

In the book I'm reading it says that this is a routine induction. However, I'm not so confident in how to do this. Starting with associativity, my instict was to expand $(x\otimes y)\otimes z$ into $$ \text{mex}\{(a\otimes(x\otimes y))\oplus(b\otimes z)\oplus(a\otimes b):a<x\otimes y, b<z\}, $$ and then try to rearrange this into a form that is similar to the expansion for $x\otimes(y\otimes z)$. But I cannot see a way of doing this. What am I missing for this 'routine' induction? Any help appreciated!

Answer 1

I could not figure this out either, so I looked up the proof in On Numbers and Games, where Conway originally developed the theory of nimbers. In Conway's notation, $a'$ is always a variable which ranges over $\{0,1,\dots,a-1\}$, so that the addition and multiplication definitions can be written more succinctly as $$ a+b:=\text{mex}\{a+b',\;\;a'+b\}\\ \hspace{1cm}ab:=\text{mex}\{a'b+ab'+a'b'\} $$

Conway uses the following fact as a lemma in his proofs:

Lemma: Let $a,b\in \mathbb N$. Let $A\subseteq \mathbb N$ such that $\{0,1,\dots,a-1\}\subseteq A$, and $a\notin A$. Similarly, let $B\subseteq \mathbb N$ such that $\{0,1,\dots,b-1\}\subseteq B$, and $b\notin B$. Then $$ a+b=\text{mex}\{a^*+b,a+b^*\mid a^*\in A,b^*\in B\}\\ ab=\newcommand{\mex}{\operatorname{mex}}\mex \{ab^*+a^*b+a^*b^*\mid a^*\in A,b^*\in B\} $$

Proof sketch: We are taking the definitons of $a+b$ and $ab$, and adding in some extra exlcudants. As long as we can show $$ a^*+b\neq a+b,\qquad a+b^*\neq a+b,\qquad a^*b+b^*a+a^*b^*\neq ab,$$whenever $a^*>a$ or $b^*>b,$ then none of the added numbers will change the mex. The first two should be obvious. Proving the last is equivalent to showing $$ a^*b^*\neq a^*b+ab^*+ab, $$ This is true provided $a^*>a$ and $b^*>b$, since $a^*b+ab^*+ab$ is one of the excludants in the definition of $a^*b^*$. The other cases where $a^*>a$ and $b^*<b$, and where $a^*<a$ and $b^*>b$, are similar.

---

With this lemma, we can now give a simple proof by induction. Let's start with distributivity, since we need that to prove associativity. From the lemma, we can write $$ (a+b)c=\text{mex}\{s^*c+(a+b)c'+s^*c'\mid s^*\in S,\color{gray}{c'<c}\}, $$ where $S$ is any subset which contains all the numbers less than $a+b$, and does not contain $a+b$. In particular, we will take $ S=\{a+b',a'+b\}. $ This means $$ (a+b)c=\mex\{(a'+b)c+(a+b)c'+(a'+b)c',\;\;(a+b')c+(a+b)c'+(a+b')c'\} $$

By induction, we can assume the distributive property for all of the simpler excludants, so $$ (a+b)c=\mex\{(a'c+ac'+a'c')+bc,\;\; ac+(b'c+bc'+b'c')\}\tag1 $$ On the other hand, $$ ac+bc=\mex\{p^*+bc,ac+q^*\mid p^*\in P,q^*\in Q\} $$ where $P$ contains all numbers less than $ac$, but excludes $ac$, and $Q$ contains all numbers less than $bc$, but excludes $bc$. In particular, we can take $P=\{a'c+ac'+a'c'\}$ and $Q=\{b'c+bc'+b'c'\}$, in which case we recover $(1)$ exactly, completing the proof.

---

Now, onto associativity. We can write $$ (ab)c=\text{mex}\{p^*c+(ab)c'+p^*c\} $$ where $p^*$ ranges over any set containing all numbers less than $ab$, but not $ab$. In particular, we let $p^*$ range over $\{a'b+ab'+a'b'\}$, which gives \begin{align} (ab)c &=\text{mex}\{(a'b+ab'+a'b')c+(ab)c'+(a'b+ab'+a'b')c'\} \\&=\text{mex}\{a'bc+ab'c+a'b'c+abc'+a'bc'+ab'c'+a'b'c'\}\tag2 \end{align} In the second equality, we use the distributive property, and we use the fact that we can inductively assume associativity for the simpler products to omit parentheses. The proof is completed by expanding $a(bc)$ using the same strategy, and noting the expression is equal to $(2)$.