Nimber
In mathematics, a nimber, also known as a "Grundy number" (though not to be confused with a Grundy chromatic number, which is also known as a "Grundy number"), is a mathematical value used in combinatorial game theory to represent the…
≈ 7 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, a nimber, also known as a "Grundy number" (though not to be confused with a Grundy chromatic number, which is also known as a "Grundy number"), is a mathematical value used in combinatorial game theory to represent the value of a position in an impartial game. Nimbers are most closely associated with the game Nim, where the nimber of a heap is the number of objects in that heap.
The nimbers are indexed by ordinal numbers and form a subclass of surreal numbers, but are endowed with nimber addition and nimber multiplication, which are distinct from both ordinal arithmetic operations and arithmetic operations of surreal numbers. Because of the Sprague–Grundy theorem, which states that every impartial game is equivalent to a Nim heap of a certain size, nimbers arise in a much larger class of impartial games.
They can be used to analyse games such as Nim, Cram, Northcott's game, and the impartial version of Hackenbush. Nimber addition and multiplication are associative and commutative. Nimber addition has 0 as its additive identity, and each nimber is its own additive inverse.
For finite nimbers, nimber addition can be calculated using the bitwise exclusive or (XOR) operation. The class of nimbers, under nimber addition and multiplication, forms a field except that it is a proper class rather than a set. Nimbers are often denoted using a star notation \{*0, *1, *2, ..., *\omega, *(\omega+1), ...\} .
Alternatively, expressions that are interpreted as ordinary arithmetic are customarily enclosed in square brackets; for example, 2^2 = *(2)^2 = 3 in nim-multiplication, but [2^2] = *(2^2) = 4 . \alpha \oplus \beta = \operatorname{mex} \! \bigl( \{ \alpha' \oplus \beta : \alpha' where the minimum excludant of a set of ordinals is defined to be the smallest ordinal that is not an element of . For finite ordinals, the nim-sum is easily evaluated on a computer by taking the bitwise exclusive or (XOR, denoted by ) of the binary representations 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 XOR of these two binary numbers is the binary number 1001, so their nim-sum is 9. This property of addition follows from the fact that both 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. \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 \zeta \oplus \gamma = \alpha \oplus \beta > \gamma, we must have either \begin{align} \alpha > \zeta \oplus \alpha &= \beta \oplus \gamma, \quad\text{or}\\[4pt] \beta > \zeta \oplus \beta &= \alpha \oplus \gamma. \end{align} Thus is included as either \begin{align} (\beta \oplus \gamma) \oplus \beta, \quad\text{or}\\[4pt] \alpha \oplus (\alpha \oplus \gamma); \end{align} and hence is the minimum excluded ordinal. Nimber addition is associative and commutative, with as the additive identity element.
Moreover, a nimber is its own additive inverse. It follows that if and only if . \alpha \otimes \beta = \operatorname{mex} \, \{(\alpha' \otimes \beta) \oplus (\alpha \otimes \beta') \oplus (\alpha' \otimes \beta') : \alpha' Nimber multiplication is associative and commutative, with the ordinal as the multiplicative identity element.
Moreover, nimber multiplication distributes over nimber addition. 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 \alpha^{-1} = \operatorname{mex}(S), where is the smallest set of ordinals (nimbers) such that is an element of ; if and is an element of , then (1 \oplus (\alpha' \oplus \alpha) \otimes \beta') \otimes (\alpha')^{-1} is also an element of . For all natural numbers , the set of nimbers less than form the Galois field of order .
Therefore, the set of finite nimbers is isomorphic to the direct limit as of the fields . This subfield is not algebraically closed, since no field with not a power of 2 is contained in any of those fields, and therefore not in their direct limit; for instance the polynomial , which has a root in , 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 The nimber product of a Fermat 2-power (numbers of the form ) with a smaller number is equal to their ordinary product; The nimber square of a Fermat 2-power is equal to .
Subsequent extensions to infinite nimbers add extensions for each prime degree; for example, the next set of extensions (up to ) are those of degree over the finite nimbers: ; For , . 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.
The next transcendental element is unknown.
Generalizations
A similar field over the class of all ordinals can be constructed for each prime characteristic , in which addition is interpreted as base- addition without carry, and so on, but the definitions are more complicated. For example, nim-addition in is recursively defined as: \alpha \oplus \beta = \operatorname{mex}(\{ \alpha' \oplus \beta : \alpha' The structure of each is similar below : a series of quadratic extensions up to , followed by extensions for each prime degree up to each , with as the smallest transcendental element.
The finite nimbers form the direct limit of for all , such that the product of distinct Fermat p-powers (numbers of the form ) is their ordinary product, and the square of a Fermat p-power is defined such that there is a primitive element. For example, for , we can take , , and for .
A general definition for nim-addition and nim-multiplication modulo p, including the rules for nimbers less than , has been described. It is also possible to define of characteristic 0 using the inductive definition of . In this case, the smallest field is the ordinals less than , and it is isomorphic to the rational numbers.
See also
Surreal number
References
which discusses games, surreal numbers, and nimbers.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1375146150 under CC BY-SA 4.0; modifications have been made.