16
$\begingroup$

I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum appears in Nim. To be more clear, I will explain my current level of understanding. I completely grasp the mechanics of the proofs of both Bouton's Theorem and the Sprague-Grundy Theorem. However, I am looking for an intuitive explanation.

I understand that the binary representations arise as a natural extension of the parity-mirroring arguments in two-heap Nim. However, I would like to know what particular properties of the bit-xor function allow it to work. For example, the bitwise-and would not work for Nim in the same way the bit-xor works; is there some functional equation that the bit-xor fulfills that makes it so ubiquitous?

Note that I am not asking for the motivation for the Sprague Grundy Theorem as in Motivation and Intuition for Sprague-Grundy Theorem. I am asking about the xor function in particular.

Thank you in advance.

By the way, this is my first question, so if anything is wrong, please critique me.

I feel that it it would be helpful to mention further context. I was reading A paper of Fraenkel and Kontorovich which used the bitwise and to explore Nim.

$\endgroup$
  • 2
    $\begingroup$ Is it the right question? I mean, cant we cook up games where say primes or some exotic operator appears also? Nim perhaps just happens to be the right game for xor. But I would be happy to see a different answer. $\endgroup$ – Per Alexandersson Jun 23 '15 at 3:09
  • $\begingroup$ I see your point Per Alexandersson. However, to find such games, very contrived rules would need to be devised. What qualities then of the xor yield such a natural and minimalist game such as Nim? $\endgroup$ – Halbort Jun 23 '15 at 3:12
  • 1
    $\begingroup$ What about the obvious answer "xor is natural and minimalist" doesn't satisfy you? You should make more precise what you are asking here. $\endgroup$ – Johannes Hahn Jun 23 '15 at 13:44
  • 1
    $\begingroup$ @PerAlexandersson : Nim is far less ad hoc than you might think at first glance; arguably, it's canonical in some sense. In Winning Ways they cook up lots of other games, but as long as they're impartial two-person games where the last player to move wins, they all reduce to Nim. XOR arises because of the definition of the sum of two games, as Douglas Zare has explained. If you change the way you combine two games then you can indeed get other operations, but there aren't that many natural ways to combine two games. $\endgroup$ – Timothy Chow Jun 24 '15 at 0:40
  • 1
    $\begingroup$ @MarkS. Of course what you say is correct, but what I was trying to counteract was the notion that Nim is just some arbitrary game with idiosyncratic rules coming out of nowhere, and that we can't expect any kind of deep explanation of the behavior of such an ad hoc structure, any more than we can expect any deep mathematics to emerge from studying the baseball rule book. $\endgroup$ – Timothy Chow Jun 25 '15 at 2:43
13
$\begingroup$

There's something of a good explanation. You accept the Sprague-Grundy theorem, which implies in particular that Nim positions must form a group - any two Nim positions are equivalent to one Nim position, and each Nim position plus itself gets you back to the identity.

OK, but which group? I guess you also know it's a 2-torsion group, so which 2-torsion group?

Well the answer is really simple. Because of how Sprague-Grundy works, each element is the first thing it can possibly be.

So 0 is the identity, because the group has to have one of those. 1 can't be the identity, so it's some other element. 1 is 2-torsion, so now we have a complete group. The next element, 2 must not be in that group, so it's a new element. No we don't have a complete group - we're missing 1+2. So that goes to 3. Now we have a complete group again, so 4 must be a new element. To generate a group from those, we need 4+1, 4+2, 4+3. Those again just go to the first element - 4+1=5, 4+2=6, 4+3=7 and so on.

So choosing the first possible element gets you the xor operation. Conway has generalized this with multiplicative structure, which in fact exists on origi nal numbers, that he calls the "first field" (formerly "nim field") - there each additively new element gets expressed in the simplest way as a product of previous elements, unless the existing numbers already form a complete ring, in which case it forms a new element satisfying the simplest possible polynomial equation, which for finite numbers is always quadratic.

$\endgroup$
  • $\begingroup$ Thank you very much @Will Savin. This is exactly what I was looking for: +1 $\endgroup$ – Halbort Jun 23 '15 at 13:36
  • $\begingroup$ Will Savin do you know where I can find an article on this "first field"? $\endgroup$ – Halbort Jun 23 '15 at 17:15
  • $\begingroup$ @Halbort, I don't think the name is used, but this appears in On Numbers and Games, as well as Siegel's Combinatorial Game Theory $\endgroup$ – Mark S. Jun 23 '15 at 19:06
  • $\begingroup$ @Halbort You could look at this article also openaccess.leidenuniv.nl/bitstream/handle/1887/2125/346_027.pdf $\endgroup$ – Will Sawin Jun 23 '15 at 19:11
  • $\begingroup$ @MarkS. Yes, Conway only recently came up with a different name. $\endgroup$ – Will Sawin Jun 23 '15 at 19:17
10
$\begingroup$

The sum of two games means a turn consists of playing in either game. Then by the mirror strategy, for any impartial game $G$, $G+G=0$, a second player win. That means that under this sum, equivalence classes of impartial games form an abelian group of exponent $2$, or an $F_2$-vector space. XOR describes the additions with respect to any basis, not just the standard one.

You can change the connection with XOR by changing the sum operation. If in a collection of games, you must play in at least one, but up to $k$ games, then the Grundy values of the components matter, but the second-player wins correspond to collections whose sums without carries have all digits divisible by $k+1$. This was observed by Moore where the games are Nim piles. Of course, this is related to your other question. There are other generalizations possible, where you are allowed to play in other collections of multiple games, and you don't simply XOR the Grundy-values of the components.

$\endgroup$
  • 3
    $\begingroup$ Thank you very much for your answer. The only reason this is not the accepted answer is because I accepted before it was posted. I think that the line : "XOR describes the additions with respect to any basis, not just the standard one." is very helpful to anyone (I hope/think I am not the only one) who was confused as to the origin of the nimsum. $\endgroup$ – Halbort Jun 23 '15 at 13:50
3
$\begingroup$

Here's my understanding of the Nimbers and of your question. Actually, you'll see that I do need to beg the question somewhere, but since you do know a proof of the bitxor rule, perhaps that's allowed --- then my answer can be understood as a proof that your proof implies your proof is natural. (Said that way it sounds like an application of Lob's theorem, or perhaps a converse....)

By "Nimbers" I mean Nim games with Conway's game addition (put two games next two each other; on your turn, you choose one of the two boards to play on) modulo the second-player-win Games. By definition, a "game" is one where you lose when you cannot make a turn. The Nimbers are the classes of single-column Nim games.

The zeroth observation is that addition (henceforth "$+$") is commutative, and that for any game $g$, the game $-g$ in which the roles are reversed is its inverse.

The first observation, then, is that impartial games, and multi-column Nim games in particular, are 2-torsion: for any Nim game $g$, we have $g + g = 0$. Thus the group generated by the Nimbers is a vector space over $\mathbb F_2$.

The next ingredient I don't really have an a priori reason for, which is that the sum of any two Nimbers is a Nimber. Actually, proving this is probably just about the same as finding the bitxor formula, so perhaps my whole story is question-begging. But let's assume that this second ingredient is just an "observation".

The third observation is the following. Let $G_k$ denote the group generated by the Nimbers $1,\dots,k$. If you allow the second observation, then it is not hard to see that if $n \in G_k$, then for every $m < n$, $m\in G_k$. Indeed, if $n\in G_k$, then I can write $n = \sum a_i$ for some sum of Nimbers with $a_i \leq k$. Let's play the game $n + \sum a_i$, which is a second-player win by assumption. Being magnanimous, I'll go first. On my turn I turn $n$ into $m$. Now you definitely have a move the return the sum to $0$. It definitely doesn't involve the pile I touched, so it must involve dropping one of the $a_i$s to an $a_i' < a_i$. But $a_i$ was one of our generators in $1,\dots,k$, and so $a_i'$ is also one of those generators.

Now we can put the observations together to describe the structure of the Nimbers. We have $G_0 = \{0\}$ and $G_1 = \{0,1\}$ is the group of order $2$. By induction, the set of Nimbers $G = \{0,1,\dots,2^k-1\}$ is closed under Nimber addition. Consider $G_{2^k}$. It is an $\mathbb F_2$-vector space generated by $G$, which has $2^k$ elements, and by one more element. Thus $|G_{2^k}| = 2^{k+1}$. Thus $G_{2^k} = \{0,\dots,2^{k+1}-1\}$. The induction can then continue.

So the Nimbers are naturally organized as an $\mathbb N$-filtered $\mathbb F_2$-vector space: $$\{0\} \subset \{0,1\} \subset \{0,1,2,3\} \subset \{0,1,2,3,4,5,6,7\} \subset \dots \subset \{0,\dots,2^{k-1}\} \subset \dots.$$ This doesn't completely pin down the addition, but it makes bitxor seem very likely. For example, it implies that if $m,n \in \{2^{k-1},\dots,2^k-1\}$, so that they have the same leading digit mod $2$, then their sum $m+n < 2^{k-1}$, and on the other hand if $m < 2^{k-1}$ and $n \in \{2^{k-1},\dots,2^k-1\}$, then $m+n \in \{2^{k-1},\dots,2^k-1\}$. This gives the bitxor rule in the leading digit.

Of course, this analysis still allows lots of group structures on $\{0,\dots,2^k-1\}$. The rule is only that the structure has to extend the one on $\{0,\dots,2^{k-1}-1\}$. You can write down ad hoc group structures by twisting the given one by any permutation of $\{2^{k-1},\dots,2^k-1\}$. To completely pin down the bitxor group law requires playing a bit more with the third observation, I think. Let's see if we can do it. We know that the bitxor rule applies to Nimbers $N < 2^k$, by induction. We also know that $2^k + 2^k = 0$, so it applies to $N \leq 2^k$. To prove the claim, it suffices to prove that the Nimber of height $2^k+2^j$ for $j<k$ is equal to the Nim addition $2^k + 2^j$. Everything else will follow from linear algebra. But now all I need to do is to tell you a second-player-win strategy for the three-column Nim game with heights $2^j$, $2^k$, and $2^k+2^j$. Well, let's suppose you play on column $2^j$. Then I have such a strategy by induction in $j$ (and linear algebra). Suppose you play on column $2^k$. Then you make it into something in $\{0,\dots,2^k-1\}$, and adding $2^j$ keeps me in that group, so I just need to drop the column of height $2^k+2^j$ to match. Finally, suppose you play on column $2^k+2^j$. If you leave it above $2^k$, I'll play on column $2^j$ to match, and use induction in $j$ to know that that works. If you take it below height $2^k$, I'll drop the $2^k$-column to make the sum come out, using bitxor in the group $\{0,\dots,2^k-1\}$.

Perhaps this is the proof you already know. It certainly is a follow-your-nose proof.

$\endgroup$
  • $\begingroup$ Huh. I started writing this last night, but only posted it this morning, and only then saw that Will Sawin has given essentially the same argument. $\endgroup$ – Theo Johnson-Freyd Jun 23 '15 at 15:30
  • $\begingroup$ Thank you very much for your comment. It is very detailed and it helped me further understand the arguments of Will Sawin and Douglas Zare. I have selected it as the "answer" for further reference to others. It is very extensive and so will give them a full understanding. $\endgroup$ – Halbort Jun 23 '15 at 15:33
  • $\begingroup$ Do you mean that $g+g=0$. $\endgroup$ – Halbort Jun 23 '15 at 16:43
  • $\begingroup$ @Halbort: Yes; I will correct it. $\endgroup$ – Theo Johnson-Freyd Jun 23 '15 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.