Last Monday, John Conway visited us. (He has two mathematical children and one grandchild on the permanent staff in the department.) He gave a seminar to what may have been the largest audience ever for a Pure Mathematics seminar.
He had announced a talk on “The simplest approach to the Monster”, but in the event he decided to talk about something else. This was not entirely a surprise. One of my very few Conway stories concerns a big conference where I happened to be chairing the plenary session at which he spoke. On that occasion he hadn’t given a title. On the stage was an old-fashioned easel with a blackboard on it. I announced him, and said that I assumed he would tell us what he was going to speak about. Instead, he walked onto the stage, picked up the blackboard, and reversed it. There were written five titles. He said, “I will count down, and when I reach zero, you should all shout as loudly as you can the number of the talk you want to hear. The chairman will decide which number is being shouted loudest.” Of course, in the pandemonium, it was completely impossible to make this decision; so I simply chose the talk I wanted to hear.
Monday’s talk was about the remarkable “Nim-field”, or On2 as it is called in his book On Numbers and Games. But he introduced it in a different way from that in the book, via another of his remarkable discoveries, lexicodes.
We are going to construct a code (a set of words) over a fixed alphabet. In coding theory, words have fixed finite length; but we are going to continue the construction infinitely, so in order to allow the words to grow, we imagine each word as beginning with an infinite sequence of zeros, but ending at a definite point. As with the usual decimal representation of integers, they are right-aligned.
Lexicodes can be defined over any alphabet, as long as the alphabet is ordered, with least element called 0 (so that we have a well-defined lexicographic order on the words). Binary and ternary lexicodes, for example, have remarkable properties and include many famous families of codes. But on this occasion, the alphabet is taken to be the set of natural numbers, with the usual ordering.
The code is to have a fixed minimum distance d in the Hamming metric; that is, any two codewords are to differ in at least d coordinates. We build the code by taking at each stage the lexicographically least word subject to haing distance at least d from the previously-constructed words.
Thus, the initial word is all-0; the next ends with d 1s; then d 2s; and so on through the alphabet. To see what happens next, consider the case d=3. The next word must have a non-zero entry outside the last three positions, necessarily a 1 in position 3 (counting the last position as 0). Now no two of the following entries can be equal; so the word is …1012. (Here and later, dots represent initial zeros.) Next comes …1103, then …1230, and …1321. And so on.
The theorem asserts:
There are definitions of addition and multiplication on the natural numbers which make them into a field, so that the Lexicode becomes linear (that is, a vector space) over this field.
We can see how the process begins. First, 0 must be the zero element of the field, since there is only one constant word in the Lexicode, the all-0. Now consider …0111+…1012. This word must be …11xy for some x and y. It lies at distance at most 2 from …1103; so it must be equal to this word, that is, x=0 and y=3. Thus, we must have 1+1=0 (that is, the characteristic is 2), and 1+2=3.
Multiplication is a little trickier since we have to choose the multiplicative identity arbitrarily (this is not determined by the fact that the code is linear, as is easily seen). So let us suppose that 1 is the multiplicative identity (any other choice would be perverse!)
The first codeword after those with 1 in position 3 is …2023; this must be 2 times …1012. Hence 2×2=3. Continuing, we find that {0,1,2,3} is a subfield isomorphic to GF(4). Indeed, the entire field (whose elements are all the natural numbers) is the quadratic closure of GF(2), the field obtained by adjoining the roots of all quadratic equations.
The multiplication was invented by Conway. (He told us how, when he discovered that 4×4=6, this seemed so extraordinary to him that he rolled on the floor laughing.) But the addition is Nim sum, due to Sprague and Grundy in the discussion of Nim-type games. The simplest such game is Nim, a game played with heaps of matches. Two players take turns removing any number of matches from a single heap; the player who takes the last match wins. A winning configuration in this game is a collection of piles such that the Nim sum of their sizes is zero. If you can leave such a configuration to your opponent, then his move must destroy this property, and you can restore it on your next move. For example, if you leave piles with sizes 1,2,3, then whatever your opponent does, you can produce two equal piles on your next move; then you simply “shadow” your opponent’s moves.
The Nim sum of two numbers is obtained by writing them in base 2 (as distinct powers of 2), adding modulo 2 (without carrying), and re-converting the result to an integer.
In On Numbers and Games, Conway gives a direct description of the field operations, without using the lexicode. When constructing them, some operations are forced (for example, if we know that 1+2=3 and that 1+1=0, then we can deduce that 1+3=1+(1+2)=(1+1)+2=2. Any sum or product which is not forced should take the smallest value which does not lead to a contradiction.
For example, let us consider 4×4. This cannot be 0, by the field axioms. It cannot be 1, 2, or 3, since these already have square roots (1, 3, 2 respectively), and in a field of characteristic 2 an element has at most one square root. It cannot be 4 by the cancellation law. It cannot be 5=4+1, since we already have two roots of the quadratic x2=x+1, namely 2 and 3. However, 6 is not excluded, and thus 6 is the answer.
Fascinating things happen when this construction is continued into the transfinite, though this is a little harder to link to lexicodes. You can read about this in the book.
Actually the construction of the Nim field and its transfinite extension is really just a byway in a single chapter of the book. The main aim of its zero-th part “On Numbers” is the construction of the surreal numbers (the name is due to Donald Knuth, in his mathematical novel on the subject), which include and extend both the real numbers (in Dedekind’s construction) and the ordinal numbers (in Cantor’s). The Nim field is a characteristic 2 analogue of the surreal numbers.
I have actually used Conway’s Nim field myself, in a paper with Sam Tarzi on limits of cubes. There are many approaches to graph limits, but I think what we did here has some novelty. Thinking of finite cubes as metric spaces, we embed Qn into Q2n by doubling each coordinate, and then halving the metric on the latter. The completion of the limit object turns out to be the space of Lebesgue measureable sets modulo null sets, and also has a connection with the Nim field. But I am getting old, and can’t remember (without looking it up) exactly what the connection was.
There is a bit more to be said about lexicodes. We have to fix a minimum distance d to define a lexicode. If we increase d by one, the effect is to add one new coordinate on the right, whose value is determined by the preceding coordinates. Thus there is a limiting lexicode, whose words are infinite in both directions, but typically non-zero to the right. What does this look like?
A simpler observation is that this extension process shows that we do not get different fields from the different lexicodes. As with any beautiful construction in mathematics, the Nim field has a robustness about it showing that the same thing can be obtained in many different ways.
Peter Cameron's Blog 
Pingback: Numbers from Games |