Thread by @gro_tsen

Let me use this as a pretext to talk about Conway's field of “nimbers”, which I think is a remarkable construction. It consists of defining two operations, which I'll write ⊕ and ⊗, on ordinals (but if you're afraid of ordinals, they're already interesting on ℕ). ⤵️ •1/30

https://twitter.com/JDHamkins/status/1437021245602738184

The operations can be defined by reference to games (below), or given an inductive definition — which is remarkably simple for the complexity it produces:

x⊕y := mex ( {x′⊕y : x′<x} ∪ {x⊕y′ : y′<y})

x⊗y := mex {(x′⊗y)⊕(x′⊗y′)⊕(x⊗y′) : x′<x, y′<y}

That's all! •2/30

Here, “mex S”, means “the smallest [ordinal] which is NOT in the set S”. So x⊕y is the smallest which is NOT of the form x′⊕y for x′<x nor of the form x⊕y′ for y′<y, and x⊗y is the smallest which is NOT of the form (x′⊗y)⊕(x′⊗y′)⊕(x⊗y′) for x′<x and y′<y; … •3/30

… these definitions are inductive: to define x⊕y or x⊗y, you are presumed to already know the value of all x′⊗y′ when x′≤x and y′≤y with at least one of the inequalities strict. But this makes sense by induction (ordinary induction for ℕ, transfinite for ordinals). •4/30

Note that there's no special case for 0 in the induction, because mex(∅)=0 so that 0⊕0=0 and 0⊗0=0. Also, if you're afraid of ordinals, you can just consider the case where x,y∈ℕ, which implies that x⊕y and x⊗y also are in ℕ. •5/30

So, to compute the table of ⊕, which is displayed below, each entry in the table is computed as ‹the smallest number which does NOT appear earlier in the line or earlier in the column› (note: it's “smallest which does not appear”, not “least greater than all which do”). •6/30

The table of ⊗ is much more tedious to compute because to compute any entry x⊗y we must look at every combination of an earlier line x′ and an earlier column y′, and for every such we compute the nim-sum (x′⊗y)⊕(x′⊗y′)⊕(x⊗y′) of three entries — then we take the mex. •7/30

The operations ⊕ and ⊗ are known as the “nim-sum” and “nim product” respectively. I defined them inductively without any reference to games, but here's how they relate to (two perfect knowledge two-player impartial games,) a form of nim and a 2-dimensional variant: … •8/30

‣ 1D variant: the game board consists of an infinite array of cells, labeled 0,1,2,3… even through the ordinals if you wish. Each cell can contain an arbitrary finite number of (interchangeable) stones, the total number being also finite. … •9/30

… A move in the game consists of taking one stone from one cell and moving it to an earlier (i.e., smaller-labeled) cell of the board. That's all. Stones in cell 0 cannot be moved so they are effectively discarded. Player alternate turns, the first who cannot play loses. •10/30

‣ 2D variant: similar, but the board is 2-dimensional, the cells labeled (x,y) with two coordinates (natural numbers or, if you want, ordinals). A move consists of replacing any one stone at (x,y) with THREE stones: at (x′,y), (x′,y′) and (x,y′) (forming a rectangle), … •11/30

… again with x′<x and y′<y, so stones on line or column 0 cannot be moved and are effectively discarded. The stones multiply but the game still always comes to an end (this isn't so trivial!). Again, the first player who cannot play (all stones are on line/col. 0) loses. •12/30

The 1D game is just the game of nim in (thin) disguise en.wikipedia.org/wiki/Nim — and the winning strategy consists of playing so as to cancel the nim sum of the labels of the squares where the stones lie (note: I'll point out below that ⊕ is associative and z⊕z=0). •13/30

The 2D game is more complex and the winning strategy consists of playing so as to cancel the nim sum of the x⊗y for all the squares (x,y) of the stones in the game. (More generally, this nim sum gives the Sprague-Grundy value of the game position.) •14/30

(One could easily define a 3D or higher-D game by reproducing stones along parallelepipeds, but the winning strategy would be always the same: take the nim-product of the coordinates of the stone, and nim-sum them over every stone.) •15/30

But enough with games. The operations ⊕ and ⊗ can be defines without any reference to games, as I did earlier. The surprising thing is, they have many nice properties, and define a remarkable algebraic structure. Let me state some results (mostly due to J.H. Conway). •16/30

First, ⊕ is associative and commutative (actually, I used this implicitly before), has 0 as neutral element, and satisfies z⊕z=0 for all z. The set {z : z<2^k} is closed under ⊕ for every k, so it forms an Abelian group. But in fact, we can be more precise: … •17/30

… the nim-sum ⊕ is simply the “exclusive or” operation on binary expansions (for ordinals, see:

https://twitter.com/gro_tsen/status/1437033209343225858

‌), which is clear in the table given earlier (tweet 6). Hence the well-known winning strategy in nim: play to cancel the XOR of the numbers of sticks. •18/30

Now ⊗ is more mysterious. However, it is also associative and commutative, has 0 as absorbing element and 1 as neutral element, and it is distributive over ⊕. (Also, if x>0 and x⊗y=x⊗y′ then y=y′.) That's already nice! •19/30

This already implies that whenever Δ is such that {z : z<Δ} is stable under ⊕ and ⊗, then it is a commutative ring (indeed an integral domain). In fact, in many cases (“club-many” cases if you know what that means) it turns out to be a field: … •20/30

… e.g., if Δ is the integer 2^(2^r) for r∈ℕ, or the ordinal ω (so {z : z<Δ} = ℕ), or the ordinal ω^(ω^r) for r∈ℕ, or ω^(ω^ω), or ω^(ω^(ω^ω)), or ω^(ω^((ω^ω)+1)), or ε₀, or any uncountable cardinal, then {z : z<Δ} is a field (of char 2) under the nim ops ⊕ and ⊗. •21/30

In fact, in the case of ω^(ω^ω) or any uncountable cardinal κ, it turns out to be not just a field, but an algebraically closed field. Specifically, ω^(ω^ω) is the algebraic closure of the field 𝔽₂ with two elements; and κ of that by adding κ indeterminates. •22/30

There are many more such fields. (Conway points out that the class of all ordinals is also an algebraically closed field under ⊕ and ⊗, but this is no more precise than what I already said, and I think it's better to state things at the level of some cardinal.) •23/30

The ordinal ω^(ω^(ω^ω)) (meaning the set of smaller ordinals, under ⊕ and ⊗) turns out to be the field of rational functions in one indeterminate over the algebraic closure of 𝔽₂ (represented as ω^(ω^ω)). An open problem is: what is the algebraic closure of THAT: … •24/30

… i.e., what ordinal gives us the algebraic closure of 𝔽₂(t), the question of the “second nim transcendental” (the first is ω^(ω^ω)). In a note on “Nim multiplication”, H. W. Lenstra conjectured that it is the small Veblen ordinal (though he doesn't call it that). •25/30

He leaves one inequality (which amounts to proving that the small Veblen ordinal is an algebraically closed field under nim operations) as an exercise(!), I think I know how to do this; the other inequality, on the other hand, seems exceedingly difficult. •26/30

But going back to x and y being natural numbers, I pointed out that x⊕y is just the XOR of the binary expansions of x and y, which is easy to compute; but what about x⊗y? The inductive definition I gave at the start of this thread is insanely lengthy, can we do better? •27/30

It turns out we can! Since ⊗ is distributive over ⊕ (and 2^k ⊕ 2^(k′) is the usual sum when k>k′), all we need to compute is 2^k ⊗ 2^(k′). Now writing k,k′∈ℕ themselves in base 2, the computation can be done by knowing just two things: … •28/30

‣ 2^(2^r) ⊗ 2^(2^r′) = 2^(2^r + 2^r′) (as the ordinary product) when r≠r′, and
‣ 2^(2^r) ⊗ 2^(2^r) = 2^(2^r) + 2^((2^r)−1), where + is the same as ⊕ here, and 2^((2^r)−1) = 2^(2^(r−1)) · ⋯ · 2^(2^1) · 2^(2^0) (where · is the same as ⊗ here).
•29/30

Using these two rules, it is possible to fairly efficiently compute x⊗y for any two integers x,y and ℕ endowed with these two nim operations is the quadratic closure of 𝔽₂ (or if you want, 𝔽_(2^∞)). Something which, I have to say, really blows my mind. •30/30