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.

From now on, all arithmetic is nimber arithmetic, except $$2^i$$ will refer to the usual power of two. When $$b=0$$, the unique solution is $$x=\sqrt{c}$$, so assume $$b\neq 0$$.

In order to solve $$z^2+bz+d=0$$, use the substitution $$z=bx$$ to reduce this to $$x^2+x=c.$$ where $$c=d/b^2$$. That is, letting $$f(x)=x^2+x$$, you need $$f^{-1}(c)$$.

Note that $$f$$ is a linear map whose kernel is $$\{0,1\}$$, which means $$f$$ is a bijection from the subspace of even nimbers to all nimbers. I will use $$f^{-1}(y)$$ to denote the unique even nimber $$x$$ for which $$f(x)=y$$. Note $$f^{-1}$$ is also a linear map.

More specifically, it can be shown that

Prop: For any $$n\ge 1$$, $$f$$ is a surjective map from the interval $$[2^n,2^{n+1})$$ to $$[2^{n-1},2^n)$$.

I omit the proof.

Writing $$c=\sum_i b_i 2^i$$ with $$b_i\in \{0,1\}$$, we have $$f^{-1}(c) = \sum_i b_i f^{-1}(2^i)$$, so it suffices to compute $$f^{-1}(2^i)$$ for any $$i$$. This can be done recursively as follows. By the above proposition, there are (easily computable) numbers $$a_{ij}\in \{0,1\}$$ for which $$f(2^{i+1})=2^i + \sum_{j=0}^{i-1} a_{ij}2^j$$ Therefore, $$f^{-1}(2^i) = 2^{i+1}+\sum_{j=0}^{i-1}a_{ij}f^{-1}(2^i)$$ so $$f^{-1}(2^i)$$ can be computed from previously computed values $$f^{-1}(2^j)$$.

• There should be two solutions $x_1$, $x_2$ to the equation. Since $x_1 \oplus x_2=b$, we may get another if one is known. But you say $f$ is a bijection? – Hang Wu Jan 30 at 2:25
• The two "oblong roots" of any nimber sum to $1$, so one is even and one is odd. Can we define a "principal" oblong root as the even one and thus repair the bijectivity? – Oscar Lanzi Jan 30 at 2:58
• @HangWu $f$ is bijective when it’s domain is restricted to the even nimbers. I defined $f^{-1}$ to be the inverse for that restricted function. – Mike Earnest Jan 30 at 3:06
• I see. Thanks a lot. – Hang Wu Jan 30 at 3:25