Talk:Nimber

This article is rated C-class on Wik.ipedia.Pro's content assessment scale. It is of interest to the following WikiProjects:

Game theory Mid‑importance This article is part of WikiProject Game theory, an attempt to improve, grow, and standardize Wik.ipedia.Pro's articles related to Game theory. We need your help! Join in | Fix a red link | Add content | Weigh inGame theoryWik.ipedia.Pro:WikiProject Game theoryTemplate:WikiProject Game theorygame theory articles Mid This article has been rated as Mid-importance on the . Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wik.ipedia.Pro. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWik.ipedia.Pro:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles Low This article has been rated as Low-priority on the project's priority scale.

Pleas for the love of pete one of you super smart peole make a youtube video... some of us cant even read and there is literally nothing relevant that come up on yt when searching nimber. I'm sorry that my life has turned out the way it has but please somebody.... 68.13.124.209 (talk) —Preceding undated comment added 04:30, 2 August 2017 (UTC)[reply]

Nice article! I didn't understand this:

(2) The nimber square of a Fermat 2-power x is equal to the standard value of 3x/2.

What does "standard value of 3x/2" mean? AxelBoldt 01:50 Jan 5, 2003 (UTC)

Thanks. The part that you asked about has been edited. It means the value of 3x/2 under the ordinary multiplication of natural numbers, so that the nimber square of 2 is 3, the nimber square of 4 is 6, the nimber square of 16 is 24, the nimber square of 256 is 384, etc. David McAnally 21:22 Jul 1, 2004 (AEST)

Other than the clumsy workaround 2^{2^n} or some sort of graphic (such as appears on the Fermat number page), is there any way to get Wik.ipedia.Pro to deal with nested exponents? I changed to the above workaround, as the previous format looked like 2²n in my browser. MJSS 20:29, 3 Sep 2004 (UTC)

If worse comes to worst you could resort to TeX and write: ${\displaystyle 2^{2^{n}}}$. Formerly, TeX looked good when "displayed" and often looked terrible when embedded in lines of text. Now it may look less than beautiful, but usually is nowhere near as bad as it used to be. Of course, if you're going to "display" it, thus

${\displaystyle \int _{0}^{\infty }1\,dx}$

then using TeX works well. Michael Hardy 22:17, 3 Sep 2004 (UTC)

Oh -- one more thing. The paragraph I wrote above was already indented, so I need to indent the "displayed" TeX twice. Michael Hardy 22:18, 3 Sep 2004 (UTC)

There is a similar problem with omega^omrga^omega at the point where it was pointed out that the set of nimbers less than omega^omega^omega is an algebraically closed field. Like 2^2^n, it does not look right, although it once did.

David McAnally 25 Septemeber, 2004

What does the following look like to you?

${\displaystyle \omega ^{\omega ^{\omega }}\neq 2^{2^{n}}.}$

Specifically where in the article is the problem you're referring to?

Michael Hardy 00:14, 26 Sep 2004 (UTC)

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

This definition doesn't make any sense to me. There are too many colons and commas inside the set braces. Revolver 19:19, 27 July 2005 (UTC)[reply]

I have modified the definition to

α + β = mex({α ′ + β : α ′ < α} ∪ {α + β ′ : β ′ < β}).

This should make it more understandable. Figaro 3:01, 13 August, 2005 (EST)

Okay, I thought that may have been one intended meaning. I'm still not sure I understand addition, though. If α and β are finite ordinals, with α not zero, then it seems that

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

If α and β are both nonzero, then

({α ′ + β : α ′ < α} ∪ {α + β ′ : β ′ < β}) = {min{α, β}, ..., α + β − 1}

so that

mex({α ′ + β : α ′ < α} ∪ {α + β ′ : β ′ < β}) = 0

If α = β = 0, it's also = 0, since the argument of the mex function is the empty set.

If one of them is zero, the other not, say α not zero, but β = 0, then it should be = α

This seems to agree with your exclusive-or definition, except for the case where each is nonzero. Where am I making a mistake? Revolver 20:51, 13 August 2005 (UTC)[reply]

The definition of addition is recursive, so that, in the definition

α + β = mex({α ′ + β : α ′ < α} ∪ {α + β ′ : β ′ < β}),

the addition on the right hand side is not ordinal addition, but nimber addition. Your suggestions above use ordinal addition. It is possible to prove by induction that α + 0 = α for all nimbers α. Similarly, 0 + α = α for all nimbers α. It follows that

1 + 1 = mex{{0 + 1, 1 + 0}) = mex({1, 1}) = 0,

1 + 2 = mex(0 + 2, 1 + 0, 1 + 1}) = mex({2, 1, 0}) = 3,

2 + 1`= mex({0 + 1, 1 + 1, 2 + 0}) = mex({1, 0, 2}) = 3,

1 + 3 = mex({0 + 3, 1 + 0, 1 + 1, 1 + 2}) = mex({3, 1, 0, 3}) = 2,

3 + 1 = mex({0 + 1, 1 + 1, 2 + 1, 3 + 0}) = mex({1, 0, 3, 3}) = 2,

2 + 2 = mex({0 + 2, 1 + 2, 2 + 0, 2 + 1}) = mex({2, 3, 2, 3}) = 0,

and so on. The exclusive-or evaluation of the sum of two finite nimbers is provable by induction on the rwo nimbers. Figaro 19:23 17 August, 2005 (AEST)

Yup. My fault for missing the word "recursively"! Revolver 03:52, 18 August 2005 (UTC)[reply]

I think it would be good to include addition and multiplication tables for the range 0-15. I've done the computation but I'm not sure how to format it. (I'm also not sure whether decimal, hex, or binary would be most illustrative. Thoughts?) 75.36.182.157 00:56, 15 April 2007 (UTC) Never mind. I looked up the formatting info for myself, decided on decimal as most appropriate, and boldly went ahead with the new section. 75.36.182.157 10:18, 21 April 2007 (UTC)[reply]

The sources cited and those I have read are set up so that nimbers are not a countable set, but rather are a proper class, larger than any set. Various subclasses of nimbers are interesting, including both a very small subclass which happens to be a set and happens not to be algebraically closed, and also another subclass which happens to be a set and an algebraically closed field. The former was presumably intended by 195.69.84.154, but they also deleted the latter.

It is important to cite sources for Wik.ipedia.Pro. Note that the material challenged by 195.69.84.154 is taken fairly directly from the sources, but the edits by 195.69.84.154 are unsourced and contradict the given sources.

It would not be a problem to include a new source that defines the nimbers to be one of these tiny sets that 195.69.84.154 is probably talking about, and discuss its properties, but this should not interfere with talking about the larger sets and classes of nimbers already discussed in the article and the current sources. JackSchmidt (talk) 17:24, 5 December 2007 (UTC)[reply]

Rereading the online source, it appears that perhaps only a sentence or two is dedicated to the nimbers. Almost everything else is background or explanation of the surreal numbers. Someone might want to check if the reference should be included there, but there are already nice references. At any rate, despite nimbers only getting a quick mention in the online reference, it definitely indicates that they form a proper class. JackSchmidt (talk) 17:53, 7 December 2007 (UTC)[reply]

I have some doubts about algebraically closedness of the nimbers. Of course, they have all roots of irreducible polynomials of degree ${\displaystyle 2^{k}}$... But, by the way, what is the root of ${\displaystyle x^{3}+x+1}$??? 195.69.84.154 (talk) 13:18, 26 February 2008 (UTC)[reply]

Well, it's more than ω and less than ${\displaystyle \omega ^{\omega ^{\omega }}}$. There's no reason the nim-product of two infinite ordinals can't be finite. But if you want to understand how to solve equations like this in general I'm afraid you have to read On Numbers And Games. 18.21.0.86 (talk) 22:53, 3 May 2008 (UTC)[reply]

I also have my doubts on algebraically closedness. I will now prove that the field of nimbers does not contain the field of order 8.

It is pretty straightforward to prove that ${\displaystyle 2^{a}-1}$ divides ${\displaystyle 2^{b}-1}$ iff a divides b.

Take any positive integers x,y, using geometric series we have: ${\displaystyle 2^{x}-1=1+2+2^{2}+...+2^{(}x-1)}$ This, times the sum ${\displaystyle 1+2^{x}+2^{(}2x)+...+2^{(}(y-1)x)}$ gives ${\displaystyle 1+2+2^{2}+...+2^{(}x-1+xy-x)=1+2+...+2^{(}xy-1)=2^{(}xy)-1}$ thus we have ${\displaystyle 2^{x}-1}$ divides ${\displaystyle 2^{(}xy)-1}$ Thus a divides b implies ${\displaystyle 2^{a}-1}$ divides ${\displaystyle 2^{b}-1}$.

For the reverse direction, suppose ${\displaystyle 2^{a}-1}$ divides ${\displaystyle 2^{b}-1}$.

Since ${\displaystyle 2^{a}-1}$ divides itself, it divides the difference ${\displaystyle (2^{b}-1)-(2^{a}-1)}$. Taking the difference of the powerseries gives

2^a + 2^(a+1) + ... + 2^(b-1)

= 2^a ( 1 + 2 + ... + 2^(b-a-1))

Clearly, 2^a - 1 is relatively prime to 2^a, so this implies that 2^a-1 divides

1 + 2 + ... 2^(b-a-1) = 2^(b-a) - 1

Repeating this, we have that 2^a - 1 divides 2^c - 1 for all c congruent to b mod a.

Suppose we have c s.t. 0 < c < a, b congruent to c mod a. Then ${\displaystyle 2^{c}-1<2^{a}-1}$, but ${\displaystyle 2^{c}-1}$ is not 0 since c is not 0. Contradiction. Hence b is congruent to 0 mod a, implying a divides b.

In particular, this proves that the multiplicative group of GF(2^(2^n)), which has order 2^(2^n) - 1, is not divisible by 2^(3) - 1, and thus cannot contain a subgroup of order 2^(3) - 1. Since the multiplicative group of GF(2^3) has order 2^3 - 1, this implies that GF(2^3) is not contained in ANY field GF(2^(2^n)). Taking the claim in the article at face value that the nimbers from 0 to 2^(2^n) - 1 are isomorphic to GF(2^(2^n)), this implies that no finite subfield of the nimbers contains GF(2^3) (or GF(2^x) for any x not a power of 2). Since GF(2^3) is finite, any embedding of it embeds it into a finite subset of the nimbers, we conclude that the field of nimbers does not contain a copy of GF(2^3).

Going back to the previous writer's irreducible polynomial x^3 + x + 1, we can now actually PROVE that there can be no root of this polynomial in the nimbers. If there were an x satisfying this, then x generates a multiplicative subgroup of the nimbers:

x

x^2

x+1

x^2 + x

x^2 + x + 1

x^2 + 1

1

of order 7. If any earlier power of x is 1, then that power is relatively prime to 7, impyling that x is 1, which is false when we substitute the value x=1 into the polynomial. Hence this is definitely a subgroup of order 7. And since for any nimber value x could take, there is a 2^(2^n) above it, this would imply some order 7 subgroup in a 2^(2^n) - 1 group, which we proved is impossible by divisibility considerations.

Thus the nimbers are NOT algebraically closed, as claimed in the article. (Assuming the claim that GF(2^(2^n)) is isomorphic to the first 2^(2^n) nimbers).

Render787 (talk) 22:40, 27 October 2008 (UTC)[reply]

Also, I think you can prove the claim that GF(2^(2^n)) is isomorphic to the first 2^(2^n)) nimbers by showing that that set is closed under multiplication (almost certainly is by a similar argument to showing that it is closed under addition) and under inverses. It certainly appears to be true. Someone should cite a proof of that, though, or else my reasoning above and my deletion of the algebraicaly closed claim would be in error. In either case, either the GF(2^(2^n)) claim or the algebraically closed claim has to go.

Render787 (talk) 23:05, 27 October 2008 (UTC)[reply]

I also just realized on re-reading the article that the claim was only made when infinite nimbers were used... So my proof may not stand... Someone who knows how ordinal arithmetic works with polynomials should point out what these roots are for polynomials like x^3 + x + 1, because that would substantially improve the article and make it much more informative.

My proof above actually shows that the set of finite nimbers is not algebraically closed. I will revert the change.

Render787 (talk) 23:14, 27 October 2008 (UTC)[reply]

I once calculated that ${\displaystyle \omega ^{2}+3\omega }$ is a root of the polynomial ${\displaystyle x^{3}+x+1}$. I just checked, and it seems right. However, I don't have a source to justify addition to the article. Perhaps, it's insignificant enough not to require a source. As hint to the verification, use the fact that ${\displaystyle \omega ^{3}=2}$. DRLB (talk) 16:01, 28 October 2008 (UTC)[reply]

Actually three roots \omega^2+3\omega, 2\omega^2+3\omega,3\omega^2+\omega. All have the form x=y+(1/y) which, if you plug thus into the original equation, gives x^3=2 or x^3=3. Different number cube roots of 2 or 3 give the different x roots given above. Olthe3rd1 (talk) 01:53, 29 June 2019 (UTC)[reply]

Need the right syntax, can my response be edited accordingly? Olthe3rd1 (talk) 01:54, 29 June 2019 (UTC)[reply]

131.215.167.232 changed "nim-addition" (resp. "nim-multiplication") to "nim-dition" (resp. "nim-tiplication"). I've reverted that, as the former spellings have some Google hits including the original books by Conway et al, while the latter spellings seem to have no Web presence other than this page itself. Joule36e5 (talk) 04:45, 17 November 2008 (UTC)[reply]

Does anyone know if there exists a game-theoretic interpretation of nimber multiplication? I've been scouring the net for some time now, and there are a few pages that mention that some such interpretation exists, but none of them actually demonstrate it. —Preceding unsigned comment added by 83.10.99.117 (talk) 23:59, 13 March 2009 (UTC)[reply]

I was wondering that myself. There must be some reason that nimber multiplication is defined as it is, whether related to nim or to game theory more generally. I know the significance of addition to nim – under "normal play", a position is winning for the player who has just moved iff the nim-sum of heap sizes is zero. The article ought to state this, but I'm not sure how best to fit it into the section as it stands. But in any case, what about multiplication? — Smjg (talk) 00:11, 5 January 2014 (UTC)[reply]

To quote "This subset is closed under both operations, since 16 is of the form 2^2^n."

If addition of two nimbers is indeed just XOR, then 16 being of the form 2^n is entirely sufficient. This can also be seen in the table for n=0,1,2,3,4 ie. 2^n = 1,2,4,8,16. Of course, that is not true for multiplication. MaZe Pallas (talk) 05:46, 7 March 2010 (UTC)[reply]

I think you answered your own question. The quote says both operations, and nimber multiplication is only closed within ordinals taking the form 2^2^n (as mentioned in article). TricksterWolf (talk) 19:15, 7 July 2013 (UTC)[reply]

The non prose starts of with the recursive definition of nim addition, but I as a reader have no clue what a nimber is, or how to represent it. Also the recursive definition assumes the reader knows what the primes (') mean applied to nimbers... — Preceding unsigned comment added by 83.134.138.194 (talk) 21:53, 3 May 2012 (UTC)[reply]

A nimber is an ordinal number with two new operations defined on it (nimber addition and nimber multiplication). Nimber addition on two nimbers is the bitwise XOR of the nimbers; multiplication is more complex to define. Finite nimbers are simply the natural numbers (0, 1, 2, 3, etc.). See ordinal number for more detail on transfinite ordinals. TricksterWolf (talk) 18:56, 7 July 2013 (UTC)[reply]

Nimbers are a really neat mathematical concept and there's a lot of fun things you can do with them from a recreational-math standpoint. But the article doesn't convey any of the wonder of nimbers and the useful bits are hidden under deep mathematical symbiology which most people might not even be equipped to unpack, which is a shame, because nimbers are really easy to understand if you explain them in plain English. For crying out loud, the article doesn't even link to the article on Nim!

I wrote this to explain nimbers to friends and think it might be useful to integrate into this article, perhaps rewritten in a more encyclopedic fashion:

There's a game called Nim. In Nim, you have a certain number of piles of objects, and a turn consists of removing some number of objects from a pile. You win if you remove the last object. So you might have a Nim game where you have a pile of 2 objects and a pile of 3 objects. Player A takes an object from the second pile; now you have two piles of 2 objects. Player B takes two objects from the first pile, and then player A wins the game by taking both objects from the second pile.

Nim is of mathematical interest because a wide variety of simple games with specific traits are mathematically equivalent to games of Nim. These games are called impartial games because each player's available moves are identical, and the only difference is whose turn it is to play.

What makes Nim particularly interesting from an analytical standpoint is that you can "add" games of Nim. For instance, let's take the game described above with a pile of 2 and a pile of 3. This is, in itself, two games of Nim - it's a game of Nim with a single pile of 2 added to a game of Nim with a single pile of 3. If we add the "nimbers" for 2 and 3, we should get the nimber for the combined game.

Let's say we're looking at piles of 2, 5, and 11 and want to find the nimber for the combined game. Here's how we do that. First, we turn the numbers into binary numbers: 0010 0101 1011 Then, we count the number of 1s in each column. If it's odd, that column's value is a 1 in the resulting nimber. If it's even, that column's value is a 0. There's one 1 in the leftmost column, one 1 in the next columnm two 1s in the next column, and two in the last column. So the nimber we get is 1100 (the binary number), which is equivalent to 12. Note that if you add two games with the same nimber, you get a value of 0, because each column will either have two 1s or zero 1s.

You can use nimbers to identify whether the first or second player can force a win in a game. If the nimber of a game is 0, then the first player loses given optimal play; if it's any other value, then the first player wins, and their optimal play is to change the game state to make the nimber 0. 24.136.1.234 (talk) 14:37, 8 December 2015 (UTC)[reply]

It would be nice to give some examples for the addition and multiplication of infinite nimbers. For example, what is ${\displaystyle \omega \oplus 1}$? I tried to calculate it using the formula given, getting 0; however I somehow suspect that is not the right result. --93.134.38.51 (talk) 15:27, 17 August 2016 (UTC)[reply]

The addition formula is

α ⊕ β = mex({α′ ⊕ β : α′ < α} ∪ {α ⊕ β′ : β′ < β})

Replacing α with ω and β with 1 gives

ω ⊕ 1 = mex({α′ ⊕ 1 : α′ < ω} ∪ {ω ⊕ β′ : β′ < 1})

Now, α′ < ω means that α′ is any finite nimber. Its bitwise exclusive OR with 1 swaps 0 with 1, swaps 2 with 3, etc. In particular, every possible finite nimber can be achieved. Also, β′ < 1 means that β′ can only be 0 and ω ⊕ 0 = ω. So the minimum excluded nimber is ω + 1. 𝕃eegrc (talk) 15:49, 17 August 2016 (UTC)

Ah, thank you, I now see where I went wrong: I mistakenly used the normal ordinal addition inside the sets. Anyway, I still think the article should give a few infinite examples. --93.134.38.51 (talk) 16:29, 17 August 2016 (UTC)[reply]

Please do. 𝕃eegrc (talk) 16:54, 17 August 2016 (UTC)[reply]

why is it that the text uses the same symbol for both XOR and nim-sum? don't your think that's confusing?

Because, as the article explains, they are more or less the same operation. —David Eppstein (talk) 16:53, 11 May 2019 (UTC)[reply]

What is meant by the subtraction operation in the expression (1+(<alpha>'-<alpha>))<beta>^-1? Why is this not rendered as an addition since nimbers are additive self-inverse? Olthe3rd1 (talk) 23:14, 28 June 2019 (UTC)[reply]

the article says nimbers are a proper class and not a set, but since nimbers are equinumerous with ordinal numbers, and ordinal numbers form a set, I think this is wrong?  AltoStev (talk) 16:25, 21 February 2023 (UTC)[reply]

The ordinals also form a proper class not a set. There is no set of all ordinal numbers, at least not in standard forms of set theory (see universal set). As our ordinal number article states: "The class of all ordinals is not a set." —David Eppstein (talk) 17:02, 21 February 2023 (UTC)[reply]

That seems unusual since natural numbers form a set... but apparently ordinals can have omegas so I was mistaken....

This implies there are infinite nimbers a la infinite ordinals, but it's unclear how they work tbh.  AltoStev (talk) 23:05, 25 February 2023 (UTC)[reply]

Omega-notation only gives you some of the countable ordinals. The ordinals get far bigger than that. —David Eppstein (talk) 23:15, 25 February 2023 (UTC)[reply]

I came to this article from one on game theory and surreals, where the motivating construction is {?|?} where we fill in the blanks. This article doesn't seem to have any of this context. It isn't clear from this article exactly what inductively defined games correspond to the nimbers. It seems to jump directly to assuming all nimbers can be talked about by proxy using a corresponding ordinal. Matthew Pocock (talk) 12:38, 27 August 2023 (UTC)[reply]

Nimbers are not surreal numbers. They both come from the inductive construction of an arithmetic on infinite games, but they are a different subset of the games. The only value they have in common is zero. —David Eppstein (talk) 15:06, 27 August 2023 (UTC)[reply]

Over ten years ago based on what my physics teacher showed us between lessons, we created "Pawn Duel" as an online game as simple illustration for counting moves in chess. It turned out to be a human-comprehensible version of Northcott's game, practical to set up if you have a chess board. Over the course of these years somebody else even got inspired and created a small flash game called "Spartans vs Goblins", which is a graphic version for kids.

I have tried creating a page describing this example as comprehensible, even for kids. It was deleted as too specific. I am not an active wiki contributor and don't know all the practices. Hence, could somebody support me, or point to a place where this practical example of Northcott's game (https://nim.ai1.co/pawnduel/) is appreciated by community? — Preceding unsigned comment added by Okkay (talk • contribs) 23:12, 9 September 2023 (UTC)[reply]