[FOM] Algebraic closure of Q

[joeshipman@aol.com]

We have been discussing how much choice is needed to prove the 
existence and uniqueness of the algebraic closure of Q. But from a 
constructive point of view, what matters is that we have a way to 
enumerate this field and compute the field operations.

(Even if some choice is required to prove that the construction has 
certain properties, the construction itself is just a set of algorithms 
to enumerate elements of Qbar and calculate the field operations.)

What I would like to know is how "nice" such a construction can be.  
The one I am thinking of represents algebraic numbers by their 
irreducible polynomials over Z, distinguishing between conjugates using 
the lexicographic ordering (the "first root" is the one which has the 
smallest imaginary part among those roots with the smallest real part, 
etc.).  The algebra is messy and painful to implement, but 
straightforward.

But much nicer representations exist for other fields. For example, 
Conway has found natural and nicely computable operations on ordinals, 
"nim-addition" and "nim-multiplication", under which the ordinal 
omega^(omega^omega) is the algebraic closure of the field 2={0,1}. 
Explicit constructions for the algebraic closure of other finite fields 
have been given by Brawley and Schnibben (though finding a construction 
for each characteristic that is as "canonical" as Conway's remains 
open).

The reason these representations are "nicer" is that the representation 
of the elements is straightforward -- it is immediately obvious whether 
a particular term in the notation system represents a field element, 
and notations are unique, so that it is easy to calculate an 
enumeration (given n, we can quickly write down the element of the 
field; this is especially easy in characteristic 2, because Conway's 
construction means one merely has to enumerate omega^(omega^omega) ).

In the representation of algebraic numbers I describe above, it is easy 
to recognize that you have a pair (integer polynomial of degree n, 
integer in {1,...,n}), but it is not easy to confirm that such a 
notation actually represents a field element, because the polynomial 
must be tested for irreducibility. (Also, notations are not unique, but 
that's easier to fix, because we can require that the polynomial have 
no common factor for the coefficients and positive leading term, which 
are easily checked.)

This means that any conversion of the representation to an enumeration 
will be really slow (to find the nth algebraic number you have to 
enumerate polynomials and sieve out the reducible ones, unless there is 
a way of enumerating irreducible polynomials only that I don't know 
about).

Another field I'd like to see a much better representation for is the 
"p-adic algebraic numbers" -- given p, this is the smallest field 
elementarily equivalent to the p-adics. Although the best known 
algorithm for the first-order theory of the p-adic numbers is 
non-elementary, the p-adic algebraics ought to have a reasonable 
representation since it is much easier than that to decide which 
polynomials have roots in the p-adics (though I don't know precisely 
how easy). Once you have irreducible polynomials for algebraic p-adic 
numbers (plus a "which root" flag), the computation of the field 
operations is even easier than it is for the ordinary algebraic numbers 
viewed as a subfield of the complex numbers.

(Whether there is a nice operation-preserving mapping from the p-adic 
algebraics into the ordinary algebraics seems a much more difficult 
problem -- it's easy to find conjugates, but hard to consistently 
select one of them.)

-- JS
________________________________________________________________________
Check out AOL.com today. Breaking news, video search, pictures, email 
and IM. All on demand. Always Free.