Characteristic 3 analogue of nimbers?

552 Views Asked by At

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?

3

There are 3 best solutions below

0
On BEST ANSWER

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.

5
On

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.

0
On

Although some years late, it might be interesting for others who are searching for these (recursive) definitions.

I have no proof for this, but it seems to work:

Let $+,\cdot$ denote multiplication in $\mathbb{N}_0$. The addition and multiplication in $\operatorname{On}_p$ are denoted $\oplus, \otimes$.

Recursive definition of addition:

$$x \oplus y := ((x+y) \mod (p)) + (\lfloor\frac{x}{p}\rfloor \oplus \lfloor \frac{y}{p}\rfloor )\cdot p$$

This can be expanded to give:

$$x \oplus y := \sum_{i=0}^{\max(r,s)} ((x_i+y_i)\mod(p) )\cdot p^i$$

where $x = \sum_{i=0}^r x_i p^i$, $y = \sum_{i=0}^s y_i p^i$ is the $p$-adic expansion of $x,y$.

(Semi-) Recursive definition of multiplication:

First initialize multiplication table $M[x,y]:=-1$

The function $x \otimes y$ computes in this order (After computation the multiplication table gets updated):

  1. The cases $a=0$ or $b=0$, $a=1$ or $b=1$ are defined to be consistent with multiplication rules of $0,1$ in fields.

  2. The cases $a\le p-1$ and $b \le p-1$ are defined $\mod (p)$:

    $a\otimes b:= a \cdot b \mod (p)$

  3. We first generate a candidate set based on Conway $\operatorname{mex}$ definition: $C := \{ 1,2,\cdots,a\cdot b\}-\{((a'\otimes b)\oplus (b' \otimes a) \ominus (a' \otimes b')| a'<a,b'<b\}$

    Usually in $\operatorname{On}_2$ the $\min$ of this set is taken as definition of $a \otimes b$. This does however not work, as it happens that it is not distributive. To make it distribute I propose the following:

    Once we have chosen an $x$ from the candidate set $C$ for $a \otimes b$, using the distributive law in fields, we can fix some entries in the multiplicaion table $M$. However, it can happen that we get a contradicition to $M$. So we must chose another $x$ from $C$. So I will chose the smalles $x$ in C, which does not contradict the distributive law with the current multiplication table $M$:

$M[a\ominus a',b \ominus b'] = x \ominus M[a,b'] \ominus M[b,a'] \oplus M[a',b'] \forall a'<a,b'<b$

Sorry for not being more precise, but this is an experiment, and I have not figured out everything yet. Yet, the "empirical" results seem promising:

addition: 2 2

$$ \left(\begin{array}{rr} 0 & 1 \\ 1 & 0 \end{array}\right) $$

multiplicatin: 2 2

$$ \left(\begin{array}{rr} 0 & 0 \\ 0 & 1 \end{array}\right) $$

addition: 2 4 $$ \left(\begin{array}{rrrr} 0 & 1 & 2 & 3 \\ 1 & 0 & 3 & 2 \\ 2 & 3 & 0 & 1 \\ 3 & 2 & 1 & 0 \end{array}\right) $$ multiplicatin: 2 4 $$ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 \\ 0 & 2 & 3 & 1 \\ 0 & 3 & 1 & 2 \end{array}\right) $$

addition: 3 3 $$ \left(\begin{array}{rrr} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{array}\right) $$

multiplicatin: 3 3 $$ \left(\begin{array}{rrr} 0 & 0 & 0 \\ 0 & 1 & 2 \\ 0 & 2 & 1 \end{array}\right) $$

addition: 3 9 $$ \left(\begin{array}{rrrrrrrrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 2 & 0 & 4 & 5 & 3 & 7 & 8 & 6 \\ 2 & 0 & 1 & 5 & 3 & 4 & 8 & 6 & 7 \\ 3 & 4 & 5 & 6 & 7 & 8 & 0 & 1 & 2 \\ 4 & 5 & 3 & 7 & 8 & 6 & 1 & 2 & 0 \\ 5 & 3 & 4 & 8 & 6 & 7 & 2 & 0 & 1 \\ 6 & 7 & 8 & 0 & 1 & 2 & 3 & 4 & 5 \\ 7 & 8 & 6 & 1 & 2 & 0 & 4 & 5 & 3 \\ 8 & 6 & 7 & 2 & 0 & 1 & 5 & 3 & 4 \end{array}\right) $$

multiplicatin: 3 9 $$ \left(\begin{array}{rrrrrrrrr} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 0 & 2 & 1 & 6 & 8 & 7 & 3 & 5 & 4 \\ 0 & 3 & 6 & 2 & 5 & 8 & 1 & 4 & 7 \\ 0 & 4 & 8 & 5 & 6 & 1 & 7 & 2 & 3 \\ 0 & 5 & 7 & 8 & 1 & 3 & 4 & 6 & 2 \\ 0 & 6 & 3 & 1 & 7 & 4 & 2 & 8 & 5 \\ 0 & 7 & 5 & 4 & 2 & 6 & 8 & 3 & 1 \\ 0 & 8 & 4 & 7 & 3 & 2 & 5 & 1 & 6 \end{array}\right) $$

addition: 5 5 $$ \left(\begin{array}{rrrrr} 0 & 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 0 \\ 2 & 3 & 4 & 0 & 1 \\ 3 & 4 & 0 & 1 & 2 \\ 4 & 0 & 1 & 2 & 3 \end{array}\right) $$

multiplicatin: 5 5 $$ \left(\begin{array}{rrrrr} 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 & 4 \\ 0 & 2 & 4 & 1 & 3 \\ 0 & 3 & 1 & 4 & 2 \\ 0 & 4 & 3 & 2 & 1 \end{array}\right) $$

addition: 5 25 $$ \left(\begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\ 1 & 2 & 3 & 4 & 0 & 6 & 7 & 8 & 9 & 5 & 11 & 12 & 13 & 14 & 10 & 16 & 17 & 18 & 19 & 15 & 21 & 22 & 23 & 24 & 20 \\ 2 & 3 & 4 & 0 & 1 & 7 & 8 & 9 & 5 & 6 & 12 & 13 & 14 & 10 & 11 & 17 & 18 & 19 & 15 & 16 & 22 & 23 & 24 & 20 & 21 \\ 3 & 4 & 0 & 1 & 2 & 8 & 9 & 5 & 6 & 7 & 13 & 14 & 10 & 11 & 12 & 18 & 19 & 15 & 16 & 17 & 23 & 24 & 20 & 21 & 22 \\ 4 & 0 & 1 & 2 & 3 & 9 & 5 & 6 & 7 & 8 & 14 & 10 & 11 & 12 & 13 & 19 & 15 & 16 & 17 & 18 & 24 & 20 & 21 & 22 & 23 \\ 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 0 & 1 & 2 & 3 & 4 \\ 6 & 7 & 8 & 9 & 5 & 11 & 12 & 13 & 14 & 10 & 16 & 17 & 18 & 19 & 15 & 21 & 22 & 23 & 24 & 20 & 1 & 2 & 3 & 4 & 0 \\ 7 & 8 & 9 & 5 & 6 & 12 & 13 & 14 & 10 & 11 & 17 & 18 & 19 & 15 & 16 & 22 & 23 & 24 & 20 & 21 & 2 & 3 & 4 & 0 & 1 \\ 8 & 9 & 5 & 6 & 7 & 13 & 14 & 10 & 11 & 12 & 18 & 19 & 15 & 16 & 17 & 23 & 24 & 20 & 21 & 22 & 3 & 4 & 0 & 1 & 2 \\ 9 & 5 & 6 & 7 & 8 & 14 & 10 & 11 & 12 & 13 & 19 & 15 & 16 & 17 & 18 & 24 & 20 & 21 & 22 & 23 & 4 & 0 & 1 & 2 & 3 \\ 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 11 & 12 & 13 & 14 & 10 & 16 & 17 & 18 & 19 & 15 & 21 & 22 & 23 & 24 & 20 & 1 & 2 & 3 & 4 & 0 & 6 & 7 & 8 & 9 & 5 \\ 12 & 13 & 14 & 10 & 11 & 17 & 18 & 19 & 15 & 16 & 22 & 23 & 24 & 20 & 21 & 2 & 3 & 4 & 0 & 1 & 7 & 8 & 9 & 5 & 6 \\ 13 & 14 & 10 & 11 & 12 & 18 & 19 & 15 & 16 & 17 & 23 & 24 & 20 & 21 & 22 & 3 & 4 & 0 & 1 & 2 & 8 & 9 & 5 & 6 & 7 \\ 14 & 10 & 11 & 12 & 13 & 19 & 15 & 16 & 17 & 18 & 24 & 20 & 21 & 22 & 23 & 4 & 0 & 1 & 2 & 3 & 9 & 5 & 6 & 7 & 8 \\ 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 16 & 17 & 18 & 19 & 15 & 21 & 22 & 23 & 24 & 20 & 1 & 2 & 3 & 4 & 0 & 6 & 7 & 8 & 9 & 5 & 11 & 12 & 13 & 14 & 10 \\ 17 & 18 & 19 & 15 & 16 & 22 & 23 & 24 & 20 & 21 & 2 & 3 & 4 & 0 & 1 & 7 & 8 & 9 & 5 & 6 & 12 & 13 & 14 & 10 & 11 \\ 18 & 19 & 15 & 16 & 17 & 23 & 24 & 20 & 21 & 22 & 3 & 4 & 0 & 1 & 2 & 8 & 9 & 5 & 6 & 7 & 13 & 14 & 10 & 11 & 12 \\ 19 & 15 & 16 & 17 & 18 & 24 & 20 & 21 & 22 & 23 & 4 & 0 & 1 & 2 & 3 & 9 & 5 & 6 & 7 & 8 & 14 & 10 & 11 & 12 & 13 \\ 20 & 21 & 22 & 23 & 24 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ 21 & 22 & 23 & 24 & 20 & 1 & 2 & 3 & 4 & 0 & 6 & 7 & 8 & 9 & 5 & 11 & 12 & 13 & 14 & 10 & 16 & 17 & 18 & 19 & 15 \\ 22 & 23 & 24 & 20 & 21 & 2 & 3 & 4 & 0 & 1 & 7 & 8 & 9 & 5 & 6 & 12 & 13 & 14 & 10 & 11 & 17 & 18 & 19 & 15 & 16 \\ 23 & 24 & 20 & 21 & 22 & 3 & 4 & 0 & 1 & 2 & 8 & 9 & 5 & 6 & 7 & 13 & 14 & 10 & 11 & 12 & 18 & 19 & 15 & 16 & 17 \\ 24 & 20 & 21 & 22 & 23 & 4 & 0 & 1 & 2 & 3 & 9 & 5 & 6 & 7 & 8 & 14 & 10 & 11 & 12 & 13 & 19 & 15 & 16 & 17 & 18 \end{array}\right) $$

multiplicatin: 5 25 $$ \left(\begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrr} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\ 0 & 2 & 4 & 1 & 3 & 10 & 12 & 14 & 11 & 13 & 20 & 22 & 24 & 21 & 23 & 5 & 7 & 9 & 6 & 8 & 15 & 17 & 19 & 16 & 18 \\ 0 & 3 & 1 & 4 & 2 & 15 & 18 & 16 & 19 & 17 & 5 & 8 & 6 & 9 & 7 & 20 & 23 & 21 & 24 & 22 & 10 & 13 & 11 & 14 & 12 \\ 0 & 4 & 3 & 2 & 1 & 20 & 24 & 23 & 22 & 21 & 15 & 19 & 18 & 17 & 16 & 10 & 14 & 13 & 12 & 11 & 5 & 9 & 8 & 7 & 6 \\ 0 & 5 & 10 & 15 & 20 & 2 & 7 & 12 & 17 & 22 & 4 & 9 & 14 & 19 & 24 & 1 & 6 & 11 & 16 & 21 & 3 & 8 & 13 & 18 & 23 \\ 0 & 6 & 12 & 18 & 24 & 7 & 13 & 19 & 20 & 1 & 14 & 15 & 21 & 2 & 8 & 16 & 22 & 3 & 9 & 10 & 23 & 4 & 5 & 11 & 17 \\ 0 & 7 & 14 & 16 & 23 & 12 & 19 & 21 & 3 & 5 & 24 & 1 & 8 & 10 & 17 & 6 & 13 & 15 & 22 & 4 & 18 & 20 & 2 & 9 & 11 \\ 0 & 8 & 11 & 19 & 22 & 17 & 20 & 3 & 6 & 14 & 9 & 12 & 15 & 23 & 1 & 21 & 4 & 7 & 10 & 18 & 13 & 16 & 24 & 2 & 5 \\ 0 & 9 & 13 & 17 & 21 & 22 & 1 & 5 & 14 & 18 & 19 & 23 & 2 & 6 & 10 & 11 & 15 & 24 & 3 & 7 & 8 & 12 & 16 & 20 & 4 \\ 0 & 10 & 20 & 5 & 15 & 4 & 14 & 24 & 9 & 19 & 3 & 13 & 23 & 8 & 18 & 2 & 12 & 22 & 7 & 17 & 1 & 11 & 21 & 6 & 16 \\ 0 & 11 & 22 & 8 & 19 & 9 & 15 & 1 & 12 & 23 & 13 & 24 & 5 & 16 & 2 & 17 & 3 & 14 & 20 & 6 & 21 & 7 & 18 & 4 & 10 \\ 0 & 12 & 24 & 6 & 18 & 14 & 21 & 8 & 15 & 2 & 23 & 5 & 17 & 4 & 11 & 7 & 19 & 1 & 13 & 20 & 16 & 3 & 10 & 22 & 9 \\ 0 & 13 & 21 & 9 & 17 & 19 & 2 & 10 & 23 & 6 & 8 & 16 & 4 & 12 & 20 & 22 & 5 & 18 & 1 & 14 & 11 & 24 & 7 & 15 & 3 \\ 0 & 14 & 23 & 7 & 16 & 24 & 8 & 17 & 1 & 10 & 18 & 2 & 11 & 20 & 9 & 12 & 21 & 5 & 19 & 3 & 6 & 15 & 4 & 13 & 22 \\ 0 & 15 & 5 & 20 & 10 & 1 & 16 & 6 & 21 & 11 & 2 & 17 & 7 & 22 & 12 & 3 & 18 & 8 & 23 & 13 & 4 & 19 & 9 & 24 & 14 \\ 0 & 16 & 7 & 23 & 14 & 6 & 22 & 13 & 4 & 15 & 12 & 3 & 19 & 5 & 21 & 18 & 9 & 20 & 11 & 2 & 24 & 10 & 1 & 17 & 8 \\ 0 & 17 & 9 & 21 & 13 & 11 & 3 & 15 & 7 & 24 & 22 & 14 & 1 & 18 & 5 & 8 & 20 & 12 & 4 & 16 & 19 & 6 & 23 & 10 & 2 \\ 0 & 18 & 6 & 24 & 12 & 16 & 9 & 22 & 10 & 3 & 7 & 20 & 13 & 1 & 19 & 23 & 11 & 4 & 17 & 5 & 14 & 2 & 15 & 8 & 21 \\ 0 & 19 & 8 & 22 & 11 & 21 & 10 & 4 & 18 & 7 & 17 & 6 & 20 & 14 & 3 & 13 & 2 & 16 & 5 & 24 & 9 & 23 & 12 & 1 & 15 \\ 0 & 20 & 15 & 10 & 5 & 3 & 23 & 18 & 13 & 8 & 1 & 21 & 16 & 11 & 6 & 4 & 24 & 19 & 14 & 9 & 2 & 22 & 17 & 12 & 7 \\ 0 & 21 & 17 & 13 & 9 & 8 & 4 & 20 & 16 & 12 & 11 & 7 & 3 & 24 & 15 & 19 & 10 & 6 & 2 & 23 & 22 & 18 & 14 & 5 & 1 \\ 0 & 22 & 19 & 11 & 8 & 13 & 5 & 2 & 24 & 16 & 21 & 18 & 10 & 7 & 4 & 9 & 1 & 23 & 15 & 12 & 17 & 14 & 6 & 3 & 20 \\ 0 & 23 & 16 & 14 & 7 & 18 & 11 & 9 & 2 & 20 & 6 & 4 & 22 & 15 & 13 & 24 & 17 & 10 & 8 & 1 & 12 & 5 & 3 & 21 & 19 \\ 0 & 24 & 18 & 12 & 6 & 23 & 17 & 11 & 5 & 4 & 16 & 10 & 9 & 3 & 22 & 14 & 8 & 2 & 21 & 15 & 7 & 1 & 20 & 19 & 13 \end{array}\right) $$

The python source code can be found here.

I have not proved anything yet, besides the addition being an abelian group.

It seems we get the finite fields of size $p^{(2^n)}$ ordered by inclusion.