9
$\begingroup$

Finite nimbers are a way of turning the natural numbers (finite ordinals) into a characteristic 2 field. Addition in this field is found by writing the numbers in binary and adding without carry, while multiplication is harder to describe concisely.

Nimber addition and multiplication have some recursive definitions as follows. Letting mex($S$) the smallest natural number not in $S$, $$ a+b=\text{mex}(\{a'+b\,|a'<a\}\cup\{a+b'|b'<b\}) $$ $$ ab = \text{mex}\,\{ab'+a'b-a'b'|a'<a,b'<b\} $$

I was wondering if anyone knew of a corresponding way to turn the natural numbers into a characteristic 3 field, and perhaps more generally one of characteristic $p$. The reason I'm hopeful this is possible is because there is a similar recursive definition of base 3 addition without carry, namely, $$ a+b = \text{mex}\,(\{a'+b\}\cup\{a+b'\}\cup\{a''+b''|a''+b=a+b''\}) $$ where $a',a''<a,b',b''<b$. There is also a similar definition for all prime $p$. But I can't seem to figure out a definition of multiplication. Has anyone else heard of/thought of this?

$\endgroup$
5
$\begingroup$

You should see the paper "On On_p", by Joseph DiMuro. In it, he gives a characteristic $p$ analogue of the nimbers. The addition is given by adding base $p$ without carries (including for ordinals). The definition of multiplication, unfortunately, is not so simple. But I think it's a good generalization.

The definition for the natural numbers is almost identical to the one Slade gives above; the only difference is in the choice of irreducible polynomial. This will result in a different field structure -- DiMuro's is equal to the union of $\mathbb{F}_{p^{2^k}}$, while (if I'm understanding correctly) Slade's is equal to the union of $\mathbb{F}_{p^{p^k}}$. But it's clearly very similar.

$\endgroup$
9
$\begingroup$

Importantly, the natural numbers with $\leq 2^n$ binary digits already form a field $F_n$ of order $2^{2^n}$ with the nim operations.

Let's see how this works inductively. $F_n \subset F_{n+1}$ is a degree $2$ extension. We have the (nim) identity $(2^{2^n})^2 = 2^{2^n} + 2^{2^n-1}$. In other words, $2^{2^n}$ is a root of the irreducible polynomial $T^2 - T - 2^{2^{n}-1}$ over $F_n$ (note: it is irreducible over $F_n$ precisely because $2^{2^{n}-1} \in F_n \setminus F_{n-1}$).

This gives a much simpler description of the $2$-nimbers: they're just the usual tower of finite fields of order $2^{2^0}, 2^{2^1},$ etc., but at stage $n \to n+1$ we identify $2^{n+1}$ with a root of $T^2 - T - 2^{2^{n}-1}$.

To guarantee uniqueness, we need to assume two things: Addition-without-carrying, and the law that the nim-product of $2^{2^k}$ with $2^{2^l}$ is the ordinary product of these when $k\neq l$. This gives a unique multiplication on the binary numbers with $\leq 2^{n+1}$ digits, that is compatible with the previous one.

It appears that every step of this applies equally to the "$p$-nimbers": Start with $F_0 = \mathbb{Z}/p$, identified as the naturals with one base $p$ digit, and form the extension $F_n \subset F_{n+1}$ using addition without carry, identifying $p^{n+1}$ with a root of the irreducible polynomial $T^p - T - p^{p^n - 1}$, and transporting the existing field structure from the finite field of $p^{n+1}$ elements.

To ensure uniqueness, we enforce that the nim-product of $p^{p^k}$ with $p^{p^l}$ is their usual product. This works because every power of $p$ is a product of powers of this form, and using the same idea we can show that the induced multiplication is well-defined and satisfies the right properties.

This makes $\mathbb{N}$ into a field of characteristic $p$, and we can all feel very pleased with ourselves.

$\endgroup$
  • $\begingroup$ Very nice, thank you for the well thought out answer! Though I still wonder if multiplication can be defined recursively in this field like it can when $p=2$, so the nested field extension property can be derived instead of used as the definition of the field. $\endgroup$ – Mike Earnest Oct 17 '14 at 6:20
  • $\begingroup$ @MikeEarnest I think that's a really important step. I rushed through some of the details when convincing myself that multiplication was well-defined as I presented it. There are various hacks I could work in, but it would be much better to just write down the multiplication recursively, and verify that it satisfies the defining properties. I'll probably try to work this out eventually, but maybe not for a while—this problem has been really interesting, but kind of time-consuming, since I started with nearly zero intuition for this whole nim business. $\endgroup$ – Slade Oct 17 '14 at 6:34
  • $\begingroup$ @MikeEarnest It might be possible to work this out even when $p$ is not prime, since I'm not sure I really needed field-iness except for convenience. Maybe this is related to some nim-type game with $p$ players. Yes sir, I could definitely put off my thesis for weeks with this problem... $\endgroup$ – Slade Oct 17 '14 at 6:36
  • $\begingroup$ @Slade CGT only deals with 2 player games. It would get a ton more complicated for more than two, so I doubt such a simple thing would work. $\endgroup$ – PyRulez Jun 27 '15 at 18:10

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.