Nimber - Properties

Properties

The Sprague–Grundy theorem states that every impartial game is equivalent to a nim heap of a certain size. Nimber addition (also known as nim-addition) can be used to calculate the size of a single heap equivalent to a collection of heaps. It is defined recursively by

where for a set S of ordinals, mex(S) is defined to be the "minimum excluded ordinal", i.e. mex(S) is the smallest ordinal which 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. This 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. 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 ξ ⊕ γ = α ⊕ β > γ, we must have α > ξ ⊕ α = β ⊕ γ or β > ξ ⊕ β = α ⊕ γ; thus γ is included as (β ⊕ γ) ⊕ β or as α ⊕ (α ⊕ γ), and hence α ⊕ β is the minimum excluded ordinal.

Nimber multiplication (nim-multiplication) is defined recursively by

α β = mex{α ′ β + α β ′ − α ′ β ′ : α ′ < α, β ′ < β} = mex{α ′ β + α β ′ + α ′ β ′ : α ′ < α, β ′ < β}.

Except for the fact that nimbers form a proper class and not a set, the class of nimbers determines an algebraically closed field of characteristic 2. The nimber additive identity is the ordinal 0, and the nimber multiplicative identity is the ordinal 1. In keeping with the characteristic being 2, the nimber additive inverse of the ordinal α is α itself. The nimber multiplicative inverse of the nonzero ordinal α is given by 1/α = 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 /α ′ is also an element of S.

For all natural numbers n, the set of nimbers less than 22n form the Galois field GF(22n) of order 22n.

In particular, this implies that the set of finite nimbers is isomorphic to the direct limit of the fields GF(22n), for each positive n. This subfield is not algebraically closed, however.

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 distinct Fermat 2-powers (numbers of the form 22n) 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.