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)$.

  • $\begingroup$ 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? $\endgroup$ – Hang Wu Jan 30 at 2:25
  • $\begingroup$ 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? $\endgroup$ – Oscar Lanzi Jan 30 at 2:58
  • $\begingroup$ @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. $\endgroup$ – Mike Earnest Jan 30 at 3:06
  • $\begingroup$ I see. Thanks a lot. $\endgroup$ – Hang Wu Jan 30 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.