On Sep 19, 2007, at 11:39 PM, Bill Hart wrote: > On 20 Sep, 06:39, Robert Bradshaw <[EMAIL PROTECTED]> > wrote: >> 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.
Yes, and I think the idea is down the right road (though I have to admit I don't have the experience using these things compared to lots of people on this list). >>> 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. I think it should give something, but the choice might be arbitrary, and one would be able to make the choice manually if one wanted. >>> 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. Yeah, I realized shortly after I posted that if Q[x]/f is Galois, then f has exactly as many elements as |Gal(K/Q)| and since the group is is transitive, so the Galois conjugates of one root of f are exactly enough to specify an element. For some reason the picture I had in my head was f being a (generic) polynomial whose closure was K and looking at the permutation of a root of f, which of course doesn't work in general. > >> >>> 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. I got the impression that using numerical approximations made things vastly faster (e.g. one would only lazily have to compute radicals and polynomials--though I should take a closer look at his code to be sure). I guess in this case trivial != efficient. - Robert --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
