Quadratic Nimber Equation

Question

I'd like to ask how to solve the quadratic nimber equation $x\otimes x \oplus b \otimes x \oplus c=0$, where $\otimes$ is nim multiplication and $\oplus$ is nim addition.

Answer 1

From now on, all arithmetic is nimber arithmetic, except for anything in brackets ($3+5=6$ while $[3+5]=8$). For each $n\ge 0$, let $F_n:= 2^{2^n}$ be the $n^\text{th}$ Fermat 2-power. These play a special roll in nimber multiplication.

• The set of nimbers less than $F_n$ is a field, closed under multiplication and addition.
• If $x<F_n$, then $x+F_n=[x+F_n]$ and $xF_n=[xF_n]$.

These two facts imply that, for any nimber $x\ge 2$, that if $F$ is the largest Fermat 2-power such that $F\le x$, then there exist unique nimbers $x_1,x_2$ such that $\max(x_1,x_2)<F$, and $$ x=x_1F+x_2 $$ First, we show how to solve some particular quadratic equations.

Lemma 1: For any nimber $x$, with $x=x_1F+x_2$ as above, we have$$ \sqrt{x}=\sqrt{x_1}\cdot F+\sqrt{x_1[F/2]+x_2} $$ Proof: To prove this, simply compute $\big(\sqrt{x_1}\cdot F+\sqrt{x_1[F/2]+x_2}\big)^2$, and check that it equals $x$. Remember that $(a+b)^2=a^2+b^2$, and that $F^2=[(3/2)F]=F+[F/2]$.

Note that Lemma 1 gives a fast, recursive method to compute $\sqrt{c}$. That is, to compute $\sqrt{c}$, you split up $c=c_1F+c_2$, then recursively compute $\sqrt{c_1}$ and $\sqrt{c_1\cdot [F/2]+c_2}$, and apply Lemma 1. This means we can solve the equation $x^2+c=0$ for $x$.

The next equation we will tackle is of the form $x^2+x+c=0$. This is equivalent to, letting $f(x)=x^2+x$, hfinding $f^{-1}(c)$. You can show that $f$ is a two-to-one additive homomorphism on the nimbers which satisfies $f(x)=f(x+1)$, so $f^{-1}(c)$ always consists of two numbers that differ by one. To be precise, I define $f^{-1}(c)$ to be the even solution of $x^2+x=c$. For example, since $f(4)=f(5)=2$, we define $f^{-1}(2)=4$.

Note that for any Fermat 2-power, $F$, we have $f(F)=F^2+F=F+[F/2]+F=[F/2]$. That is, $f^{-1}([F/2])=F$.

Lemma 2: Let $y$ be any nimber, and write $y=y_1F+y_2$.

• If $y_1\ge [F/2]$, then $$f^{-1}(y)=[F^2]+f^{-1}(y+[F^2/2]).$$
• Otherwise, letting $x_1=f^{-1}(y_1)$ we have $$f^{-1}(y)=x_1\cdot F+f^{-1}(x_1^2\cdot [F/2]+y_2)$$

Proof: Again, you can verify both equations by taking $f$ of both sides.

Again, Lemma 2 allows us to compute $f^{-1}(y)$ for all nimbers $y$, recursively.

With these two Lemmas, we now have the power to compute the solution to any quadratic equation. In order two solve $ax^2+bx+c=0$, there are two cases.

• If $b=0$, then $x=\sqrt{c/a}$, so we can compute the solution using Lemma 1.
• If $b\neq 0$, then letting $z=(a/b)x$, we have $$z^2+z+ac/b^2=(a/b^2)(ax^2+bx+c)=0$$Therefore, we have $x=(b/a)z=(b/a)\cdot f^{-1}(ac/b^2)$, so we can compute using Lemma 2.