I.6a: The Nimber FIELD

This post is going to rely on more background than my average posts. In particular, facts about finite fields and ordinals will come into play. If you don’t know about these things at all, don’t worry, they won’t be necessary for I.7, etc. As a disclaimer, a good portion of this post is coming from Conway’s excellent, if slightly inaccessible, On Numbers and Games.

As discussed before, ⊕ (binary xor) makes ω (the set of nonnegative integers) into an abelian group of order 2. Also, by the rules of Nim and the Sprague-Grundy theorem, we know that p⊕q=mex({p’⊕q,p⊕q’:p'<p,q'<q}). To go along with this, there is a nice multiplication operation, similarly defined: p⊗q=mex({(p'⊗q)⊕(p⊗q')⊕(p'⊗q'):p'<p,q'<q}). It's easy to show (as in, it requires no background other than definitions) that ⊕ and ⊗ make ω into a commutative ring with 1. With a terrible bit of induction, it can be shown that 22n⊗22m is their regular product if n≠m, and is 3*22n/2 if n=m. With this in hand, you can show (in a terribly ugly way) that if you use these operations on the set of numbers below a “Fermat 2-power” 22n, you actually have a finite field! Thus, ω is the direct limit (think “union”) of the finite fields of size 22n. ω is not an algebraically closed field, though.

Since the ordinals are well-ordered, the mex definitions for ⊕ and ⊗ extend just fine to the class of all ordinals, On. When we give it the operations ⊕ and ⊗, the same proof that ω became a commutative ring works: On becomes a commutative RING with 1 (in fact it becomes an algebraically closed FIELD), denoted On2. A technical note: On is a proper class, not a set, so it can’t really be a ring or a field; the capitalization of “RING” and “FIELD” in the previous sentence is a standard way to represent this distinction.

As mentioned in I.6, ⊕ works essentially the same way in the infinite case as it did in the finite case: like binary xor. ⊗ in the infinite realm will be a little weirder; the pattern for finite numbers doesn’t really continue in any meaningful way. We can still get some preliminary results to help us understand things.

n⊗ω=nω for finite n.
Why?
We’ll prove it by induction on n; it’s trivial for n=0. By definition, n⊗ω=mex({(m⊗ω)⊕(n⊗o)⊕(m⊗o):m<n,o<ω}). By inductive hypothesis, m⊗ω=mω for any m<n, so we have to deal with mex({(mω)⊕(n⊗o)⊕(m⊗o):m<n,o<ω}). Consider a Fermat 2-power above n. Then the set of numbers below that form a field, so for any choice of m, we can solve the equation (n⊗o)⊕(m⊗o)=x for o. Since m and x are arbitrary, any ordinal less than nω is in the set (and no others), so the mex is just nω, as desired. ✓

ω⊗ω=ω2.
Why?
By definition, ω⊗ω=mex({(m⊗ω)⊕(ω⊗n)⊕(m⊗n):m,n<ω}). From the previous fact and the commutative ring structure of On2, this is mex({(m⊕n)ω+(m⊗n):m,n<ω}). To see that this is ω2, we must show that m⊕n and m⊗n are independently arbitrary. I.e. we need to be able to solve m⊕n=x and m⊗n=y for m and n. This system reduces to a quadratic in m, and we can solve any desired quadratic in a sufficiently big finite field of characteristic 2. ✓

ω⊗ω2=2.
That’s not a typo. Why?
By definition, ω⊗ω2=mex({(n⊗ω2)⊕(ω⊗(pω+q)⊕(n⊗(pω+q):n,p,q<ω}). Collecting like terms and using previously shown facts, this reduces to mex({(n⊕p)⊗ω2⊕(q+n⊗p)ω⊕n⊗q:n,p,q<ω}). If the expression inside the set is finite, then there must be no ω2 term, so n⊕p=0 so n=p. Similarly, there must be no ω term so q=n⊗p=n⊗n. Thus, the only finite numbers attainable are those of the form n⊗q where q=n⊗n. 0=0⊗0⊗0, so it’s not the mex, and similarly for 1. The question boils down to “does 2 have a cube root in any of the finite fields of size 22k?” Since 2⊗2⊗2=1, the question becomes “does 1 have any primitive 9th roots in one of those fields?” Since the multiplicative groups are cyclic, and 22k is never 1 modulo 9, the answer is no, and the mex is just 2, as desired. ✓

Very do-able exercise (but requiring some background): What are the other cube roots of 2?

At the beginning of this post I alluded to some inelegant inductions to prove some of the basic facts, and haven’t provided any justification at all for claims like “On2 is a FIELD“. Almost everything you need to know about On2 actually follows from a beautiful collection of theorems I’m quoting straight from Conway (after dealing with notation differences) which aren’t terribly hard to prove (once you know the statements), but which I won’t spend time proving here. Be warned, Δ and Γ are ordinals playing double-duty as both an ordinal and the set of all lower ordinals; also, I’ll use α⊗3 to denote α⊗α⊗α, etc.

  • If Δ is not a group under ⊕, then Δ=α⊕β, where (α,β) is the lexicographically earliest pair such that α⊕β is not in Δ.
  • If Δ is a group under ⊕, then Δα⊕β=Δα+β for all α and all β∈Δ
  • If Δ is a group under ⊕ but not a ring with ⊗, then Δ=α⊗β, where (α,β) is the lexicographically earliest pair such that α⊕β is not in Δ
  • If Δ is a ring, and Γ≤Δ is an additive subgroup all of whose non-zero elements have ⊗-multiplicative inverses in Δ, then Δ⊗γ=Δγ for all γ∈Γ.
  • If Δ is a ring, but not a field, then Δ is the multiplicative inverse for the smallest element α of Δ without an inverse in Δ
  • If Δ and α are as in the previous line, and Γ is the largest ordinal≤α which is a group under ⊕, then (Γ is a field and) Δ⊗n⊗γn⊕Δ⊗(n-1)⊗γn-1⊕…⊕Δ⊗γ1⊕δ=Δ(Γn-1γn+…+γ1)+δ for all n∈ω, all δ∈Δ, and all γ01,…γn∈Γ. (This one is actually a little subtle; Conway’s proof contains an error that was patched by Lenstra.)
  • If Δ is a field but not algebraically closed, then Δ is a root of the lexicographically earliest polynomial having no root in Δ. [In the lexicographic order, we examine high degree coefficients first.]
  • If Δ is as in the previous line, and N is the degree of that “earliest” polynomial, then Δ⊗n⊗δn⊕…⊕δ0nδn+…+δ0 for all n<N and all δ0,…,δn∈Δ.
  • If Δ is an algebraically closed field, then Δ is transcendental over Δ and the previous equation holds for all n∈ω.

In Conway’s words, “Each ordinal Δ extends the set of all previous ordinals in the simplest possible way.” With this in hand it’s not to bad to prove things like “distinct powers of 2 add normally”. or ω⊗3=2, or anything else you’d want to know, really. There are more things that can be said about On2, but I’ll leave you with a couple more facts: (ω3)⊗3=ω and ωωω is algebraically closed.

Wait a second, if we have all of these fields, there’s gotta be a way to divide. In fact, finding inverses does not require trial and error. The inverse of p, call it q, is given recursively by q=:1/p= mex({0,((p’⊕p)⊗q’⊕1)⊗(1/p’):0<p'<p,q'<q}).

Since "q'<q" is part of the expression, it might not seem like this calculation can be done. Let’s calculate the inverse of 2. I’ll build up the list of things we’re taking the mex of recursively:
We know 0 is in there, so the mex is at least 1.
Since the mex is at least 1, we may take q’=0, and since p=2, p’ is always forced to be 1.
Thus, we also have in the set: ((1⊕2)⊗0⊕1)⊗(1/1)=1.
So the mex is at least 2, and we may take q’=1, yielding ((1⊕2)⊗1⊕1)⊗(1/1)=3⊕1=2.
So the mex is at least 3, and we may take q’=2, yielding
((1⊕2)⊗2⊕1)⊗(1/1)=3⊗2⊕1=(1⊗2)⊕(2⊗2)⊕1=2⊕3⊕1=1⊕1=0.
But we already knew 0 was in the set, so we can’t get anything new anymore, and 1/2=3.

With the previous calculation we’ve already multiplied 2⊗3 to get 1, so this calculation really worked. It takes a bit of thought to see why this weird recursive definition will always work. Incidentally, there’s a similar formula that gives the square root: r=√s= mex({√s’,(p⊗q⊕s)⊗(1/(p⊕q)):s'<s, and p,q<r distinct}). Both of these formulas (and perhaps the formula for ⊗ as well) seem to come out of nowhere without the context of the Surreal Numbers, which will be discussed in a much later post.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s