The algebraic closure of the rationals
John Baez
algebra, and we were led to some puzzles neither of us knows
anything about. Let Qbar stand for the algebraic closure of
the field of rational numbers. To what extent can we get our
hands on Qbar in an explicit way?
(Perhaps I should say Qbar is "an" algebraic closure, since
while they're all isomorphic, the full set of isomorphisms is
hard to understand, and this is part of the issue.)
For example:
1) Is there a way to enumerate the elements of Qbar such that
relative to this enumeration, the field operations are computable?
If so, how efficiently can they be computed? If not, how far
up the hierarchy of impossible-to-actually-compute functions do
we have to go?
2) On the other extreme: can we even prove the existence of Qbar
without the axiom of choice, or perhaps countable choice?
3) I've heard that it's even hard to get an "explicit" description
of the algebraic closures of finite fields - are there any
theorems to this effect?
tc...@lsa.umich.edu
>1) Is there a way to enumerate the elements of Qbar such that
>relative to this enumeration, the field operations are computable?
>If so, how efficiently can they be computed? If not, how far
>up the hierarchy of impossible-to-actually-compute functions do
>we have to go?
Computability is not a problem. The simplest way to enumerate algebraic
numbers is by means of their minimum polynomials. Given univariate
polynomials f(x) and g(x) with integer coefficients, you can compute a
polynomial h(x) that contains among its roots all numbers of the form a+b
where a is a root of f(x) and b is a root of g(x); similarly for a*b.
To see the proof, just look up the textbook proof that the algebraic
numbers form a field.
There are some annoying issues associated with trying to keep track of
"which root of f(x) is which" (the simplest example being, how do you
keep i and -i straight?), and eliminating extraneous factors of h(x),
but none of this introduces uncomputability problems.
>2) On the other extreme: can we even prove the existence of Qbar
>without the axiom of choice, or perhaps countable choice?
I think the construction sketched above shows that you don't need choice,
though perhaps I'm missing some subtlety.
>3) I've heard that it's even hard to get an "explicit" description
>of the algebraic closures of finite fields - are there any
>theorems to this effect?
I doubt it. Probably what underlies the rumor is the fact that if you
want to construct F_{p^n} then you need to pick an irreducible degree-n
polynomial over F_p, and in general there will be many choices, none of
which will be "canonical" or "natural." However, as far as computability
or constructibility goes, you can always factor x^(p^n) - x and make up
some rule for picking a suitable irreducible polynomial---say, the first
one lexicographically or something. The list of polynomials you get as
you go up to higher and higher degrees will not have a "simple explicit
description," but I doubt there is a satisfactory way to define the word
"explicit" precisely enough to let you prove theorems about it.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
Jim Heckman
On 6-Apr-2006, ba...@galaxy.ucr.edu (John Baez)
wrote in message <e13l06$sr9$1...@glue.ucr.edu>:
[...]
> (Perhaps I should say Qbar is "an" algebraic closure, since
> while they're all isomorphic, the full set of isomorphisms is
> hard to understand, and this is part of the issue.)
[...]
> 2) On the other extreme: can we even prove the existence of Qbar
> without the axiom of choice, or perhaps countable choice?
Pretty much every undergraduate algebra textbook has a proof that C
contains an algebraic closure of Q, which theorem is in fact almost
trivial given the Fundamental Theorem of Algebra.
I think you do need AC to show that all algebraic closures of a
given field are isomorphic, and perhaps also to show the existence
of an algebraic closure for fields other than subfields of C.
[...]
--
Jim Heckman
JoeSh...@aol.com
extensions of finite fields", AMS Contemporary Mathematics series)
which treats this. In fact, it's not hard to get an "explicit
description" of any algebraic extension of a finite field -- they are
characterized by the orders of their finite subfields, which in turn
are characterized by functions from the set of primes to
{0,1,2,3,...,"infinity"} -- for any such function f, the corresponding
algebraic extension of Z/p has a finite subfield of order p^k iff the
prime factorization of k has the exponent of each prime q being <=
f(q).
If you are just interested in algebraic closures of finite fields,
there is an especially nice and explicit representation due to Conway
in the case of characteristic 2. The ordinal omega^(omega^omega) forms
an algebraically closed field of characteristic 2 under "nim-addition"
and "nim-multiplication". See Conway's book "On Numbers and Games", or
H.W. Lenstra's paper "Nim Multiplication" which can be found here:
http://hdl.handle.net/1887/2125
It is an interesting open problem to extend this construction to
characteristics other than 2. The idea is to define addition and
multiplication as far as possible inductively, and when you have a
choice pick the least ordinal consistent with the resulting structure
being part of a field; but in characteristic p>2 it is hard to find a
nice interpretation of the operations that makes them easy to compute.
-- Joe Shipman
David Madore
> 1) Is there a way to enumerate the elements of Qbar such that
> relative to this enumeration, the field operations are computable?
> If so, how efficiently can they be computed? If not, how far
> up the hierarchy of impossible-to-actually-compute functions do
> we have to go?
The usual manner is to represent a real element of Qbar by
* its minimal polynomial over Q (or perhaps, some polynomial, not
necessarily minimal, but probably at least separable, of which it is a
root),
* an interval which isolates the root from all other roots (or the
number of the root in the usual order on the reals).
Basically the trick is that sums and products can be computed by
universal rules (if P1 and P2 are polynomials over Q, there is a
polynomial, which can be given universally in function of the
coefficients of P1 and P2, whose roots are the sums of roots of P1 and
P2, and ditto for the product), and roots can always be isolated using
Sturm-Liouville (in other words, you can narrow the interval as much
as you want since Sturm-Liouville lets you count the number of roots
in any given interval).
This is for real algebraics; for the full Qbar, you just represent a
complex number by its real and imaginary parts (both of which are
algebraic if the complex is algebraic).
Actually programming this is *unbelievably* painful. As for the
algorithmic complexity, I think it's not that bad, in the sense that
if x and y have small height (for any reasonable definition of
"height") then computing x+y can be done in a reasonable time, but
there's a catch: the height of x+y grows considerably larger than that
of x or y, so any actual computation can become terribly difficult.
(The same problem happens for rationals: computing r+s where r and s
are rationals is polynomial in the height of r and s, but try
computing something like 1/2+1/3+1/5+1/7+1/11+1/13+1/17...)
For some specific uses it is better to use the p-adics than the reals:
the advantage is that p-adic approximation is *much* easier than real
approximation (thanks to the ultrametric properties); the disadvantage
is that whereas the reals are "almost" algebraically closed, the
p-adics are quite far from it, and representing elements of the
algebraic closure of Q_p is again quite a nuisance.
> 2) On the other extreme: can we even prove the existence of Qbar
> without the axiom of choice, or perhaps countable choice?
Yes, the *existence* of Qbar, or of any countable or even
well-orderable field (and various others, such as Q_p), can be shown
without the axiom of choice. However, the *uniqueness* of Qbar
requires the axiom of choice: it is consistent in ZF alone that there
exists an uncountable algebraic closure of Q. (Basically it's true in
ZFA because you can create atoms for elements of Qbar and let Galois
act on them and take the usual permutation model, and then some
embedding theorem gives the result in ZF.) I'm not sure about whether
one needs AC to show that the algebraic closure of Q constructed using
the reals and the p-adics as explained above actually give the same
thing.
> 3) I've heard that it's even hard to get an "explicit" description
> of the algebraic closures of finite fields - are there any
> theorems to this effect?
I don't think it's hard. In fact, here's a very elegant and
intriguing explicit construction of the algebraic closure of F_2,
which is due to Conway:
Define two binary operations, '#' and '@', on the class of ordinals,
by transfinite induction, by letting:
x # y = mex ( { x'#y | x'<x } union { x#y' | y'<y } )
x @ y = mex { (x'@y)#(x'@y')#(x@y') | x'<x and y'<y }
(respectively called the "Nim sum" and "Nim product" by Conway).
Then:
* the operation '#' coincides with the "exclusive or" on the binary
representation of ordinals (= unique representation as decreasing sum
of distinct powers of 2),
* the operations '#' and '@' make various ordinals (such as omega,
omega^omega, epsilon_0, omega_1, and in fact a closed unbounded class
of ordinals, or even "the class of all ordinals") into a field of
characteristic 2, which for some well-known ordinal (I think it is
omega^(omega^omega) or omega^omega or epsilon_0 or some such thing -
you can find the correct version in Conway's "On Numbers and Games")
is exactly the algebraic closure of F_2. (As for omega, i.e., the set
of natural numbers, it is the quadratic closure of F_2, this one I'm
sure about. Somewhere far beyond that we get the algebraic closure of
F_2(t), which is a much nastier beast than that of F_2, but I think
nobody knows exactly which ordinal that is - possibly the
Feferman-Schuette ordinal.)
This is as explicit as you might wish: there are no choices to be
made, everything is well-defined. It is not too computational,
however, because in principle to compute x@y for two ordinals x and y
you need to know x'@y' for every pair (x',y') with x'<=x and y'<=y and
(at least one not being equal): in fact, it's not that bad, and at
least up to omega the Nim product ('@') can be computed fairly
efficiently, I don't know what about higher ordinals but I suspect it
is reasonalby well-behaved at least as far as defining the algebraic
closure of F_2 goes.
I hope this answers your question.
--
David A. Madore
(david....@ens.fr,
http://www.dma.ens.fr/~madore/ )
John Baez
David Madore <david....@ens.fr> wrote:
>Actually programming this is *unbelievably* painful.
I bet! Thanks for the detailed description.
>> 2) On the other extreme: can we even prove the existence of Qbar
>> without the axiom of choice, or perhaps countable choice?
>Yes, the *existence* of Qbar, or of any countable or even
>well-orderable field (and various others, such as Q_p), can be shown
>without the axiom of choice. However, the *uniqueness* of Qbar
>requires the axiom of choice: it is consistent in ZF alone that there
>exists an uncountable algebraic closure of Q.
>I'm not sure about whether
>one needs AC to show that the algebraic closure of Q constructed using
>the reals and the p-adics as explained above actually give the same
>thing.
I can imagine it requiring countable choice to "construct" an
isomorphism between two countable algebraic closures of Q.
Does anyone know about this?
>> 3) I've heard that it's even hard to get an "explicit" description
>> of the algebraic closures of finite fields - are there any
>> theorems to this effect?
>
>I don't think it's hard. In fact, here's a very elegant and
>intriguing explicit construction of the algebraic closure of F_2,
>which is due to Conway:
>
>Define two binary operations, '#' and '@', on the class of ordinals,
>by transfinite induction, by letting:
>
> x # y = mex ( { x'#y | x'<x } union { x#y' | y'<y } )
>
> x @ y = mex { (x'@y)#(x'@y')#(x@y') | x'<x and y'<y }
What's "mex"?
>(respectively called the "Nim sum" and "Nim product" by Conway).
>
>Then:
>
>* the operation '#' coincides with the "exclusive or" on the binary
>representation of ordinals (= unique representation as decreasing sum
>of distinct powers of 2),
>
>* the operations '#' and '@' make various ordinals (such as omega,
>omega^omega, epsilon_0, omega_1, and in fact a closed unbounded class
>of ordinals, or even "the class of all ordinals") into a field of
>characteristic 2, which for some well-known ordinal (I think it is
>omega^(omega^omega) or omega^omega or epsilon_0 or some such thing -
>you can find the correct version in Conway's "On Numbers and Games")
>is exactly the algebraic closure of F_2.
I'd call this "hard", though it's certainly intriguing.
What field do you get if you just go up to omega?
David Madore
> David Madore <david....@ens.fr> wrote:
>>I'm not sure about whether
>>one needs AC to show that the algebraic closure of Q constructed using
>>the reals and the p-adics as explained above actually give the same
>>thing.
>
> I can imagine it requiring countable choice to "construct" an
> isomorphism between two countable algebraic closures of Q.
Actually, come to think of it, I now think any two countable algebraic
closures of Q can be shown to be isomorphic without using any form of
the axiom of choice, the argument being something like this: number
the elements of both fields by natural numbers (which can be done,
since we are assuming them to be countable), take the smallest-labeled
element of one field, say x, consider its minimal polynomial (over Q),
take its roots in the other field, consider the smallest-labeled among
them, say y, and map x to y; then map Q(x) to Q(y) in the only
possible way; then take the smallest-labeled element still not
accounted for, and so on.
And I think that answers my own question: the algebraic closure of Q
constructed using the reals or the p-adics are isomorphic (because
both are countable) even without using the axiom of choice. I'm not
completely certain I didn't make a subtle mistake somewhere along the
line, though.
And more or less the same argument seems to show that Countable Choice
implies the uniqueness of the algebraic closure of Q.
>>Define two binary operations, '#' and '@', on the class of ordinals,
>>by transfinite induction, by letting:
>>
>> x # y = mex ( { x'#y | x'<x } union { x#y' | y'<y } )
>>
>> x @ y = mex { (x'@y)#(x'@y')#(x@y') | x'<x and y'<y }
>
> What's "mex"?
Sorry... mex(S) is the smallest ordinal not belonging to S ("mex" for
"minimal excluded").
It's rather instructive, and rather intriguing, to work out the values
of x#y and x@y for small integer x and y.
> I'd call this "hard", though it's certainly intriguing.
Well I meant that the definition is only two lines long, and it is
algorithmically workable (and certainly *much* easier to program than
Qbar).
> What field do you get if you just go up to omega?
The quadratic closure of F_2, i.e., F_{2^{2^\infty}} if you will. In
this case, there are elegant ways of computing x#y and x@y based on
the binary representation of x and y (as I said, x#y is just exclusive
or; x@y is a bit trickier, but it can be done). A few years ago, I
had mused on the possible applications of the Conway operations to
cryptography and even designed a block cipher which uses them, see
<URL: http://www.madore.org/~david/math/consum.pdf > - but I never got
around to seriously studying its cryptanalysis.
Incidentally, just today I attended a lecture by Maxim Kontsevich at
the I.H.É.S., part of a colloquium in honor of André Weil (whose 100th
birthday is on 2006-05-06): he (Kontsevich, not Weil :-) was
discussing a possible generalization of the Weil conjectures (which,
unfortunately, I could satisfactorily explain as I took no notes), but
one interesting byproduct of his idea would be, he said, to construct
the finite fields in a canonical way. (In a nutshell, his argument
was this: he conjectures the existence of a functor Phi from some
category whose objects are schemes of finite type over F_q (and
morphisms are a little complicated to describe, so I won't even try,
but it looks remotely like motives) to another category whose objects
are finite-dimensional vector spaces over C (and again, morphisms are
rather complicated). Now the affine line A^1 is a ring object in the
former category, so its image by Phi should be an algebra, and the
Spec of that algebra should give a canonical version of F_q. Don't
ask me to explain why this should work, nor why it is canonical, nor
even how it is related to the Weil conjectures. :-)
John Baez
David Madore <david....@ens.fr> wrote:
>John Baez in litteris <e3fohq$7l0$1...@glue.ucr.edu> scripsit:
>> David Madore <david....@ens.fr> wrote:
>>>I'm not sure about whether
>>>one needs AC to show that the algebraic closure of Q constructed using
>>>the reals and the p-adics as explained above actually give the same
>>>thing.
>> I can imagine it requiring countable choice to "construct" an
>> isomorphism between two countable algebraic closures of Q.
>Actually, come to think of it, I now think any two countable algebraic
>closures of Q can be shown to be isomorphic without using any form of
>the axiom of choice, the argument being something like this: number
>the elements of both fields by natural numbers (which can be done,
>since we are assuming them to be countable), take the smallest-labeled
>element of one field, say x, consider its minimal polynomial (over Q),
>take its roots in the other field, consider the smallest-labeled among
>them, say y, and map x to y; then map Q(x) to Q(y) in the only
>possible way; then take the smallest-labeled element still not
>accounted for, and so on.
Oh, okay. The folks over at the category theory mailing list
seemed to think I was nuts for suggesting that the axiom of choice
might come into this, and now I see why: a countable set comes
equipped with an enumeration, so we don't have to make any of the
arbitrary choices I was imagining.
They also seemed to think it impossible for there to be an uncountable
algebraic closure of Q, as you had suggested. But back when I knew
something about axiomatic set theory, it seemed the whole theory of
cardinality was pretty weird without choice.
>And more or less the same argument seems to show that Countable Choice
>implies the uniqueness of the algebraic closure of Q.
Hmm, I don't understand this. Sorry.
>Incidentally, just today I attended a lecture by Maxim Kontsevich at
>the I.H.E.S., part of a colloquium in honor of Andre Weil (whose 100th
>birthday is on 2006-05-06): he (Kontsevich, not Weil :-) was
>discussing a possible generalization of the Weil conjectures (which,
>unfortunately, I could satisfactorily explain as I took no notes), but
>one interesting byproduct of his idea would be, he said, to construct
>the finite fields in a canonical way.
Interesting! Thanks!!!
tc...@lsa.umich.edu
John Baez <ba...@math.removethis.ucr.andthis.edu> wrote:
>Oh, okay. The folks over at the category theory mailing list
>seemed to think I was nuts for suggesting that the axiom of choice
>might come into this, and now I see why: a countable set comes
>equipped with an enumeration, so we don't have to make any of the
>arbitrary choices I was imagining.
Right; what you were probably vaguely remembering was that if you have
countably many countable sets, then picking an enumeration for each of
the countable sets may require countable choice.
>They also seemed to think it impossible for there to be an uncountable
>algebraic closure of Q, as you had suggested. But back when I knew
>something about axiomatic set theory, it seemed the whole theory of
>cardinality was pretty weird without choice.
That ZF doesn't prove the uniqueness (up to isomorphism) of an algebraic
closure of Q is proved in W. Hodges, "Lauchli's algebraic closure of Q,"
Math. Proc. Camb. Phil. Soc. 79 (1976), 289-297.
tc...@lsa.umich.edu
>closures of Q can be shown to be isomorphic without using any form of
>the axiom of choice, the argument being something like this: number
>the elements of both fields by natural numbers (which can be done,
>since we are assuming them to be countable), take the smallest-labeled
>element of one field, say x, consider its minimal polynomial (over Q),
>take its roots in the other field, consider the smallest-labeled among
>them, say y, and map x to y; then map Q(x) to Q(y) in the only
>possible way; then take the smallest-labeled element still not
>accounted for, and so on.
Hold on a second...this seemed to make sense to me when I first read it,
but on second reading I'm not sure I understand your construction. When
you take the "smallest-labeled element still not accounted for," are you
taking the smallest-labeled element in the first algebraic closure or
the second? If you're flipping back and forth between them, isn't this
an implicit use of Koenig's lemma or something?
David Madore
<4460ad81$0$572$b45e...@senator-bedfellow.mit.edu> scripsit:
> In article <e3glsr$2b4m$1.re...@nef.ens.fr>,
> David Madore <david....@ens.fr> wrote:
>>Actually, come to think of it, I now think any two countable algebraic
>>closures of Q can be shown to be isomorphic without using any form of
>>the axiom of choice, the argument being something like this: number
>>the elements of both fields by natural numbers (which can be done,
>>since we are assuming them to be countable), take the smallest-labeled
>>element of one field, say x, consider its minimal polynomial (over Q),
>>take its roots in the other field, consider the smallest-labeled among
>>them, say y, and map x to y; then map Q(x) to Q(y) in the only
>>possible way; then take the smallest-labeled element still not
>>accounted for, and so on.
>
> Hold on a second...this seemed to make sense to me when I first read it,
> but on second reading I'm not sure I understand your construction. When
> you take the "smallest-labeled element still not accounted for," are you
> taking the smallest-labeled element in the first algebraic closure or
> the second? If you're flipping back and forth between them, isn't this
> an implicit use of Koenig's lemma or something?
I don't think there's any reason to flip back and forth (once all
elements of one field have been exhausted, the elements of the other
also necessarily have been exhausted, since both are algebraic
closures of Q), but, even if I did, I don't think that would require
choice (e.g., Cantor's theorem that any two countable dense unbounded
totally ordered sets are isomorphic doesn't require any form of the
axiom of choice).
(Also I seem to remember that there are several subtly different
formulations of the Koenig lemma, some of which require choice and
some of which don't. So I won't argue on that count, but I'm pretty
sure my reasoning above works without choice - unless I'm mistaken and
it doesn't work at all, I mean.)