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?) > 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()) > > 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)? > 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)? > 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. > 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). > 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? > 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. > 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 = K[sqrt3], L2 = K[sqrt2] and L3 = K[sqrt6] > if they so wished. This then specifies embeddings of K into L1, L2 and > L3 that the user has themselves chosen. Again, the idea of sqrt returning a list is unsettling for me from a usability standpoint. I think sqrt(L(3))*sqrt(L(2)) == sqrt(L(6)) would be either true or false, depending on the (unpredictable but deterministic) arbitrary choices it made. If this was false, and one wanted it to be true, one could let (say) sqrt2 = sqrt(L(2), all=True) [1]. > Similarly if they did polroots(L, y^3-L(t)*y+L(4)) where t is an > element of K, it would return a list of roots of the given polynomial > expressed in terms of a generator of the Galois closure of the field > defined by the given polynomial over K. Yes, though I think the L here is redundant as it is now the basering of the polynomial, i.e. one should be able to just type ff = y^3-L(t)*y + 4; f.roots() > > What do people think of this model of doing things? > > Bill. > > On 19 Sep, 18:52, "David Roe" <[EMAIL PROTECTED]> wrote: >>>> I remember a few years ago (when working with Enrique Gonzales >>>> on some >>>> modular form programs) spending ages finding a bug in a Magma >>>> program >>>> which gave different results to an earlier Mathematica program. It >>>> turned out that we were assuming that >> >>>> sqrt(-1)*sqrt(-2)=sqrt(2) >> >>>> but Mathematica normalized sqrt(-1) = +1*I, sqrt(-2)=+sqrt(2)*I, so >>>> that multiplying them gives +sqrt(2)*I^2=-sqrt(2). >> >>>> One can always find a consistent interpretation for a single >>>> radical >>>> expression; the problems start when you try to insiste that these >>>> choices are compatible with respect to "obvious" identities such as >>>> sqrt(a*b)=sqrt(a)*sqrt(b). >> >>> Ah, now that is a very valid point. Question: Does Magma's Qbar >>> actually >>> correctly respect those obvious identities? If so, then I start >>> to see >>> the >>> value to it. >> >> It chooses randomly in a situation like that: "Care must be taken >> with the >> interpretation of the roots of a polynomial in this system. The >> roots of >> polynomials are only defined algebraically, and the user may wish to >> identify them with some particular elements of the complex field, for >> example, but one cannot assume that the system will follow the >> embedding one >> wishes. An example will demonstrate. Suppose that alpha is a root >> of x^2 - >> 2, beta is a root of x^2 - 3, and gamma is a root of x^2 - 6. Does >> gamma = >> alpha.beta or does gamma = - alpha.beta? The system will have to >> make a >> choice between the two possibilities if the situation arises, but >> the choice >> which it will make cannot be predicted beforehand. That is, even >> if we might >> like to interpret things as alpha=sqrt 2, beta=sqrt 3 and >> gamma=sqrt 6 >> (referring to the positive real roots in each case), it cannot be >> assumed >> that this will hold in the particular algebraically closed field, >> since the >> roots are only defined algebraically." (http://www.msri.org/about/ >> computing/docs/magma/html/text704.htm) >> David > > > --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
