(A substantial part of this post was rewritten since it was first posted. I managed to mangle things while editing, and the result was not particularly comprehensible: for example, in the original version of the post, I managed to delete the definition of "mex", which continuing to use mex in several other definitions. I've tried to clear it up. Sorry for the confusion!)
This is actually a post in the surreal numbers series, even though it's not going to look like one. It's going to look like an introduction to another very strange system of numbers, called nimbers. But nimbers are a step on the path from
surreal numbers to games and game theory.
Nimbers come from a very old game called Nim. We'll talk more about Nim later, but it's one of the oldest strategy games known. The basic idea of it is that you have
a couple of piles of stones. Each turn, each player can take some stones from one of the piles. Whoever is left making the last move loses. It seems like a very trivial game. But it turns out that you can reduce pretty much every impartial game to some variation of Nim.
Analyzing Nim mathematically, you wind up finding that it re-creates the concept of ordinal numbers, which is what surreals are also based on. In fact, creating nimbers can end up re-creating the surreals. But that's not what we're going to do here: we're going to create the nimbers and the basic nimber addition and multiplication
operations.
The trick to creating nimbers is going to be using an ordinal process where we don't distinguish between left and right sets in the nimbers, but we use the idea of the corresponding surreals to define things like ≤. And using this non-distinguishing
ordinal process, we're going to create numbers that form a (peculiar) field. In fact, we're going to get the number field with characteristic 2 - meaning a number field where
each number is its own additive opposite.
So we start with ordinal 0. Obviously, ordinal 0 defines the number 0 - the additive identity. After that, for successive ordinals, we'll just play around with a definition of addition based on the idea of the minimum excluded ordinal: the smallest ordinal which is not yet a part of our set. The sum of two of two ordinals can't exist before the ordinals themselves - and we'll exploit that. So we'll define things in terms of the minimum exluded ordinal (mex) the minimum ordinal number which isn't yet part of the set of nimbers.
So we've got zero. And we can't add any new numbers using addition - because 0+0=0. So we look for the mex of the set of defined ordinals: mex({0}). That's 1. So now we have two numbers, 0 and 1.
Now, for successive generations, we're going to use nimber addition. Given two nimbers A and B, A+B = mex({A'+B : A'<A} ∪ {A+B': B'<B}). Using that, we get a set of new nimbers defined from the sums of existing nimbers. Each time we've exhausted the new numbers that can be generated using sums, we'll create a new nimber by taking the mex of the nimbers that we've defined so far.
Nimber addition, as defined above, is strange. Let's take a moment and look at why. In nimber addition, what's 1+1? It's 0: 1 is its own additive inverse. In fact, we'll find that every nimber is its own additive inverse: N+N=0 for all N. And if we work through from there, we'll find that we can treat every number as its binary expansion, and cancel pairs of the same power of two. So, for example, we can take thu nimber sum of 7 and 9: 7=4+2+1; 9=8+1; so 7+9=(4+2+1)+(8+1) = 8+4+2+1+1; cancel the pair of ones, and it equals 8+4+2 = 14. For another example, we can take the nimber sum of 15 (8+4+2+1) and 6 (4+2) = 8+4+4+2+2+1; cancel the pair of 4s and the pair of twos, and we get 8+1=9. So 15+6=9. So for any two nimbers A and B, the addition operation is really bitwise exclusive-or of the binary expansion of the number. (The first addition example in this paragraph originally contained a typo: when I re-arranged the additive expansion terms, I changed a 1 to a 2. Thanks to alert commenters who noticed and pointed that out.)
What about multiplication? Well, it's similar to addition: A×B = mex(A'×B + A×B' : A'<A and B'<B). The nimber product of any two nimbers ends up being the nimber sum of numbers of the form 22n. Those numbers are called Fermat 2-powers. In nimber multiplication, the nimber product of two distinct Fermat 2-powers is their product in the normal surreal number field. The nimber-product of any Fermat 2-power N with itself it 3N/2.
So what's 4×4? 6. 4×6? Well, 6=4+2, so 4×6=4×(4+2)=4×4 + 4×2. We know 4×4=6, so that's 6+(4×2) = 6+8=14.
How about 4×10? Well, 10=8+2. 8=4×2. So 10=4×2+2. So 4×10 =
4×(4×2+2) = 4×4×2 + 4×2 = 6×2 + 8 = (4+2)×2 + 8 = 8+3+8=8+8+3=0+3=3.
All of this works out to give us a new field of ordinal numbers. Yes - this crazy stuff actually does work out to be a field. And these operations actually do make sense, in a strange way. When you start analyzing games, any impartial game is equivalent to a game of Nim for some set of piles. And given a game of Nim two piles of size A and B, there's an equivalent game of Nim with one pile - and the size of that pile is the nimber sum A+B.
There's a similar reason why the product makes sense. But we'll get back to that
some other time.
- Log in to post comments
What is mex(A, B)?
Alexey:
Sorry - I spent so much time rewriting this post trying to make it comprehensible, I accidentally deleted the definition of mex!
The mex of a set of nimbers is the minimum excluded ordinal: the smallest ordinal number not included in the set.
Would not 7+9 be 14?
I think I'm confused about Nimber multiplication. You're saying that 2x2=3, but from the definition, it looks to me like 2x2 should be mex(0x2+2x0, 1x2+2x0, 0x2+2x1, 1x2+2x1)=mex(0+0, 2+0, 0+2, 2+2) = mex(0,2,2,0) = 1.
Did I get something wrong there?
The theory of impartial combinatorial games Mark describes (played under the "last player to move wins," or 'normal play' convention) is called the Sprague-Grundy theory.
It might be of interest to point out that the Sprague-Grundy theory has been recently generalized to misere play (last player to move loses). The misere analogue of nim addition is given by a commutative monoid, the misere quotient. Misere quotients are localized to the rules of a particular game. Lots of previously unsolved misere combinatorial games have now been solved using the theory, but there are many open algebraic questions about the mysterious misere quotient algebras themselves.
Come to miseregames.org and join the fun if you like; there's lots more to do...
In adding 7+9 you have:
7+9=(4+2+1)+(8+1)
=8+4+2+2+1
But shouldn't this be
=8+4+2+1+1 = 8+4+2 = 14
?
Dirac:
Yes, you're exactly right. I miscopied the additive expansion, which led me to an incorrect result.
I looked up "impartial game" on wikipedia, and I discovered something wonderful. Typical boardgames like chess and go aren't impartial (as far as I understand) since players have different options - the black player can only place/move black pieces and so on. But I've recently discovered the noveau abstract game Zertz, which is so wonderfully mind-bending precisely because it is an impartial game. Both players play from the same pool of marbles, and there's no use setting traps, because your opponent can immediately spring them on you. I wonder if Zertz is vulnerable to analysis because of this odd nim-equivalience you mentioned?
Mark, I thought that you would find it interesting that Nim was played for money on a TV show in Spain in the nineties. The show (called "Hola, Rafaella") had a magician who each week would challenge one viewer who called on the phone. With a different notation, they would play Nim, always starting with the position (2,3,4). The viewer could choose whether to go first or second. If the viewer beated the magician, he would win some money. This little game was part of the show for various months and only one viewer was able to beat the magician. I could not believe it.
In your definition of multiplication, you differ from the one in Wikipedia, which includes the term -A'xB'. I believe this is necessary to get the result "1" when calculating an intermediate step for multiplying 2x2, to then make the answer 3. (Otherwise 2x2 would be 1, which would lead to further problems).