{"id":376,"date":"2007-04-09T08:05:00","date_gmt":"2007-04-09T08:05:00","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/04\/09\/sign-expanded-surreal-numbers\/"},"modified":"2007-04-09T08:05:00","modified_gmt":"2007-04-09T08:05:00","slug":"sign-expanded-surreal-numbers","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/04\/09\/sign-expanded-surreal-numbers\/","title":{"rendered":"Sign-Expanded Surreal Numbers"},"content":{"rendered":"

In addition to the classic {L|R} version of the surreal numbers, you can also describe surreals using something called a sign expansion<\/em>, 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.<\/p>\n

<\/p>\n

It’s based on ordinals (which we also called birthdays<\/em>) Remember, ordinals are the numbered generations<\/em> 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.<\/p>\n

For each ordinal x<\/em>, we can define three sets of numbers:<\/p>\n

    \n
  1. The Made numbers, Mx<\/sub>: the numbers that have been created by
    \nordinal x<\/em>.<\/li>\n
  2. The New numbers, Nx<\/sub>: the numbers that were created<\/em> in ordinal
    \nx<\/em>.<\/li>\n
  3. The Old numbers, Ox<\/sub>: the numbers that were created before<\/em>
    \nx<\/em>, in earlier ordinals.<\/li>\n<\/ol>\n

    Now, pick a number a, created in ordinal X. For each ordinal i starting at ordinal 0, pick the number Ai<\/sub> which is the closest<\/em> value to a<\/em> which is
    \npart of Ni<\/sub>. If Ai<\/sub><a, then the i<\/em>th position of
    \nthe sign-expansion form of a is “+”; if Ai<\/sub>>a, then the i<\/em>th position of the sign-expansion form of a is “-“.<\/p>\n

    Let’s take a simple example: 3 1\/2.<\/p>\n

      \n
    1. Ordinal 0 contains only the number 0, so A0<\/sub>=0. 0<3 1\/2, so
      \nthe 0th position is “+”.<\/li>\n
    2. In Ordinal 1, the closest new value to 3 1\/2 is +1, so A1<\/sub>=1. 1<3 1\/2, so
      \nthe 1th position is “+”; so the sign expansion so far is “++”.<\/p>\n
    3. In ordinal 2, the closest new number is 2, so A2<\/sub>=2, so the sign
      \nexpansion so far is “+++”.<\/li>\n
    4. In ordinal 3, the closest new number is 3, so A3<\/sub>=3, so the sign
      \nexpansion so far is “++++”.<\/li>\n
    5. In ordinal 4, the closest new number is 4, so A4<\/sub>=4; 4>3 1\/2,
      \nso the expansion is “++++-“.<\/li>\n<\/ol>\n

      So in sign expansion form, 3 1\/2 is “++++-“.<\/p>\n

      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 “+++++++++++++++++”.<\/p>\n

      When there’s a fractional part, it gets interesting. In the surreal numbers, the first integer larger
      \nthan any fraction is always created before that fraction. So 1 is created before 1\/2; 4 is created before 17\/5, and so on. <\/p>\n

      So in sign-expansion form, you always overshoot<\/em> 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.<\/p>\n

      Likewise, for the negatives, you always start with a sequence of “-“s for the integer part, followed by “-+”, followed by the fractional part.<\/p>\n

      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!)<\/p>\n

      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<\/em> 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.<\/p>\n

      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<\/em> 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<\/em> 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<\/em> 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<\/em> there were an extra “+” on the end, so we add a 1. So “+–” expands to “0+(.012<\/sub>” = 0+1\/4 = 1\/4.<\/p>\n

      (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.<\/em><\/p>\n

      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
      \nparts of the number. The part before<\/em> the separator is the integer part in ordinal form. If you take the part after<\/em> 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
      \nnegative numbers.<\/p>\n

      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.\n<\/p>\n

      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:<\/p>\n

        \n
      1. We’re looking at the range (2,3); so we add a “-“, because 2 3\/8 is smaller than 2 1\/2.<\/li>\n
      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.<\/li>\n
      3. 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,
        \nso we’re done.<\/li>\n<\/ol>\n

        So 2 3\/8 would be written “+++–+”.<\/p>\n

        This alternate form of the surreals has a pretty neat property. If you sort
        \nsign-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.<\/p>\n","protected":false},"excerpt":{"rendered":"

        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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[62],"tags":[],"class_list":["post-376","post","type-post","status-publish","format-standard","hentry","category-surreal-numbers"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-64","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/376","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=376"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/376\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=376"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=376"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=376"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}