Exploring Surreal Numbers: A Construction Based on Binary Expansion of Integers

[jambaugh]

I just bought a copy of Conway's book "On Numbers and Games" which I had read many years ago with great delight. It reminded me of a little construction I did on my own which I thought I'd share.

In Conway's book he defines surreal numbers as (equivalence classes) of ordered pairs of numbers recursively said pairs generalizing Dedekind cuts and further generalizing to "games".

I found another construction based on the binary expansion of integers.

Start with:
I. $$0=\{\}$$
Then define the sets you construct by inclusion and union starting with 0 by its binary expansion:
II. $$\{ n_k\} = \sum_k 2^{n_k}$$

Thus for example:
$$9=8+1=2^3+2^0=\{3,0\}=\{(2^1+2^0),0\}=\{\{1,0\},0\}=\{\{\{0\},0\},0\}$$

Every non-negative integer is a finite set and every finite set is a non-negative integer.

$$S \equiv \sum_{n\in S} 2^n$$

Addition and multiplication are defined algorithmically as usual binary addition and multiplication. I won't go through the trouble of recasting these algorithms in set notational form as it is an easy exercise.

Now consider then the set of all natural numbers:
$$\mathbb{N}=\{0,1,2,\cdots\}$$
Observe that following the algorithm we have:
$$1 + \mathbb{N} = 0$$
(assuming we can carry out the algorithm on a transfinite infinite bit computer we can show that each "bit" is set to zero at some finite step.)

We thus define the set of natural numbers as the number -1. Further using one's complement we can define the entirety of the integers as subsets of the set of natural numbers. Example:

$$-5 = \mathbb{N}\oplus 5 + 1 = \{0,1,3,4,\cdots\}=\cdots111011_2$$

Ok, nothing especially exciting here. We are simply doing arithmetic on an infinite computer. However note that we may add and multiply any subsets of -1={0,1,2,...} not all of which represent natural numbers. The question then is which do behave like regular numbers?
(Henceforth I will use binary notation for the most part or at worst one level of brackets.)

Consider for example the "set of even natural numbers":
$$E=\{\cdots 6,4,2,0\}=...10101010101_2$$
$$E\times 3 = ...1010101_2\times 11_2 = \cdots 11111_2=-1$$
Thence we may take:
$$E = -1/3$$
(And we can take the one's complement to define +1/3!)

Now that is interesting! With some work you can find that all rationals with reduced odd denominators may be so expressed.

Finally note that if we go on to include sets containing negative integers
e.g. $$3.625=11.101_2 = \{1,0,-1,-3\}$$
then we may define in addition fixed point binary numbers and thence include even denominator rationals. In order for the addition and multiplication algorithms to be well defined we must restrict ourselves to finite fixed point binary expansions. In short we stick to subsets of the set of integers which have a least element.

So what other "numbers" lie in the power set of -1={...4,3,2,1,0}?

Since we can express odd fractions, we might for example consider if the limit
$$e = \lim_{n\to\infty,n odd} (1+1/n)^n$$
is meaningful as a limit in terms of the algorithmic definition of addition and multiplication. I.e. do the binary values below a given fixed index eventually become fixed themselves?

Lots of possible fun here. Enjoy!

Regards,
James Baugh

P.S. I seem to recall finding square roots of some integers but can't recover the construction...possibly I am only remembering trying to find such and forgetting my failure. It has been over a decade since I played with this idea.
R. J.B.

 

[Moo Of Doom]

I found this very interesting. Thanks for the post. I'll be fiddling around with this idea for some time. :)

 

[JohnDuck]

Now consider then the set of all natural numbers:
$$\mathbb{N}=\{0,1,2,\cdots\}$$
Observe that following the algorithm we have:
$$1 + \mathbb{N} = 0$$
(assuming we can carry out the algorithm on a transfinite infinite bit computer we can show that each "bit" is set to zero at some finite step.)

Could you demonstrate this in detail? I'm a little confused.

 

[Hurkyl]

These aren't surreal numbers; they're 2-adic numbers. (more generally, you can study p-adic numbers for any prime p) They have an absolute value function defined by:

$$| 2^a b |_2 := 2^{-a}$$

for every odd 2-adic integer b. In particular, the further left a binary digit is, the less significant it is. (Which is the opposite of what you see in the reals, where digits on the right are less significant)

This absolute value let's you reproduce ordinary analysis; you can study limits, derivatives, power series, etc.


For example, you can use Newton's method to compute square roots. An odd number has a square root if and only if its three right-most digits are 001. If you let N be the number whose square root you want, then applying Newton's method to find a root of x^2 - N:

$$x_0 := 1$$
$$x_{k+1} := x_k - \frac{x_k^2 - N}{2 x_k} = \frac{x^k^2 + N}{2 x_k}$$

this sequence will converge (quadratically) to a square root of N.

2-adic analysis interacts well with modular arithmetic. To demonstrate, let me compute a square root of 17.

We start with
$$x_0 = 1$$
Note that $(x_0)^2 \equiv 17 \mod 8$.

Applying the theory behind Newton's method, or doing the analysis directly, we find that the next step should have at least 4 (=2*3 - 2) bits of accuracy, so we work modulo 16¹:

$$x_1 := \frac{(1 + 17)}{2} \equiv 9 \pmod{16}$$

Lo and behold: $9^2 = 81 \equiv 17 \pmod{16}$.

The next iteration should have at least 6 (=2 * 4 - 2) bits of accuracy, and we should work modulo 64 (=2^6):

$$x_2 := \frac{(81 + 17)}{18} = \frac{49}{9} \equiv 49 * 57 \equiv 41 \pmod{64}$$

Lo and behold: $41^2 \equiv 17 \pmod{64}$


The convergence is more vivid in binary notation. * represents digits whose value are insignificant.

x₀ = ...*****001
x₁ = ...****1001
x₂ = ...**101001
...


In many ways, 2-adics are easier to use than reals. For example, in the reals, if you approximate things and do a lot of arithmetic, those errors can build up and ruin your answer. But 2-adically, errors cannot accumulate, because:

$$|a + b| \leq \max\{|a|, |b|\}.$$


1: well, technically we can't divide by two modulo 16, but with a little bit of work you can make this more rigorous

 

[jambaugh]

Could you demonstrate this in detail? I'm a little confused.

Sure:
$$\mathbb{N} = \{ \ldots,5,4,3,2,1,0\}= \cdots 111111_2\}$$

Take it in stages:
$$1+1 = 10$$
$$11+1=100$$
$$111+1=1000$$
$$1111+1=10000$$
etc

So you see if all the bits are set to 1 below the n-th then 1 plus that "number" will have all the bits below the n-th set to zero via carry. Thus if all the bits are set then adding one will clear all bits eventually and you get the empty set = 0. Hence this "number" acts like -1.

Simply see how -1 is represented on N-bit machines. Then generalize where N becomes infinity.

 

[jambaugh]

These aren't surreal numbers; they're 2-adic numbers. ...

Right, they are not the surreal numbers but...No they are not 2-adics. Note that sticking to subsets of $$-1=\mathbb{n}$$ you get exactly the opposite of 2-adics. I.e. the conjunction of all the odd p, p-adics.

You get 2-adics only if you restrict to finite sets of the whole set of integers.

But I'm more interested in the other infinite subsets of the naturals (which I define to include zero so I don't have to you the bulkier term "non-negative integers")

Example: Can you identify a real number corresponding to the bit set:
$$...10001001011_2$$?

Can you find some bit pattern which will square to say 1/3= ...10101011?

Is there some interpretation other than "sets" we can give to those subsets which do not correspond to numbers?

What is the reciprocal algorithm? i.e. find the bit pattern which will algorithmically multiply a given bit pattern to yield 2^n for some n.

As I said, Lots of fun to be had.

Regards,
James

 

[Hurkyl]

Right, they are not the surreal numbers but...No they are not 2-adics. Note that sticking to subsets of $$-1=\mathbb{n}$$ you get exactly the opposite of 2-adics. I.e. the conjunction of all the odd p, p-adics.

If you stick to finite subsets of N, your arithmetic simply gives you N. The correspondence was given in your opening post; the finite subset S of N represents the nonnegative integer

$$\sum_{s \in S} 2^s$$


The correspondence between the arithmetic you define and the 2-adic integers is given by the same sum: any (possibly infinite) subset S of N represents the 2-adic integer

$$\sum_{s \in S} 2^s$$

(where convergence is in the 2-adic metric)


And when you generalize to take subsets of Z that contain finitely many negative numbers, you get precisely the 2-adic rationals, with the correspondence again given by the same sum

$$\sum_{s \in S} 2^s$$

Can you find some bit pattern which will square to say 1/3= ...10101011?

No: the square of any of your numbers ends in either 00 or 001, in the binary¹ represntation.

What is the reciprocal algorithm? i.e. find the bit pattern which will algorithmically multiply a given bit pattern to yield 2^n for some n.

The following sequence converges to the reciprocal of the odd number N:

x₀ = 1
x_k+1 = x_k * (2 - N * x_k)

x_k will be correct in the rightmost 2^k bits.

(This is Newton's method with f(x) = N - 1/x)

e.g. to compute 1/3, we go through the sequence:

1
-1 = 1 * (2 - 3 * 1)
-5 = -1 * (2 + 3 * 1)
-85 = -5 * (2 + 3 * 5)
-21845 = -85 * (2 + 3 * 85)
...

The right 16 bits of this number are guaranteed to be correct. The binary represntation of -21845 is
...111111010101010101011,
which agrees with your calculation.

For the 2-adic reciprocal of a (rational) integer, you can probably prove something about its binary representation being eventually periodic to the left.



1: Both 2-adics and the reals have a binary representation. A sequence of binary digits can represent a 2-adic number iff it's finite on the right, and a real number iff it's finite on the left. If its finite on both ends, then it represents the same rational number in the two different number systems.

 

[jambaugh]

If you stick to finite subsets of N, your arithmetic simply gives you N. The correspondence was given in your opening post; the finite subset S of N represents the nonnegative integer

$$\sum_{s \in S} 2^s$$

Yes of course.

The correspondence between the arithmetic you define and the 2-adic integers is given by the same sum: any (possibly infinite) subset S of N represents the 2-adic integer

$$\sum_{s \in S} 2^s$$

(where convergence is in the 2-adic metric)

Ah, I was looking at the wrong reference (p-adic rationals). Found the definition at http://mathworld.wolfram.com/p-adicInteger.html"

Thanks for naming them...I never found a reference to the construction in the few searches I made. Do you know if one can map 4-adic numbers to Conway's "games"? It would seem you could use the two bits to indicate left, right or both inclusions in his extension of the Dedekind cuts.


I (think I) understand the convergence issues but I need to look more closely at the norm you posted.

And when you generalize to take subsets of Z that contain finitely many negative numbers, you get precisely the 2-adic rationals, with the correspondence again given by the same sum

$$\sum_{s \in S} 2^s$$

But given that you didn't bound the positive elements you also have the rationals with denominator co-prime to 2 and thence you get all the rationals (plus non-rational 2-adic numbers).

No: the square of any of your numbers ends in either 00 or 001, in the 2-adic repres[e]ntation.

Right, and I think one can then make an inductive argument that no irrational square roots exist in the set.

The following sequence converges to the reciprocal of the odd number N:

x₀ = 1
x_k+1 = x_k * (2 - N * x_k)

x_k will be correct in the rightmost 2^k bits.

(This is Newton's method with f(x) = N - 1/x)

e.g. to compute 1/3, we go through the sequence:

1
-1 = 1 * (2 - 3 * 1)
-5 = -1 * (2 + 3 * 1)
-85 = -5 * (2 + 3 * 5)
-21845 = -85 * (2 + 3 * 85)
...

The right 16 bits of this number are guaranteed to be correct. The 2-adic represntation of -21845 is
...111111010101010101011,
which agrees with your calculation.

For the 2-adic reciprocal of a (rational) integer, you can probably prove something about it being eventually periodic to the left.

Yes. Let me see... it is easier to define a negative reciprocal first then one's complement it:

Given n is odd I think you can find a lemma in number theory where there is a k such that n divides 2^k-1, with then m = (2^k-1)/n. You take k-periodic (or k+1 periodic?) repetitions of m's bit pattern and that times n will be -1.

Not quite an algorithm but it can also act as a reverse proof that there does exist such a k or something close to this given one may independently prove the eventual periodicity.

Thanks,
James

 

[jambaugh]

One other question to you Hurkyl,

Given the 2-adic norm, there should then be convergence of series of rationals with denominator co-prime to 2, within the 2-adic integers. Such a series which converges to 1/2 in the reals would seem to yield an infinite set corresponding to 1/2. But this is I think impossible.

Norm convergence must not imply "bit-wise" convergence and so we can't assume closure in this field under the given norm.

Regards,
James Baugh

 

[Hurkyl]

Each of the absolute values on Q capture a different aspect of arithmetic. You already understand the real absolute value (i.e. the usual one), for which the notion of "closeness" is based on the ordering of the rationals. On the other hand, each of the p-adic absolute values relates to divisibility by p -- two numbers are "close" in the p-adic metric iff their difference is divisible by a large power of p.

Because the notion of "closeness" is different for the different absolute values, they each have a different notion of convergence. Your intuition was right; a sequence that converges to 1/2 in the real metric will generally fail to converge in the 2-adic metric. In fact:

Theorem: Let $a_i$ be a sequence of integers, and $b_i$ be a sequence of odd integers. Then $a_i / b_i$ does not converge to 1/2 in the 2-adic metric.​

Proof: $|a_i|_2 \leq 1$ ($a_i$ is an integer, and so 2 cannot divide it a negative number times), and $|b_i|_2 = 1$ (because 2 divides it exactly zero times). Thus $|a_i / b_i|_2 \leq 1 / 1 = 1$.

However, $|1/2|_2 = 2$, because 2 divides 1/2 exactly -1 times. (i.e. $1/2 = 2^{-1} * 1$, and 1 is odd). And so $|1/2 - a_i / b_i|_2 = 2$, which clearly does not go to zero as i increases.

(I used the fact that if $|a|_2 \neq |b|_2$, then $|a + b|_2 = \max\{|a|_2, |b|_2\}$. But even that's overkill; I could have just used $|x - y| \geq |x| - |y|$, which is true for any absolute value, not just the p-adic ones)



This implies that there are real numbers that have no analog in the 2-adics; we've already seen $\sqrt{1/3}$ as such an example.

Conversely, there are 2-adic numbers that have no analog in the real numbers; $\sqrt{-7}$ is such an example.

Similarly, there are 2-adic numbers that have no analog in the 3-adics, and so forth.

 

[Hurkyl]

Actually, the p-adics are complete, with respect to the p-adic metric.

While the sequence 1/3, 2/5, 3/7, 4/9, 5/11, ... converges to 1/2 with respect to real absolute value, it is not a Cauchy sequence in the 2-adic metric! It is not true that
$$\lim_{m \rightarrow +\infty, n \rightarrow +\infty} \left| \frac{n}{2n+1} - \frac{m}{2m+1} \right|_2 = 0,$$
which is required for this to be a Cauchy sequence. For example,

$$\left| \frac{n}{2n+1} - \frac{n+1}{2(n+1)+1} \right|_2 = \left| \frac{-1}{(2n+1)(2n+3)} \right|_2 = 1.$$


For an example in the opposite direction, the sequence

1, 2, 4, 8, 16, 32, ...

converges to zero in the 2-adic absolute value, while it fails to converge in the real absolute value.

 

[jambaugh]

...Because the notion of "closeness" is different for the different absolute values, they each have a different notion of convergence. Your intuition was right; a sequence that converges to 1/2 in the real metric will generally fail to converge in the 2-adic metric.

I get it. For a moment I thought the 2-adics where much more boring than I'd first hoped but not so. Its just the norm which is more boring IMNSHO.

Convergence in the norm does correspond to "bitwise convergence" (differences become larger multiples of two so each bit eventually becomes fixed).

This implies that there are real numbers that have no analog in the 2-adics; we've already seen $\sqrt{1/3}$ as such an example.

Conversely, there are 2-adic numbers that have no analog in the real numbers; $\sqrt{-7}$ is such an example.

I'd like to see the $\sqrt{-7}$ expanded if you have it on hand.
Of course this is a value in the complex field so the obvious next question is then are there 2-adic (p-adics in gen) with no complex analogue.

Clearly given the $\aleph_1$ cardinality there are many more 2-adics than can be expressed as analytic numbers.

Clearly the norm has all the right properties. It simply doesn't define the same ordering as the reals where the two sets intersect.

Does the p-adic norm define a total ordering of the field? Clearly such is not necessary as with the counter example of the complex numbers.

Finally do you know of a geometric presentation of p-adic #'s (e.g. a fractal in the complex plane?) analogous to the real number line where the norm is a metric on the point set?

Regards,
James

 

[jambaugh]

These aren't surreal numbers

Ahhh, re-reading my first post I see I mistakenly implied I was constructing surreal numbers. My intent was to say I had come up with a construction of a set of "numbers" other than the surreal numbers.

(While editing the original post I went back and added the qualifier "surreal" and this totally changed the meaning of the second half of the sentence.)

Very poor wording on my part, and my thanks to you Hurkyl for finally showing me what they are called in the lit.

Regards,
James Baugh

 

[Hurkyl]

The p-adic norm, in fact, doesn't yield an ordering. In fact, you cannot put an ordered ring structure on the p-adic integers for roughly the same reason you cannot put one on the complexes: you can write 0 nontrivially as a sum of squares. In the 2-adics, that's

$$0 = \left( \sqrt{-7} \right)^2 + \sum_{i = 1}^7 1^2,$$

in the p-adics for any p > 2, that's

$$0 = \left( \sqrt{1 - p^2 } \right)^2 + \sum_{i = 1}^{p^2 - 1} 1^2,$$

and in the complexes, you have

$$0 = i^2 + 1^2.$$


The p-adic norm does give a metric space structure, but it's not one that arises from an ordering.



If you assume the axiom of choice, you can embed the p-adic numbers as a field into the complexes. Alas, this is rather uninteresting, because (I think) you can embed any field of characteristic zero and of cardinality no greater than |C| into the complex numbers -- the p-adic topology and the complex topologies will not coincide, so this embedding only works in a purely algebraic sense.

Finally do you know of a geometric presentation of p-adic #'s (e.g. a fractal in the complex plane?) analogous to the real number line where the norm is a metric on the point set?

There's nothing wrong with taking the p-adic numbers themselves as the point set; then the p-adic absolute value is a metric on that set, and gives you a metric space. In fact, this metric space (often written Q_p) is precisely the completion of Q with respect to the p-adic metric. (In the same way that R is the completion of Q with respect to the real metric)

 

[Hurkyl]

I'd like to see the $\sqrt{-7}$ expanded if you have it on hand.

Nope. But we can compute it! I've already listed Newton's method. I'll now show a way that's reasonable for computing a few bits by hand.

-7 = ...001₂, so we have 2 possible initial estimates for its square root: 1 = 01₂ and 3 = 11₂. (While we have 3 bits of precision for 1^2 ~= -7 and 3^2 ~= -7, we only have 2 bits of precision on 1 and 3)

Now, we extend our precision by 1 bit: -7 ~= 1001₂
1^2 = 1 = 0001₂
3^2 = 9 = 1001₂

1^2 is wrong, so we have to add a one to it. Our new estimates for the square roots are:
5 = 101₂
3 = 011₂

-7 ~= 11001₂
5^2 = 25 ~= 11001₂
3^2 = 9 ~= 01001₂

3^2 is wrong, so we have to add a one to it. Our new estimates are:
5 = 0101₂
11 = 1011₂

-7 ~= 111001₂
5^2 = 25 ~= 011001₂
11^2 = 121 ~= 111001₂
New estimates:
21 = 10101₂
11 = 01001₂

And so forth.