## 403/503- Homework 1

Recall that we defined Nim addition $\oplus$ and Nim multiplication $\otimes$ on the natural numbers ${\mathbb N}=\{0,1,\dots\}$ by setting:

1. $n\oplus m$ is the result of writing $n,m$ in binary and adding without carrying.
2. $\otimes$ is the unique binary operation on ${\mathbb N}$ that is commutative, associative, distributive over $\oplus$ and satisfies:
• $\displaystyle F_n\otimes F_n=\frac32 F_n$ and
• $\displaystyle F_n\otimes m=F_nm$ whenever $m< F_n$. Here, $F_n=2^{2^n}$ for all $n\in{\mathbb N}$, call these numbers “Fermat’s 2-powers”.

The first problem is that it is not quite clear that $\otimes$ is even well-defined (i.e., are there any functions at all that behave as required of $\otimes$? Is there really only one such function?). Begin by checking this, by showing that the rules above give us that $n\otimes m$ is the result of writing $n,m$ as sums of (multiplications by powers of 2) of Fermat 2-powers, and expanding using associativity, distributivity, and the two rules about how to multiply with Fermat 2-powers. (Verify that any $n$ can indeed be written as such a sum in a unique way, and that this indeed shows that $\otimes$ is completely characterized by our description.)

Show that if we set ${\mathbb F}_{2^{2^n}}=\{0,1,\dots,F_n-1\}$, then ${\mathbb N}$ and each ${\mathbb F}_{2^{2^n}}$ are fields (over ${\mathbb Z}_2$, with addition and multiplication given by $\otimes,\oplus$.

In lecture I erroneously mentioned that ${\mathbb N}$ is algebraically closed. This is not the case. For example, show that the equation $x^3+x+1=0$ has no solutions in ${\mathbb N}$ when we interpret “$n$ is a solution” to mean that $(n\otimes n\otimes n)\oplus n\oplus 1=0$.

Nim addition and multiplication were introduced by John Conway. A bit of online searching will give you references for this exercise, but please abstain from looking for them. I will provide references and some additional details once the homework has been turned in.

This set is due February 11 at the beginning of lecture.