Nimber

As a class, nimbers are indexed by ordinal numbers, and form a subclass of surreal numbers, introduced by John Conway as part of his theory of combinatorial games. However, nimbers are distinct from ordinal and surreal numbers in that they follow distinct arithmetic rules, nim-addition and nim-multiplication. Other than that they are a proper class rather than a set, nimbers form a field under nim-addition and nim-multiplication. The field of nimbers is denoted . As a set, finite nimbers can be put in one-to-one correspondence with finite ordinal numbers, which are the natural numbers. Nonetheless, their arithmetic structures are not isomorphic; nimber arithmetic fundamentally differs from ordinary arithmetic operations on natural numbers. 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. == Uses ==

Nim Nim is a game in which two players take turns removing objects from distinct heaps. As moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric, Nim is an impartial game. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The goal of the game is to be the player who removes the last object. The nimber of a heap is simply the number of objects in that heap. Using nim addition, one can calculate the nimber of the game as a whole. The winning strategy is to force the nimber of the game to 0 for the opponent's turn. Cram Cram is a game often played on a rectangular board in which players take turns placing dominoes either horizontally or vertically until no more dominoes can be placed. The first player that cannot make a move loses. As the possible moves for both players are the same, it is an impartial game and can have a nimber value. For example, any board that is an even size by an even size will have a nimber of 0. Any board that is even by odd will have a non-zero nimber. Any board will have a nimber of 0 for all even and a nimber of 1 for all odd . Northcott's game In Northcott's game, pegs for each player are placed along a column with a finite number of spaces. Each turn each player must move the piece up or down the column, but may not move past the other player's piece. Several columns are stacked together to add complexity. The player that can no longer make any moves loses. Unlike many other nimber related games, the number of spaces between the two tokens on each row are the sizes of the Nim heaps. If your opponent increases the number of spaces between two tokens, just decrease it on your next move. Else, play the game of Nim and make the Nim-sum of the number of spaces between the tokens on each row be 0. Hackenbush Hackenbush is a game invented by mathematician John Conway. It may be played on any configuration of colored line segments connected to one another by their endpoints and to a "ground" line. Players take turns removing line segments. An impartial game version, thereby a game able to be analyzed using nimbers, can be found by removing distinction from the lines, allowing either player to cut any branch. Any segments reliant on the newly removed segment in order to connect to the ground line are removed as well. In this way, each connection to the ground can be considered a nim heap with a nimber value. Additionally, all the separate connections to the ground line can also be summed for a nimber of the game state. == Addition ==

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 \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 . == Multiplication ==

Nimber multiplication (nim-multiplication) is defined recursively by \alpha \otimes \beta = \operatorname{mex} \! \bigl(\{(\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. The next transcendental element is unknown. == Addition and multiplication tables ==

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 . of Z24 – or the table of bitwise XOR operations.The small matrices show the single digits of the binary numbers. of Z15.The small matrices are permuted binary Walsh matrices. Calculating the nim-products of powers of two is a decisive point in the recursive algorithm of nimber-multiplication. ==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==