In addition to the classic {L|R} version of the surreal numbers, you can also describe surreals using something called a sign expansion, where they’re written as a sequence of “+”s and “-“s – a sort of binary representation of surreal numbers. It’s fully equivalent to the {L|R} construction, but built in a different way. This is a really cool, if somewhat difficult to grasp, construction.
It’s based on ordinals (which we also called birthdays) Remember, ordinals are the numbered generations of surreal numbers. Ordinal 0 contains the value 0; ordinal one adds the values +1 and -1; ordinal two adds +1/2, -1/2, +2, and -2. And so on.
For each ordinal x, we can define three sets of numbers:
- The Made numbers, Mx: the numbers that have been created by
ordinal x. - The New numbers, Nx: the numbers that were created in ordinal
x. - The Old numbers, Ox: the numbers that were created before
x, in earlier ordinals.
Now, pick a number a, created in ordinal X. For each ordinal i starting at ordinal 0, pick the number Ai which is the closest value to a which is
part of Ni. If Ai<a, then the ith position of
the sign-expansion form of a is “+”; if Ai>a, then the ith position of the sign-expansion form of a is “-“.
Let’s take a simple example: 3 1/2.
- Ordinal 0 contains only the number 0, so A0=0. 0<3 1/2, so
the 0th position is “+”. - In Ordinal 1, the closest new value to 3 1/2 is +1, so A1=1. 1<3 1/2, so
the 1th position is “+”; so the sign expansion so far is “++”. - In ordinal 2, the closest new number is 2, so A2=2, so the sign
expansion so far is “+++”. - In ordinal 3, the closest new number is 3, so A3=3, so the sign
expansion so far is “++++”. - In ordinal 4, the closest new number is 4, so A4=4; 4>3 1/2,
so the expansion is “++++-“.
So in sign expansion form, 3 1/2 is “++++-“.
If you followed that, it should be pretty clear that every positive integer N is written as a series of N “+”s in this form. So 5 is “+++++”; six is “++++++”; 18 is “+++++++++++++++++”.
When there’s a fractional part, it gets interesting. In the surreal numbers, the first integer larger
than any fraction is always created before that fraction. So 1 is created before 1/2; 4 is created before 17/5, and so on.
So in sign-expansion form, you always overshoot a fraction, and then come back. This leads to an important observation: since every positive number is just a sequence of “+”s, and you always overshoot fractions, then the first “+-” pair in the number is, basically, the decimal point – it’s the divider between the integral and fractional part of a number.
Likewise, for the negatives, you always start with a sequence of “-“s for the integer part, followed by “-+”, followed by the fractional part.
Remember that the way we end up creating things with ordinals, we always introduce a new number which is exactly half-way between previously created ordinals. So given the numbers 3 and 4, the first new number between them will be 3 1/2; and then the generation after that, 3 1/4 and 3 3/4s will get added, and so on. So the signs in the fractional part are describing how to find the value of the fractional part between the two integers on either side of it in terms of…. a binary search! (And you thought that the binary search post the other day was unrelated!)
The fractional part F of a number N is a sequence of “+”s and “-“s. At each sign, we have a range from a lower bound l to an upper bound u. At first, l is the integer part of N, and u is l+1. Each time we get another sign, we split the range between L and R in half. If the sign is “+”, then we know that N is in the upper half of the (l,r), so we increase l to (l+r)/2. If the sign is “-“, then we know N is in the upper half, so we reduce r to (l+r)/2.
That tells us how to write the a fraction in surreal sign expanded form. But there’s one more trick to understanding how to read the fractional part. The problem is, if the sign sequence is finite, and the number N belongs to ordinal i, then the sign sequence tells us what to do up to ordinal (i-1). So at the end of the sign sequence, we’re always missing one step: the step from ordinal (i-1) to ordinal i. It’s easy to fix: the nature of this procedure works out so that we’re always a bit too low – since we started by overshooting, and dropping back, we always wind up just below N at the last sign in the fractional part. So for computing the value of a surreal number in sign expanded form, we treat it as if it ended with an extra “+” at the end, and that gives us precisely on the value of the fractional part. But it’s important to realize that that trailing plus is not part of the notation of the number: it’s only added as part of a procedure for calculating the value of a sign-expanded number. So, for example, 1/4 is written “+–“. If we wanted to read that, we start by recognizing “+-” as the separator between integer and fractional parts – so the integer part is 0. For the the fractional part, we write it as a binary decimal. The first digit of the binary part is 0 (because “-” becomes 0), and then we treat it as if there were an extra “+” on the end, so we add a 1. So “+–” expands to “0+(.012” = 0+1/4 = 1/4.
(Note: the previous paragraph was originally written in a way that made it sound like you actually add the trailing “+” to the sign-expanded notation of a number – so that, for example, 1/4 would be written “+–+” instead of “+–“. Thanks to Blake Stacey for pointing that out.
Based on all of this, you should be able to see that there’s a trick to reading the sign expansion, to see what number it is. For positive numbers, they always start off with a series of “+”s followed by “+-“; for negatives, they always start off with a series of “-“s, followed by a “+”. So, take the first sign-switch in a sign expansion, and treat it the separator between the integer and fractional
parts of the number. The part before the separator is the integer part in ordinal form. If you take the part after the separator, and add a “1” to the end if it’s finite, then it’s the binary decimal for the fractional part; if it’s a positive number, then “+”s in the sign expansion count as 1s and “-“s count as 0s; and the opposite for
negative numbers.
So let’s look at our expansion of 3 1/2: “++++-“. That’s “+++(+-)”. We add a one (+, since the number is positive) to the end: “+++(+-)+”. So the part before the separator is “+++”: unary 3. The part after the separator is binary 0.1 = 1/2. So it’s the number 3 1/2.
Let’s try forming the sign expansion of 2 3/8. It starts with “++” for the integer part; then it’s got “+-” as the sign divider. Then:
- We’re looking at the range (2,3); so we add a “-“, because 2 3/8 is smaller than 2 1/2.
- Then, we’re looking at the range (2, 2 1/2). We add a “+”, because 2 3/8 is larger than 2 1/4.
- We’re looking at the rnage (2 1/4, 2 1/2). The number in that range from the next ordinal is 2 3/8,
so we’re done.
So 2 3/8 would be written “+++–+”.
This alternate form of the surreals has a pretty neat property. If you sort
sign-expanded surreal numbers in lexicographic order (that is, sort them as strings, where “-“<“+”), it’s exactly the same as sorting them by numeric value. The strings are direct correspondences for the lexicographic position of the numbers in the total order of surreals.
Natural, if somewhat silly, question: what’s the expected running time to search a transfinite binary tree? 😀
I’m confused about the “one more trick to understanding the fractional part”. In Conway’s book, he gives the same rule for translating sign-expansions to binary numbers that the first half of this post does. Conway explains this rule (due originally to Elwyn Berlekamp) in the following way:
It’s that “adding a final 1” which has me a little perplexed. Conway gives the example ++++-+–, which when bracketed becomes +++(+-)+– = 3.1001 (the final 1 added because the expansion is finite). So, ++++-+– = 3 9/16.
He also says that +-+ is the expansion of 3/4 (up to 1, down to 1/2, up to 3/4), but by MarkCC’s rule, 3/4 would be “+-++”. Let’s see: (+-)+ = 0.1 with an extra 1 = 1/2 + 1/4 = 3/4. Yeah, I think the rule should be to add an extra 1 to the binary expansion, not to add an extra + to the sign-expansion.
Blake:
Thanks for the catch – it’s imprecise writing on my part. I was trying to explain how the representation works at the same time as explaining how to read it. For reading the fractional part, you treat it as if you had appended a trailing “+”; the trailing “+” is not part of the actual number representation. I’ll try to figure out how to fix the post’s text to make that clear.
Glad I could help!
(you forgot a couple of closing tags!)
This reminds me suspiciously of Hackenbush, right? So now we’ll have to deal with infinite sequences, to get rational numbers not of the form m/2^n and at least real numbers.
Whats the sign expansion of 1/3 then? I tried, but can not work it out.
Andrew:
The sign expansion of 1/3 is going to be infinitely long. It will start with the separator mark “+-“, and then it will be followed by the binary decimal form of 1/3… If my brain is working right, then, it will be an infinite sequence “+-(+-)ω”.
.mau.:
Right!
Conway and Richard Guy give the details in Chapter 10 of The Book of Numbers. To summarize, a sign-expansion of a surreal number is exactly equivalent to a Hackenbush chain.
Hackenbush is a “take-away” game played with sticks, colored blue (or black) and red, which are connected at nodes. Each Hackenbush configuration must have the property that you can get from any node to the “ground” by following a chain of edges. The game has two players, Left and Right; Left can delete any blue/black edge while Right can remove any red edge. The players alternate, removing one edge each move, and each time any edges not connected to the ground must be removed. The goal is to get the other guy into a position where they cannot move.
In the “empty position”, there are no red or black edges at all, a situation which we write as
{ | } = 0.
In this notation, the set to the left of the bar indicates Left’s options, while the set to the right indicates the choices Right has available. A general Hackenbush position can be written,
{a, b, c, … | d, e, f, …} = g.
If the picture has just one black edge and no red edges, Left has exactly one legal move, and Right has none at all. This is {0 | } = 1. Similarly, with one red edge connected to the ground and no black edges, we write the board configuration as { | 0} = -1. Reversing red and black edges exchanges the roles of the two players, and this interchange is called taking the negative of the Hackenbush game.
How do we compare two Hackenbush games? Suppose that we have two positions, g and h. We combine them into a single picture — just put the two stick arrangements side-by-side on the same ground line — negating h to –h. Then we ask, who wins the combined game? If Left can win, no matter who is first to play, we say that g > h. Likewise, if Right can win no matter who moves first, g < h. In the event that the second player to move can always win, the two games are equal: g = h.
If you imagine a tower of red and black sticks, rising beanstalk-like up from the ground, you’ve got a Hackenbush chain. Replace black edges with + signs and red sticks with – signs, and you’ve got yourself a sign-expansion! To turn the chain into a binary number, treat the first pair of opposite-color edges (black then red, for positive numbers) as the “binary point”. After that point, read the black edges as 1 and the red edges as 0, appending an extra bit 1 if your Hackenbush chain has finite length.
For those of you reading Blake Stacey’s second to last paragraph in the above post and wondering why he left out a case (the game is such that the first player can always win), it’s because then you’re completely out of numbers entirely and into the more general category of games. If the first player can always win, then g and h are fuzzy – they’re incomparable. g
interesting!
Wondering what applications/reasons to use this approach in a Computer Science approach. I guess creating languages that use this is direct enough; but practicality is what I’m reaching for…
I think “If the sign is “+”, then we know that N is in the upper half of the (l,r), so we increase l to (l+r)/2. If the sign is “-“, then we know N is in the upper half, so we reduce r to (l+r)/2.”
should read, “If the sign is “+”, then we know that N is in the upper half of the (l,r), so we increase l to (l+r)/2. If the sign is “-“, then we know N is in the lower half, so we reduce r to (l+r)/2.”
Xanthir, FCD:
Thanks for plugging the hole!
For terminology’s sake, somebody should note that the games which are not numbers are called pseudo-numbers in Knuth’s book. Also, the “category of games” is dangerous talk, since it wasn’t until 1977 (a year after ONAG) that Andre Joyal specified what a morphism between two games must be, thereby obtaining a category which gives a combinatorial calculus of strategies.
It looks as if there are some interesting issues at work here which I do not have the expertise to understand or comment meaningfully upon. Quoting Robin Houston (2004),
Oh, and because I love references like I love few things in life, here’s an introduction to combinatorial game theory by Schleicher and Stoll available on the arXiv (via John Baez).
One thing that confuses me (not relevant to the important parts of the post). In the sets Mx, Nx, and Ox am I right to interpret “The Made numbers, Mx: the numbers that have been created by ordinal x.” to mean the numbers that will be created by ordinal x. Or to be more clear, the numbers for which ordinal X and only ordinal X are necessary. ie M1 = {-2, -1/2, 1/2, 2}. If not I don’t understand what Mx is.
Jon L: My impression was that Mx = O(x+1) = the union of Nx and Ox. So M1 = {-1, 0, 1} = O2.
It seems to me that this is very close to Peano-style construction of the naturals. If we do it in Haskell:
dataAnything deeper lying here?
Huh? That showed up fine in the preview… I’ll try without formatting.
data Nat = Zero | Succ Nat — naturals
data Sur = Zero | Succ Sur | Prec Sur — surreals