Nimber

Last updated February 12, 2024

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 numbers endowed with nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.

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.^[2]

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 $2 \times n$ board will have a nimber of 0 for all even $n$ and a nimber of 1 for all odd $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.^[3]

Hackenbush

Hackenbush is a game invented by mathematician John Horton 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

{\displaystyle \alpha \oplus \beta =\operatorname {mex} \!{\bigl (}\{\alpha '\oplus \beta

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 $\oplus$ ) 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 $α \oplus β$ is $β$ , and vice versa; thus $α \oplus β$ is excluded.

{\displaystyle \zeta

On the other hand, for any ordinal $γ < α \oplus β$ , 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

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

thus $γ$ is included as either

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

and hence $α \oplus β$ 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 $α \oplus β = 0$ if and only if $α = β$ .

Multiplication

Nimber multiplication (nim-multiplication) is defined recursively by

\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

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

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

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

For all natural numbers $n$ , the set of nimbers less than $2 2 n$ form the Galois field $GF(2 2 n)$ of order $2 2 n$ . Therefore, the set of finite nimbers is isomorphic to the direct limit as $n \to \infty$ of the fields $GF(2 2 n)$ . 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 3 + x + 1$ , which has a root in $GF(2 3)$ , 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 $2 2 n$ ) with a smaller number is equal to their ordinary product;
The nimber square of a Fermat 2-power $x$ is equal to $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 $ω ω ω$ , where $ω$ is the smallest infinite ordinal. It follows that as a nimber, $ω ω ω$ is transcendental over the field.^[5]

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 $2 2 n$ . (If you prefer simple text tables, they are here .)

Notes

↑ Advances in computer games : 14th International Conference, ACG 2015, Leiden, the Netherlands, July 1-3, 2015, Revised selected papers. Herik, Jaap van den,, Plaat, Aske,, Kosters, Walter. Cham. 2015-12-24. ISBN 978-3319279923. OCLC 933627646.{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: others (link)
↑ Anany., Levitin (2012). Introduction to the design & analysis of algorithms (3rd ed.). Boston: Pearson. ISBN 9780132316811. OCLC 743298766.
↑ "Theory of Impartial Games" (PDF). Feb 3, 2009.
1 2 Brown, Ezra; Guy, Richard K. (2021). "2.5 Nim arithmetic and Nim algebra". The Unity of Combinatorics. Vol. 36 of The Carus Mathematical Monographs (reprint ed.). American Mathematical Society. p. 35. ISBN 978-1-4704-6509-4.
↑ Conway 1976, p. 61.

Related Research Articles

In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.

<span class="mw-page-title-main">Limit ordinal</span> Infinite ordinal number class

In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal. Alternatively, an ordinal λ is a limit ordinal if there is an ordinal less than λ, and whenever β is an ordinal less than λ, then there exists an ordinal γ such that β < γ < λ. Every ordinal number is either zero, or a successor ordinal, or a limit ordinal.

The fixed-point lemma for normal functions is a basic result in axiomatic set theory stating that any normal function has arbitrarily large fixed points. It was first proved by Oswald Veblen in 1908.

In mathematics, especially in the area of abstract algebra known as ring theory, a free algebra is the noncommutative analogue of a polynomial ring since its elements may be described as "polynomials" with non-commuting variables. Likewise, the polynomial ring may be regarded as a free commutative algebra.

<span class="mw-page-title-main">SO(8)</span> Rotation group in 8-dimensional Euclidean space

In mathematics, SO(8) is the special orthogonal group acting on eight-dimensional Euclidean space. It could be either a real or complex simple Lie group of rank 4 and dimension 28.

In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations.

In abstract algebra, the Chien search, named after Robert Tienwen Chien, is a fast algorithm for determining roots of polynomials defined over a finite field. Chien search is commonly used to find the roots of error-locator polynomials encountered in decoding Reed-Solomon codes and BCH codes.

In mathematics, the epsilon numbers are a collection of transfinite numbers whose defining property is that they are fixed points of an exponential map. Consequently, they are not reachable from 0 via a finite series of applications of the chosen exponential map and of "weaker" operations like addition and multiplication. The original epsilon numbers were introduced by Georg Cantor in the context of ordinal arithmetic; they are the ordinal numbers ε that satisfy the equation

In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable ordinal notations. However, it is not possible to decide effectively whether a given putative ordinal notation is a notation or not ; various more-concrete ways of defining ordinals that definitely have notations are available.

In mathematics, the Schur orthogonality relations, which were proven by Issai Schur through Schur's lemma, express a central fact about representations of finite groups. They admit a generalization to the case of compact groups in general, and in particular compact Lie groups, such as the rotation group SO(3).

In mathematics, the Veblen functions are a hierarchy of normal functions, introduced by Oswald Veblen in Veblen (1908). If φ₀ is any normal function, then for any non-zero ordinal α, φ_α is the function enumerating the common fixed points of φ_β for β<α. These functions are all normal.

In mathematical logic and set theory, an ordinal collapsing function is a technique for defining certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger than the one being defined, perhaps even large cardinals, and then "collapse" them down to a system of notations for the sought-after ordinal. For this reason, ordinal collapsing functions are described as an impredicative manner of naming ordinals.

In set theory, a branch of mathematics, an additively indecomposable ordinalα is any ordinal number that is not 0 such that for any $, we have Additively indecomposable ordinals were named the gamma numbers by Cantor, p.20 and are also called additive principal numbers . The class of additively indecomposable ordinals may be denoted, from the German "Hauptzahl". The additively indecomposable ordinals are precisely those ordinals of the form for some ordinal .$

In the mathematical theory of games, genus theory in impartial games is a theory by which some games played under the misère play convention can be analysed, to predict the outcome class of games.

In combinatorial game theory, and particularly in the theory of impartial games in misère play, an indistinguishability quotient is a commutative monoid that generalizes and localizes the Sprague–Grundy theorem for a specific game's rule set.

In set theory, a branch of mathematics, the Milner – Rado paradox, found by Eric Charles Milner and Richard Rado (1965), states that every ordinal number $less than the successor of some cardinal number can be written as the union of sets where is of order type at most κ n for n a positive integer.$

In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals aimed to extend enumeration to infinite sets.

In mathematics, Ricci calculus constitutes the rules of index notation and manipulation for tensors and tensor fields on a differentiable manifold, with or without a metric tensor or connection. It is also the modern name for what used to be called the absolute differential calculus, developed by Gregorio Ricci-Curbastro in 1887–1896, and subsequently popularized in a paper written with his pupil Tullio Levi-Civita in 1900. Jan Arnoldus Schouten developed the modern notation and formalism for this mathematical framework, and made contributions to the theory, during its applications to general relativity and differential geometry in the early twentieth century.

In relativistic quantum mechanics and quantum field theory, the Joos–Weinberg equation is a relativistic wave equation applicable to free particles of arbitrary spin $j$ , an integer for bosons or half-integer for fermions. The solutions to the equations are wavefunctions, mathematically in the form of multi-component spinor fields. The spin quantum number is usually denoted by $s$ in quantum mechanics, however in this context $j$ is more typical in the literature.

Buchholz's psi-functions are a hierarchy of single-argument ordinal functions $introduced by German mathematician Wilfried Buchholz in 1986. These functions are a simplified version of the -functions, but nevertheless have the same strength as those. Later on this approach was extended by Jäger and Schütte.$

References

Conway, John Horton (1976). On Numbers and Games. Academic Press Inc. (London) Ltd.
Lenstra, H. W. (1978). Nim multiplication. Report IHES/M/78/211. Institut des hautes études scientifiques. hdl:1887/2125.
Schleicher, Dierk; Stoll, Michael (2004). "An Introduction to Conway's Games and Numbers". arXiv: math.DO/0410026 . which discusses games, surreal numbers, and nimbers.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Advances in computer games : 14th International Conference, ACG 2015, Leiden, the Netherlands, July 1-3, 2015, Revised selected papers. Herik, Jaap van den,, Plaat, Aske,, Kosters, Walter. Cham. 2015-12-24. ISBN 978-3319279923. OCLC 933627646.{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: others (link)

[2] Anany., Levitin (2012). Introduction to the design & analysis of algorithms (3rd ed.). Boston: Pearson. ISBN 9780132316811. OCLC 743298766.

[3] "Theory of Impartial Games" (PDF). Feb 3, 2009.

[Unity2021-4] 1 2 Brown, Ezra; Guy, Richard K. (2021). "2.5 Nim arithmetic and Nim algebra". The Unity of Combinatorics. Vol. 36 of The Carus Mathematical Monographs (reprint ed.). American Mathematical Society. p. 35. ISBN 978-1-4704-6509-4.

[5] Conway 1976, p. 61.

[1]

[2]

[3]

[4]

[5]