Nimber

Nimber addition (also known as nim-addition) can be used to calculate the size of a single nim heap equivalent to a collection of nim heaps. It is defined recursively by

$${\displaystyle \alpha \oplus \beta =\operatorname {mex} \!{\bigl (}\{\alpha '\oplus \beta$$ :\alpha '<\alpha \}\cup \{\alpha \oplus \beta ':\beta '<\beta \}{\bigr )},}

where the minimum excludant mex(S) of a set S of ordinals is defined to be the smallest ordinal that is not an element of S.

For finite ordinals, the nim-sum is easily evaluated on a computer by taking the bitwise exclusive or (XOR, denoted by ⊕) of the corresponding numbers. For example, the nim-sum of 7 and 14 can be found by writing 7 as 111 and 14 as 1110; the ones place adds to 1; the twos place adds to 2, which we replace with 0; the fours place adds to 2, which we replace with 0; the eights place adds to 1. So the nim-sum is written in binary as 1001, or in decimal as 9.

This property of addition follows from the fact that both mex and XOR yield a winning strategy for Nim and there can be only one such strategy; or it can be shown directly by induction: Let α and β be two finite ordinals, and assume that the nim-sum of all pairs with one of them reduced is already defined. The only number whose XOR with α is α ⊕ β is β, and vice versa; thus α ⊕ β is excluded.

$${\displaystyle \zeta$$ :=\alpha \oplus \beta \oplus \gamma }

On the other hand, for any ordinal γ < α ⊕ β, XORing ξ with all of α, β and γ must lead to a reduction for one of them (since the leading 1 in ξ must be present in at least one of the three); since

$${\displaystyle \zeta \oplus \gamma =\alpha \oplus \beta >\gamma ,}$$

we must have either

$${\displaystyle {\begin{aligned}\alpha >\zeta \oplus \alpha &=\beta \oplus \gamma ,\\[4pt]\beta >\zeta \oplus \beta &=\alpha \oplus \gamma$$ ;\end{aligned}}}

thus γ is included as either

$${\displaystyle {\begin{aligned}(\beta \oplus \gamma )\oplus \beta ,\\[4pt]\alpha \oplus (\alpha \oplus \gamma );\end{aligned}}}$$

and hence α ⊕ β is the minimum excluded ordinal.

Nimber addition is associative and commutative, with 0 as the additive identity element. Moreover, a nimber is its own additive inverse.[4] It follows that α ⊕ β = 0 if and only if α = β.

Nimber multiplication (nim-multiplication) is defined recursively by

$${\displaystyle \alpha \,\beta =\operatorname {mex} \!{\bigl (}\{\alpha '\beta \oplus \alpha \,\beta '\oplus \alpha '\beta ':\alpha '<\alpha ,\beta '<\beta \}{\bigr )}.}$$

Nimber multiplication is associative and commutative, with the ordinal 1 as the multiplicative identity element. Moreover, nimber multiplication distributes over nimber addition.[4]

Thus, except for the fact that nimbers form a proper class and not a set, the class of nimbers forms a ring. In fact, it even determines an algebraically closed field of characteristic 2, with the nimber multiplicative inverse of a nonzero ordinal α given by

$${\displaystyle \alpha ^{-1}=\operatorname {mex} (S),}$$

where S is the smallest set of ordinals (nimbers) such that

1. 0 is an element of S;
2. if 0 < α′ < α and β' is an element of S, then ${\displaystyle {\tfrac {1+(\alpha '-\alpha )\beta '}{\alpha '^{-1}}}}$ is also an element of S.

For all natural numbers n, the set of nimbers less than 2²ⁿ form the Galois field GF(2²ⁿ) of order 2²ⁿ. Therefore, the set of finite nimbers is isomorphic to the direct limit as n → ∞ of the fields GF(2²ⁿ). This subfield is not algebraically closed, since no field GF(2^k) with k not a power of 2 is contained in any of those fields, and therefore not in their direct limit; for instance the polynomial x³ + x + 1, which has a root in GF(2³), does not have a root in the set of finite nimbers.

Just as in the case of nimber addition, there is a means of computing the nimber product of finite ordinals. This is determined by the rules that

1. The nimber product of a Fermat 2-power (numbers of the form 2²ⁿ) with a smaller number is equal to their ordinary product;
2. The nimber square of a Fermat 2-power x is equal to 3x/2 as evaluated under the ordinary multiplication of natural numbers.

The smallest algebraically closed field of nimbers is the set of nimbers less than the ordinal ω^ωω, where ω is the smallest infinite ordinal. It follows that as a nimber, ω^ωω is transcendental over the field.[5]

The following tables exhibit addition and multiplication among the first 16 nimbers.

This subset is closed under both operations, since 16 is of the form 2²ⁿ. (If you prefer simple text tables, they are here.)

Nimber addition (sequence A003987 in the OEIS)
This is also the Cayley table of Z₂⁴ – or the table of bitwise XOR operations.
The small matrices show the single digits of the binary numbers.

Nimber multiplication (sequence A051775 in the OEIS)
The nonzero elements form the Cayley table of Z₁₅.
The small matrices are permuted binary Walsh matrices.

Nimber multiplication of powers of two (sequence A223541 in the OEIS)
Calculating the nim-products of powers of two is a decisive point in the recursive algorithm of nimber-multiplication.

• Surreal number