Editing Nimber

{{short description|Number used in combinatorial game theory}}
{{Distinguish|Number}}
{{multiple issues|
 {{lead extra info|date=January 2019}}
 {{inadequate lead|date=January 2019}}
}}

In [[mathematics]], the '''nimbers''', also called '''Grundy numbers''', are introduced in [[combinatorial game theory]], where they are defined as the values of heaps in the game [[Nim]].  The nimbers are the [[ordinal number]]s endowed with ''nimber addition'' and ''nimber multiplication'', which are distinct from [[ordinal addition]] and [[ordinal multiplication]].

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 may also occur in [[partisan game]]s like [[Domineering]].

The nimber addition and multiplication operations are associative and commutative. Each nimber is its own [[additive inverse]].  In particular for some pairs of ordinals, their nimber sum is smaller than either addend.<ref>{{Cite book|title=Advances in computer games : 14th International Conference, ACG 2015, Leiden, the Netherlands, July 1-3, 2015, Revised selected papers|others=Herik, Jaap van den,, Plaat, Aske,, Kosters, Walter|isbn=978-3319279923|location=Cham|oclc=933627646|date = 2015-12-24}}</ref>  The [[minimum excludant]] operation is applied to sets of nimbers.

== Uses ==

=== Nim ===
{{main|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.<ref>{{Cite book|title=Introduction to the design & analysis of algorithms|last=Anany.|first=Levitin|date=2012|publisher=Pearson|isbn=9780132316811|edition=3rd|location=Boston|oclc=743298766}}</ref>

=== Cram ===
{{main|Cram (game)}}
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 {{math|2 × ''n''}} board will have a nimber of 0 for all even {{mvar|n}} and a nimber of 1 for all odd {{mvar|n}}.

=== 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.<ref>{{Cite web|url=http://web.mit.edu/sp.268/www/nim.pdf|title=Theory of Impartial Games|date=Feb 3, 2009}}</ref>

=== Hackenbush ===
{{main|Hackenbush}}
Hackenbush is a game invented by mathematician [[John Horton Conway]]. It may be played on any configuration of colored [[line segment]]s 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
<math display=block>\alpha \oplus \beta = \operatorname{mex} \! \bigl( \{ \alpha' \oplus \beta : \alpha' < \alpha \} \cup \{\alpha \oplus \beta' : \beta' < \beta \} \bigr),</math>
where the [[minimum excludant]] {{math|mex(''S'')}} of a set {{mvar|S}} of ordinals is defined to be the smallest ordinal that is ''not'' an element of {{mvar|S}}.

For finite ordinals, the '''nim-sum''' is easily evaluated on a computer by taking the [[Bitwise operation|bitwise]] [[exclusive or]] (XOR, denoted by {{math|⊕}}) 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 {{math|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 {{mvar|α}} and {{mvar|β}} 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 {{mvar|α}} is {{math|''α'' ⊕ ''β''}} is {{mvar|β}}, and vice versa; thus {{math|''α'' ⊕ ''β''}} is excluded. 
<math display=block>\zeta := \alpha \oplus \beta \oplus \gamma</math> 
On the other hand, for any ordinal {{math|''γ'' < ''α'' ⊕ ''β''}}, XORing {{mvar|ζ}} with all of {{mvar|α}}, {{mvar|β}} and {{mvar|γ}} must lead to a reduction for one of them (since the leading 1 in {{mvar|ζ}} must be present in at least one of the three); since 
<math display=block>\zeta \oplus \gamma = \alpha \oplus \beta > \gamma,</math> 
we must have either
<math display=block>\begin{align}
\alpha > \zeta \oplus \alpha &= \beta \oplus \gamma, \quad\text{or}\\[4pt]
\beta > \zeta \oplus \beta &= \alpha \oplus \gamma.
\end{align}</math>
Thus {{mvar|γ}} is included as either
<math display=block>\begin{align}
(\beta \oplus \gamma) \oplus \beta, \quad\text{or}\\[4pt]
\alpha \oplus (\alpha \oplus \gamma);
\end{align}</math>
and hence {{math|''α'' ⊕ ''β''}} is the minimum excluded ordinal.

Nimber addition is [[associative]] and [[commutative]], with {{math|0}} as the additive [[identity element]]. Moreover, a nimber is its own [[additive inverse]].<ref name=Unity2021>{{cite book |title=The Unity of Combinatorics |first=Ezra |last=Brown |authorlink=Ezra Brown |first2=Richard K. |last2=Guy |author-link2=Richard K. Guy |section=2.5 Nim arithmetic and Nim algebra|page=35 |publisher=[[American Mathematical Society]] |year=2021 |isbn=978-1-4704-6509-4 |volume=36 of The Carus Mathematical Monographs |edition=reprint}}</ref> It follows that {{math|1=''α'' ⊕ ''β'' = 0}} [[if and only if]] {{math|1=''α'' = ''β''}}.

== Multiplication ==
Nimber multiplication ('''nim-multiplication''') is defined recursively by

<math display=block> \alpha \, \beta = \operatorname{mex} \! \bigl(\{\alpha' \beta \oplus \alpha \, \beta' \oplus \alpha' \beta' : \alpha' < \alpha, \beta' < \beta \} \bigr).</math>

Nimber multiplication is associative and commutative, with the ordinal {{math|1}} as the multiplicative [[identity element]]. Moreover, nimber multiplication [[Distributive property|distributes over]] nimber addition.<ref name=Unity2021/>

Thus, except for the fact that nimbers form a [[class (set theory)|proper class]] and not a set, the class of nimbers forms a [[ring (algebra)|ring]]. In fact, it even determines an [[algebraically closed field]] of [[characteristic (algebra)|characteristic]] 2, with the nimber multiplicative inverse of a nonzero ordinal {{mvar|α}} given by

<math display=block>\alpha^{-1}  = \operatorname{mex}(S),</math>
where {{mvar|S}} is the smallest set of ordinals (nimbers) such that
# {{math|0}} is an element of {{mvar|S}};
# if {{math|0 < ''α''′ < ''α''}} and {{mvar|β'}} is an element of {{mvar|S}}, then <math>\tfrac{1 + (\alpha' \oplus \alpha) \beta'}{\alpha'}</math> is also an element of {{mvar|S}}.

For all natural numbers {{mvar|n}}, the set of nimbers less than {{math|2<sup>2<sup>''n''</sup></sup>}} form the [[Galois field]] {{math|GF(2<sup>2<sup>''n''</sup></sup>)}} of order&nbsp;{{math|2<sup>2<sup>''n''</sup></sup>}}. Therefore, the set of finite nimbers is isomorphic to the [[direct limit]] as {{math|''n'' → ∞}} of the fields {{math|GF(2<sup>2<sup>''n''</sup></sup>)}}. This subfield is not algebraically closed, since no field {{math|GF(2<sup>''k''</sup>)}} with {{mvar|k}} not a power of 2 is contained in any of those fields, and therefore not in their direct limit; for instance the polynomial {{math|''x''<sup>3</sup> + ''x'' + 1}}, which has a root in {{math|GF(2<sup>3</sup>)}}, 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 {{math|2<sup>2<sup>''n''</sup></sup>}}) with a smaller number is equal to their ordinary product;
# The nimber square of a Fermat 2-power {{mvar|x}} is equal to {{math|3''x''/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 {{mvar|ω<sup>ω<sup>ω</sup></sup>}}, where {{mvar|ω}} is the smallest infinite ordinal. It follows that as a nimber, {{mvar|ω<sup>ω<sup>ω</sup></sup>}} is [[transcendental number|transcendental]] over the field.<ref>Conway 1976, p.&nbsp;61.</ref>

== 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&nbsp;{{math|2<sup>2<sup>''n''</sup></sup>}}.
<small>(If you prefer simple text tables, they are {{Oldid|page=Nimber|oldid=383699838|label=here}}.)</small>

[[File:Z2^4; Cayley table; binary.svg|thumb|center|500px|Nimber addition {{OEIS|A003987}}<br>This is also the [[Cayley table]] of [[List of small groups#List of small abelian groups|Z<sub>2</sub><sup>4</sup>]] – or the table of [[Bitwise operation|bitwise]] [[w:Exclusive or|XOR]] operations.<br>The small matrices show the single digits of the binary numbers.]]

[[File:Nimbers 0...15 multiplication.svg|thumb|center|500px|Nimber multiplication {{OEIS|A051775}}<br>The nonzero elements form the [[w:Cayley table|Cayley table]] of [[w:List of small groups#List of small abelian groups|Z<sub>15</sub>]].<br>The small matrices are permuted binary [[Walsh matrix|Walsh matrices]].]]

[[File:Nimber products of powers of two.svg|thumb|center|900px|Nimber multiplication of [[Power of two|powers of two]] {{OEIS|A223541}}<br>Calculating the nim-products of powers of two is a decisive point in the recursive algorithm of nimber-multiplication.]]

==See also==
* [[Surreal number]]

==Notes==
{{reflist}}

==References==
{{refbegin}}
* {{cite book
|first1=John Horton
|last1=Conway
|authorlink1=John Horton Conway
|title=On Numbers and Games
|publisher=[[Academic Press]] Inc. (London) Ltd.
|year=1976
|title-link=On Numbers and Games
}}
* {{cite book
|first1=H. W.
|last1=Lenstra
|authorlink1=Hendrik Willem Lenstra, Jr.
|title=Nim multiplication
|series = Report IHES/M/78/211
|institution= Institut des hautes études scientifiques
|hdl=1887/2125
|year=1978
}}
* {{cite arXiv
|first1=Dierk
|last1=Schleicher
|first2=Michael
|last2=Stoll
|eprint=math.DO/0410026
|title= An Introduction to Conway's Games and Numbers|year=2004
}} which discusses games, [[surreal number]]s, and nimbers.
{{refend}}
{{Authority control}}
[[Category:Combinatorial game theory]]
[[Category:Finite fields]]
[[Category:Ordinal numbers]]