# what simple extensions can be naturally embedded into Conway's algebraic closure of $\mathbb{F}_2$?

John Conway proved in his book, On Numbers and Games (ch6, theorem 49) that the set of all ordinals smaller than $\omega^{\omega^\omega}$ form a field of characteristic 2 that is isomorphic to $\bar{\mathbb{F}_2}$, the algebraic closure of $\mathbb{F}_2$. The arithmetic of this field is described in more detail in Lenstra's note, On the Algebraic Closure of Two Additionally, there's another good note on this field at lieven le bruyn's blog, neverendingbooks

In doing so, Conway also proved that the finite numbers that form fields in the same way are of the form $2^{2^k}$. Let $[n]$ denote one of such fields (exempli gratia, $[4]=[2^2] ={0,1,2,3}$, the set of all smaller ordinals. Hence we have all extensions $[2^{2^n}]$ contained in the algebraic closure.

Is there a choice (and explicit construction) of monic irreducible polynomials $m_n(x)$ of degree $n$ so that the field isomorphism $$\mathbb{F}_2[x]/(m_n(x)) \cong [2^n]$$ is natural for all finite $n=2^k$?

I suppose I need to say what I mean by "natural". Let me try to explain, and please let me know if this makes no sense: We can always construct such an isomorphim $\phi$, if we choose a root $\mu$ of $m_n(x)$ and a corresponding $\phi(\mu) \in \{3, 4, \ldots, n\}$, then the axioms of fields and isomorphisms will force the other choices (I think). I want a set of $m_n(x)$'s so that the isomorphism doesn't depend on any arbitrary choices I make. (I really don't know how to make precise what I mean by natural. Suffice to say that I'm asking if there is a preferred set of polynomials that make the isomorphism obvious!)

Update* Of course, other fields, $\mathbb{F}_{2^k}$ for k not a power of two, must also live inside $\omega^{\omega^\omega}$. As already noted, $[\omega]$ is a quadratic closure. Conway's method is then to take a cubic closure, by noting that $[\omega^3], [\omega^9], \ldots$ are also fields; and then taking a quintic closure through the fields $[\omega^\omega], [\omega^{5 \omega}], \ldots$, et cetera. Hence a field like $\mathbb{F}_8$ can be embedded into one of the cubic fields, exempli gratia $[\omega^3]$. Can we describe how $\mathbb{F}_{2^k}$ fits into these fields, and can we also find an irreducible polynomial that gives us a natural embedding?

*Perhaps this should be a separate question? Let me know...

• Isomorphic how? One set is naturally well-ordered and the other cannot be linearly ordered in coherence with its field structure. – Asaf Karagila Jul 4 '12 at 23:17
• The field with 8 elements is not an extension field of the field with 4 elements. – user14972 Jul 4 '12 at 23:19
• @AsafKaragila field isomorphisms here. My suspicion from the literature, actually, is that there isn't any preferred field extension, but I wanted to ask the clever folks on here before I run off with that conclusion. – mebassett Jul 4 '12 at 23:20
• @Hurkyl a very good point! I'll correct that. – mebassett Jul 4 '12 at 23:21
• +1: Thanks for telling me about this! I didn't know about this construction by Conway (even though I'm relatively familiar with finite NIM-addition). Playing with the multiplication rule a bit quickly leads to the observation that with finite ordinals you only get the fields $F_k=GF(2^{2^k})$ as the intervals $F_k=\{0,1,\ldots,2^{2^k}-1\}$. This family of finite fields has other recursive constructions (trying to reformulate one in a way that helps here). So for example the unique field of 8 elements has the elements 0,1 and then 6 infinite ordinals (that I dare not try and guess yet:-) – Jyrki Lahtonen Jul 5 '12 at 7:22

From le Bruyn's notes (as well as from the useful exercise of reproducing the NIM-multiplication tables he presented) it follows that only the fields $F_k=\mathbb{F}_{2^{2^k}}$ can be realized with NIM-arithmetic of finite ordinals in such a way that $F_k=\{0,1,\ldots,2^{2^k}-1\}$. This is all well (and hardly a surprise - at least in hindsight), because these finite fields form a nested sequence $$F_0=\mathbb{F}_2\subset F_1=\mathbb{F_4}\subset F_2=\mathbb{F}_{16}\subset F_3=\mathbb{F}_{256}\subset\cdots$$ Below I will describe another way of recursively constructing this sequence of finite fields. As a consequence we will derive a recursive formula for the minimal polynomials of the ordinals $2^{2^k}$. I admit that I don't feel confident enough to try my hand with the infinite ordinals, so I leave that to somebody else.

We work inside an algebraic closure $K$ of $\mathbb{F}_2$. Let us define a sequence of elements $\alpha_i\in K,i=0,1,\ldots,$ as follows. Let $\alpha_0=1$, and let, for all natural numbers $k$, $\alpha_{k+1}$ be one of the solutions of the equation $$x^2+x+\alpha_k=0$$ in $K$. This equation has two solutions ($\alpha_{k+1}+1$ is the other), but just pick one of them. This may sound unsatisfactory at first, but they will turn out to be conjugates, so cannot be distinguished by algebraic means any way.

Lemma. For all $k=0,1,\ldots,$ we have \begin{aligned} (i)&F_k=F_0(\alpha_k),\\ (ii)&\sum_{j=0}^{2^k-1}\alpha_k^{2^j}=1,\\ (iii)&\text{the polynomial}\ x^2+x+\alpha_k\in F_k[x]\ \text{is irreducible.} \end{aligned}

Proof. An induction on $k$. The case $k=0$ is trivial, because the sum in claim $(ii)$ consist of only the term $\alpha_0=1$, and the polynomial $x^2+x+1$ is irreducible over the prime field, because it has no zeros there.

Assume that the claim holds for some $k=\ell$. From part $(iii)$ of the induction hypothesis $\alpha_{\ell+1}\notin F_\ell$, and $[F_\ell(\alpha_{\ell+1}):F_\ell]=2$, so from part $(i)$ of the induction hypothesis it follows $F_\ell(\alpha_{\ell+1})$ is the unique quadratic extension of $F_\ell$, i.e. $F_{\ell+1}$, proving part $(i)$ of the induction step. Part $(ii)$ then follows from part $(ii)$ of the induction hypothesis as follows. In the sum $$S(\ell+1):=\sum_{j=0}^{2^{\ell+1}-1}\alpha_{\ell+1}^{2^j}$$ let's write $j=2n+\epsilon$, where $0\le n\le 2^\ell-1$ and $\epsilon\in\{0,1\}$, so \begin{aligned} S(\ell+1)&=\sum_{n=0}^{2^k-1}\sum_{\epsilon=0}^1\alpha_{\ell+1}^{2^{2n+\epsilon}}\\ &=\sum_{n=0}^{2^\ell-1}(\alpha_{\ell+1}^2+\alpha_{\ell+1})^{2^n}\\ &=\sum_{n=0}^{2^\ell-1}\alpha_\ell^{2^n}=S(\ell)=1. \end{aligned} Part $(ii)$ is equivalent to saying that the absolute trace of $\alpha_{\ell+1}$ $$tr^{F_{\ell+1}}_{F_0}(\alpha_{\ell+1})=1.$$ This is relatively well known (ask, if you haven't seen this) to imply that the polynomial $$x^2+x+\alpha_{\ell+1}$$ has no solutions in $F_{\ell+1}$ proving part $(iii)$, the induction step, and the lemma. Q.E.D.

The NIM-arithmetic rule from le Bruyn's notes: $2^{2^k}\cdot2^{2^k}=2^{2^k}+2^{2^{k-1}}$ then quickly allows us to define an automorphism from $\bigcup_{k=0}^\infty F_k$ to the set of finite ordinals by (NIM-algebraically) extending the mapping $\alpha_k\mapsto 2^{2^k}$.

I promised a fact about minimal polynomials. The minimal polynomial $f_1(x)$ of $\alpha_1$ over the prime field $F_0$ is $$f_1(x)=x^2+x+1.$$ The Lemma and the recursive definition then imply that the minimal polynomials $f_k(x)$ of $\alpha_k$ over $F_0$ satisfy the recurrence relation. $$f_{k+1}(x)=f_k(x^2+x).$$ I leave it as an exercise to prove that this implies the closed formula $$f_k(x)=1+\sum_{j=0}^k{k\choose j}x^{2^j}\in F_0[x].$$ This is then also the minimal polynomial of the ordinal $2^{2^k}$.

• Sorry about not really doing any NIM-arithmetic here. I'm rather relying on a few bits from le Bruyn's notes. The only bit answering the OP's question is that final formula for the minimal polynomials of the ordinals $2^{2^k}$. :-( – Jyrki Lahtonen Jul 5 '12 at 9:32
• This is nevertheless a helpful answer! I'll comment more ( or accept) later today when I can read over it a bit more carefully. – mebassett Jul 5 '12 at 10:24
• One thing is bothering me, though, and this may be a separate question: if $\omega^{\omega^\omega}$ is an algebraic closure, and if an algebraic closure contains all $\mathbb{F}_{2^k}$, even k not a power of 2, then shouldn't $\omega^{\omega^\omega}$ contain a subfield isomorphic to $\mathbb{F}_{2^k}$? Indeed this is hard to reconcile with the multiplication table at me neverendingbooks for say, k=3. Ordinals $2^{2^k}$ only give us a quadratic closure, no? – mebassett Jul 5 '12 at 10:37
• Oops. Never mind, such fields are covered by infinite ordinals. This is why I should wait to respond! – mebassett Jul 5 '12 at 10:43
• Yeah. I have to confess that it is anything but clear to me, why $\omega$ should have a cubic minimal polynomial :-) – Jyrki Lahtonen Jul 5 '12 at 11:05