7
$\begingroup$

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...

  • 0
    Isomorphic how? One set is naturally *well*-ordered and the other cannot be linearly ordered in coherence with its field structure.2012-07-04
  • 4
    The field with 8 elements is not an extension field of the field with 4 elements.2012-07-04
  • 0
    @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.2012-07-04
  • 0
    @Hurkyl a very good point! I'll correct that.2012-07-04
  • 0
    But the ordinals do not make a good field. Their addition and multiplication is not commutative is hardly invertible. How do you define the addition on the ordinals?2012-07-04
  • 0
    @AsafKaragila See Conway's book or Lenska's note for that, or even this link: http://www.neverendingbooks.org/index.php/on2-conways-nim-arithmetics.html the addition is binary arithmetic (for finite numbers) without carrying the extra digit. multiplication is a lot more complicated.2012-07-04
  • 0
    You may want to add that link to the post.2012-07-04
  • 2
    +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:-)2012-07-05

1 Answers 1

4

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}$.

  • 0
    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}$. :-(2012-07-05
  • 0
    This is nevertheless a helpful answer! I'll comment more ( or accept) later today when I can read over it a bit more carefully.2012-07-05
  • 0
    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?2012-07-05
  • 0
    Oops. Never mind, such fields are covered by infinite ordinals. This is why I should wait to respond!2012-07-05
  • 0
    Yeah. I have to confess that it is anything but clear to me, why $\omega$ should have a cubic minimal polynomial :-)2012-07-05
  • 0
    this is indeed a helpful answer, and sheds much light on the proof in conway's book I didn't understand (he uses the same technique with that polynomial). In fact it solves my problem for all finite numbers where its possible to solve it. But I'd still like a description of the other subfields, though. I'm going to leave the question open, but if you're interested I'll post a note or another question on the bits I [do not] understand from Conway's book. Thanks! :D2012-07-05
  • 0
    @mebassett: Glad to hear that you find this helpful. It is, of course, not a full solution, so you should leave it open. Actually I am more than a bit curious myself to see how the rest of it goes! I thank you for bringing this construction to my notice.2012-07-06