On 20 Sep, 06:39, Robert Bradshaw <[EMAIL PROTECTED]>
wrote:
> On Sep 19, 2007, at 9:20 PM, Bill Hart wrote:
>
> > My personal opinion is that SAGE should distinguish between an abstact
> > number field and an embedded number field right from the start.
>
> I agree, and like David Harvey's suggestion of how to handle this.
>
>
>
> > An abstract number field should be basically a number field defined by
> > a polynomial with no embedding specified. If you like, it can be
> > thought of as David Harvey suggested, as a number field embedded into
> > itself, i.e. any function which relies on an embedding should map the
> > generator x, say, of the field, to itself, not an element of the
> > complex numbers, or any other field. The number field then exists as
> > an abstract field apart from any embedding into C, Omega or any other
> > field you might like to embed it into. And this enables you to embed
> > the field into a variety of other fields, not just C.
>
> > Here is how such a system would work (let's restrict for now to
> > absolute extensions of Q, though it is possible to have any abstract
> > number field as the base field with some not too technical
> > modifications of the following):
>
> > 1) A number field K would be defined by a monic polynomial f(x) \in
> > Q[x] for some `symbol' x. The symbol x would stand for an
> > *unspecified* root of f, thought of as the generator of K/Q.
>
> Is the requirement that f be monic too strong (or could we just
> normalize behind the scene perhaps?)
Could do.
>
>
>
> > 2) An element of K should be specified as an explicit polynomial
> > expression in the nome x with coefficients in Q. In fact it is really
> > an element of Q[x]/f(x), but any representative will do to specify the
> > element of K uniquely. To test equality of two elements g1 and g2 of
> > K, specified as polynomials in Q[x], one then simply reduces them mod
> > f to see if they are the same. Since f is monic, this should be well
> > defined.
>
> > 3) One may specify an element of K as a *root* of a polynomial s(y)
> > iff precisely one root of s lies in K=Q[x]. Internally the system
> > would represent this element as a polynomial expression in x, uniquely
> > identifying the element as an element of K. If more than one root of s
> > lies in K then a function should exist to find all the roots of s *as
> > elements of K*, i.e. it should give explicit polynomial expressions in
> > x for all the roots of s that lie in K. This would enable one to
> > specify an element of K as a specific root of s. Basically I think
> > that function should have the syntax polroots(K, f) where K is the
> > field and f is the polynomial. If none of the roots of f are in K,
> > this should return an empty list. polroots should return a list of the
> > roots of K as polynomial expression in the generator x of K.
>
> Personally, I like the notation f.roots(K), where f.roots() == f.roots
> (f.base_ring())
Yes, some of my notation is a bit unintuitive. It's the general idea
that I'm presenting here which is suppose to be worth something.
>
>
>
> > 4) One may specify an element of K as an expression involving radicals
> > iff this uniquely identifies an element of K. E.g. if we are in the
> > field defined by the polynomial x^3-3 then 3^(1/3) would simply be a
> > synonym for x. Again the system will represent this element internally
> > as a polynomial expression in x. If an expression involves radicals of
> > objects which are actually coerced to be elements of K then the
> > expression should return a list of all the possible elements of K the
> > expression could represent (expressed as polynomials in x). If no such
> > expression exists in K, the list should be empty.
>
> Things that sometimes return lists, and sometimes not, are messy to
> deal with. Especially if I write something like a^(1/3)+1 and the
> first part returns a list... sqrt has an optional parameter
> 'all' (which is false by default) that does this (though not very
> consistently). It also has an 'extend' parameter (by default true)
> which will give the result in an extension if one doesn't exist in
> the current field (though making an arbitrary choice). Is this the
> kind of stuff you are looking for (though in much more generality)?
Yeah perhaps radicals should just be meaningless unless you have a
number field embedded in C, in which case they should just return the
root with the least argument.
>
> > 5) A function should exist to determine if a given element of K is a
> > root of a given polynomial. Similarly a function should exist to
> > determine if two elements of K are conjugate.
>
> > 6) In the case that K is Galois, one ought to be able to compute the
> > Galois group of K. This should be represented by the group of elements
> > of K Galois conjugate to x. To apply a Galois automorphism sigma
> > (represented as an element of Q[x]/f) to an element g (represented by
> > a polynomial in x, thought of as an element of Q[x]/f) of K, one
> > simply takes g(sigma(x))/f, i.e. if g is the polynomial representing
> > the element g of K that one is applying sigma to, and sigma(x) is the
> > polynomial representing the application of the Galois automorphism
> > sigma to the generator x of K, then one simply composes the
> > polynomials g and sigma(x) and then reduces modulo f to get the
> > element sigma(g) of K.
>
> Perhaps I'm showing my naivety here, but I thought computing Galois
> groups was a hard problem in general. Aren't the Galois conjugates of
> x the other roots of f, and if so (by the pigeonhole principle) I
> don't see how they would be enough to identify elements of Gal(K/Q)?
If K is Galois then all the roots of the min poly of the generator are
in the field. That means by definition that they have an expression as
polynomials in the generator.
As for there being more elements in the Galois group of a polynomial
than there are roots of the polynomial, I agree that this can happen
in general. In general an element of the Galois group of a polynomial
has to be represented by its action on *all* of the roots of the
polynomial.
But isn't it the case that if the field is Galois then since the
Galois automorphisms are precisely that - automorphisms - that their
action on the field is fully characterised by their action on a
generator of the field, which because of the fact that the field is
Galois, must be other elements of the field (specifically other roots
of the defining polynomial as you noted). Doesn't this then give a
proof that the automorphisms of a Galois field can be represented by
their action on the generator of the field, i.e. there aren't too many
of them.
>
> > 7) If K is not Galois, one ought to be able to define the Galois
> > closure of K. This would be represented by a polynomial in another
> > symbol y, say. One should then be able to specify an embedding of K
> > into its Galois closure and x would be given an expression in terms of
> > y, i.e. be represented as a polynomial expression in terms of y. This
> > would allow one to refer to the conjugates of x, which now have
> > expressions in terms of y.
>
> Makes sense.
Well, I *think* it makes sense. But only over Q.
>
> > Note how everything above can be done completely in terms of
> > polynomial arithmetic.
>
> This is good :-). For efficiency, I'm assuming extensions of a number
> field would be (hopefully transparently) implemented as absolute
> extensions of Q. We could do this with generic polynomials as well
> (where it makes sense).
I think so. But it becomes slightly harder. So long as you are talking
about Galois extensions everything probably works. I think you can
still define the Galois closure of a field L over a field K. But it
has been a while for me....
>
>
>
> > Of course as soon as one supplies an embedding of K into another field
> > (be it another number field, its Galois closure, the complex numbers
> > or your favourite algebraically closed field) elements of K will have
> > expressions in terms of elements of that other field, e.g. if K is
> > embedded in C, elements can be referred to by their embeddings into
> > the complex numbers (when suitably coerced).
>
> > The idea of forcing expressions involving radicals to default to the
> > root with least argument seems OK to me. So:
>
> > QQ[3^(1/3)], QQ[sqrt(1+i)], QQ[sqrt(2), sqrt(3)], etc would all make
> > sense. This would be implemented as an abstract number field with a
> > specified embedding. Note that if one has implemented abstract number
> > fields first, this becomes easier since each of the generators will
> > have an expression in terms of a single generator for the field, which
> > will be computed entirely with polynomials.
>
> > To define an abstract number field, something like K =
> > number_field(QQ, x^3-3*x^2+1) could work. Eventually one will want to
> > be able to do adjoin(K, y^5+7*y-1), compositum(L, M), etc.
>
> Would/could these functions return lists too, if, say, the
> intersection of L and M was not Q?
Yeah, I haven't really thought through what these would actually
return. Moreover, I haven't thought up an algorithm to compute these
things either. Lists are one possibility. The other option would be to
only make them make sense under certain circumstances.
>
> > To embed an abstract number field into CC, something like embed(K,
> > polroots(CC, K.pol)[1]) could work. This would simply assign to the
> > generator x of K, the specified explicit complex root of the defining
> > polynomial of K. But I see no reason why embed(K,
> > polroots(galois_closure(K), K.pol)[1]) shouldn't also work, etc.
>
> > One could also implement something like Allan Steel's algebraic
> > closure as well. That seems reasonable and important though it becomes
> > slightly complicated. The algebraic closure just gets implemented as
> > an abstract algebraic field containing all the fields and elements one
> > has defined over K so far with randomly chosen embeddings of those
> > things into the algebraic closure. This is still possible in the
> > abstract setting, though slightly complicated.
>
> Carl Witty did an implementation of the Algebraic Reals by letting
> every element be specified by a polynomial and an interval containing
> a single root. I've been wondering if the same approach could be
> feasible for Qbar, the main difficulty being that the product of two
> balls in C is not a ball (though it is close for small enough
> epsilon). This might be much faster, for instance proving inequality
> is done by numerical verification (with adaptive root refinement) and
> if that fails it falls back to trying to deduce equality algebraically.
>
I'm not sure. Assuming you have a representation of the two elements
you want in terms of the generator of the big superfield you have
constructed, determining whether two elements are equal is trivial.
But of course it only works in characteristic zero.
> > For example, one could do:
>
> > K = number_field(QQ, x^3+3*x+1)
> > L = algebraic_closure(K)
> > s = x+1
> > t = L(sqrt(x+1)[1])
>
> > At this point SAGE would internally compute the abstract field (lets
> > call it K1) defined as a relative extension of K defined by y^2 = x +
> > 1 with a randomly chosen embedding of K into K1. Now there is no
> > generator that one can give for L so one cannot refer to the two
> > square roots of x+1 in terms of elements of L, but there is a
> > generator one can give for the Galois closure of K1. So basically
> > sqrt(x+1) would return a two coordinate vector of polynomials
> > representing the two roots of x+1 in the Galois closure of K1. By
> > setting t to one of these roots, one is fixing which root of x+1 that
> > one is referring to.
>
> > If this is how things were implemented then sqrt(L(3))*sqrt(L(2)) ==
> > sqrt(L(6)) has no meaning. But sqrt(L(3))[1]*sqrt(L(2))[2] ==
> > sqrt(L(6))[1] has a meaning. Of course internally SAGE is just
> > constructing a field which contains all the Galois closures of all the
> > fields one is constructing, with randomly chosen embeddings. But as
> > far as the user is concerned, they are still able to choose which
> > embedding they want.
>
> > So if they test sqrt(L(3))[1]*sqrt(L(2))[2] == sqrt(L(6))[1] and it is
> > false, and they want it to be true, they would simply set sqrt3 =
> > sqrt(L(3))[1]; sqrt2 = sqrt(L(2))[2]; sqrt6 = sqrt(L(6))[2] and it
> > will be true that sqrt3*sqrt2 = sqrt6 as they desire. At this point
> > they could specify that L1
Bill.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
