Closed arminstraub closed 13 years ago
This fails because the present definition for relative number fields:
def is_galois_relative(self):
return self.Hom(self).order() == self.relative_degree()
is completely wrong. In the case above
sage: L.Hom(L).order()
6
while the relative degree is 3. Clearly the Homset contains all endomorphisms of of L, not just the relative ones. One obvious possibility would be to count those endomorphisms which fix the base field. But the following might be better
def is_galois_relative(self):
rel_poly = self.relative_polynomial()
return len(rel_poly.base_extend(self).factor()) == self.relative_degree()
I'll do some testing and post a patch later today.
After a rather longer than expected delay, I'm attaching a patch which gives correct results for is_galois_relative
. I've also rewritten is_galois_absolute
using a corresponding algorithm because it is (i) faster than the existing code, and (ii) capable of handling extension of larger degree.
Attachment: trac_9390.patch.gz
Nice, that is a lot faster, and correct. There is one thing I don't like though: you introduced a difference between is_galois
of absolute number fields and is_galois_absolute
of relative number fields:
With your patch on Sage 4.6.1.alpha2:
sage: M.<c> = NumberField(cyclotomic_polynomial(100))
sage: M
Number Field in c with defining polynomial x^40 - x^30 + x^20 - x^10 + 1
sage: M.is_galois()
NotImplementedError
sage: M.relativize(1, 'd').is_galois_absolute()
True
sage: M.relativize(1, 'd').is_galois_relative()
True
Without your patch, it is NotImplementedError, NotImplementedError, False, so your patch is a definite improvement, but could be better.
I think it would be better to put your new code in is_galois
of absolute fields instead of is_galois_absolute
of relative fields. Then is_galois_absolute()
can simply call self.absolute_field().is_galois()
PS grammar: line 1177 of number_field_rel.py after the patch, previous should be previously (or simply replace the line by "Check that bug #9390 is fixed::")
Author: Francis Clarke
Reviewer: Marco Streng
Replying to @mstreng:
I think it would be better to put your new code in
is_galois
of absolute fields instead ofis_galois_absolute
of relative fields. Thenis_galois_absolute()
can simply callself.absolute_field().is_galois()
I've done this in a new replacement patch, and dealt with the grammatical point you raised.
It was also necessary to make a minor change to an unconnected doctest. This is because of PARI's inconsistent behaviour when choosing ideal generators. The same issue arose in #5842.
Attachment: trac_9390-replacement.patch.gz
Replaces previous patch
On which Sage version is this a speedup for is_galois_absolute?
With Sage 4.6.1.alpha2 and no patches
sage: K.<a>=NumberField(x^2+1)
sage: Kt.<t> = K[]
sage: L.<b> = K.extension(t^3-3*t-1)
sage: M.<c> = L.absolute_field()
sage: time L.is_galois_absolute()
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.00 s
True
sage: time L.is_galois_relative()
CPU times: user 0.08 s, sys: 0.00 s, total: 0.08 s
Wall time: 0.08 s
False
sage: time M.is_galois()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
True
Same version, but with your patch:
sage: K.<a>=NumberField(x^2+1)
sage: Kt.<t> = K[]
sage: L.<b> = K.extension(t^3-3*t-1)
sage: M.<c> = L.absolute_field()
sage: time L.is_galois_absolute()
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.04 s
True
sage: time L.is_galois_relative()
CPU times: user 0.04 s, sys: 0.01 s, total: 0.05 s
Wall time: 0.05 s
True
sage: time M.is_galois()
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
True
So you did correct (and apparently speed up) is_galois_relative. However, it seems to slow down is_galois and is_galois_absolute. This gets worse if you use is_galois multiple times for the same field, as the old version uses cached data and your version doesn't:
Without patch:
sage: K.<b> = NumberField(cyclotomic_polynomial(11))
sage: time K.is_galois()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
True
sage: time [K.is_galois() for i in range(500)];
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
With patch:
sage: K.<b> = NumberField(cyclotomic_polynomial(11))
sage: time K.is_galois()
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.06 s
True
sage: time [K.is_galois() for i in range(500)];
CPU times: user 11.66 s, sys: 0.05 s, total: 11.71 s
Wall time: 11.72 s
I'm very sorry for not noticing this earlier and for letting you do make the changes you did after my first review.
On the other hand, my suggestion allowed for a good test of your code, as is_galois is ubiquitous:
sage -t -long devel/sage/sage/schemes/elliptic_curves/gal_reps.py
*** *** Error: TIMED OUT! PROCESS KILLED! *** ***
Maybe it is better to stick with the is_galois_relative correction only.
Also, if you know about cached methods, then perhaps you could make is_galois_relative and is_galois_absolute cached while you're at it.
You can also make a distinction in is_galois between degree <= 11 (use the old method) and degree > 11 (old method only works if KASH is installed, use your method).
I suppose it is good to still let is_galois_absolute() simply call absolute_field().is_galois().
Replying to @mstreng:
On which Sage version is this a speedup for is_galois_absolute? ...
I'm sorry about this. I don't know how I convinced myself that the absolute version was faster.
On the other hand, my suggestion allowed for a good test of your code, as is_galois is ubiquitous:
sage -t -long devel/sage/sage/schemes/elliptic_curves/gal_reps.py
*** *** Error: TIMED OUT! PROCESS KILLED! *** ***
I can't reproduce this. Actually is_galois
is not particularly ubiquitous (and certainly does figure in gal_reps.py
):
sage -grep -l is_galois
----------------------------------------------------------------------
| Sage Version 4.6, Release Date: 2010-10-30 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
coding/linear_code.py
rings/number_field/galois_group.py
rings/number_field/number_field.py
rings/number_field/number_field_rel.py
rings/number_field/totallyreal_rel.py
rings/padics/unramified_extension_generic.py
rings/number_field/number_field_element.pyx
Maybe it is better to stick with the is_galois_relative correction only. Also, if you know about cached methods, then perhaps you could make is_galois_relative and is_galois_absolute cached while you're at it. You can also make a distinction in is_galois between degree <= 11 (use the old method) and degree > 11 (old method only works if KASH is installed, use your method). I suppose it is good to still let is_galois_absolute() simply call absolute_field().is_galois().
The new patch implements this, except it doesn't do any caching. is_galois_absolute
is already cached in the degree <= 11 cases via self.absolute_field()
. In the other cases, I think what really needs caching is the factorisation of the defining polynomial over self,
since it's also what's needed to compute endomorphisms. But that is for another patch, I think.
Replaces previous two patches
Attachment: trac_9390-2nd_replacement.patch.gz
Replying to @sagetrac-fwclarke:
I can't reproduce this. Actually
is_galois
is not particularly ubiquitous (and certainly does figure ingal_reps.py
):
How could you be so sure about that? The timeout is caused by the long test EllipticCurve([1,-1,0,-107,-379]).galois_representation().image_type(7)
The image_type() part runs forever on 4.6.1.alpha2 with your second patch, and is quite fast without any patches. That method is a long piece of code, so I didn't read it all, but it does suggest that it uses is_galois somewhere via another function.
Replying to @mstreng:
I can't reproduce this. Actually
is_galois
is not particularly ubiquitous (and certainly does figure ingal_reps.py
):How could you be so sure about that?
My mistake was that I was using 4.6. The long test in question was introduced in #8451 which was merged in sage-4.6.1.alpha2. I haven't checked it fully, but it looks like in this case the function image_type
calls galois_group
, which calls is_galois
. It seem that is_galois
is much more ubiquitous that I thought as it's used in several functions of the classes GaloisGroup_v2
and GaloisGroupElement
. Sorry for not noticing this before.
Strange: I remove all patches, build, and the long gal_reps.py test is fine, then I apply your latest patch, build, and it times out again after 1800 seconds.
The only thing I could think of is that (somewhere in a function called by EllipticCurve([1,-1,0,-107,-379]).galois_representation().image_type(7)
) an Error of is_galois with degree > 11 is raised and handled in some way. With your patch, that computation will just go on and on.
Or there is something wrong with my sage installation. Can anyone reproduce this increase in test time? (4.6.1.alpha2 with no other patches applied)
For buildbot:
Apply trac_9390-2nd_replacement.patch
Replying to @mstreng:
The only thing I could think of is that (somewhere in a function called by
EllipticCurve([1,-1,0,-107,-379]).galois_representation().image_type(7)
) an Error of is_galois with degree > 11 is raised and handled in some way. With your patch, that computation will just go on and on.
Same problem with a fresh install.
Actually, something fishy happens in image_type(7). Without your patch, it outputs 'The image is a group of order 36.'
quickly. With your patch, it goes on and on, until I press Ctrl+C, in which case it catches my KeyboardInterrupt and outputs 'The image is a group of order 36.'
without showing me any Error! So image_type catches all errors, which is why it stops working with your improvement.
Sorry, but that means this patch can't go in the way it is: either fix gal_reps or don't touch is_galois.
With the #8451 patch, and with is_galois
unchanged, I find
sage: set_verbose(1)
sage: EllipticCurve([1, -1, 0, -107, -379]).galois_representation().image_type(7)
verbose 1 (1326: free_module.py, coordinate_module) rational in-place Gauss elimination on 0 x 0 matrix
...
verbose 1 (811: gal_reps.py, image_type) field of degree 36. try to compute galois group (time = 14.321421)
'The image is a group of order 36.'
deriving from the following lines in gal_reps.py
(as patched by #8451):
if p <= 13:
K = _division_field(self.E,p)
d = K.absolute_degree()
misc.verbose("field of degree %s. try to compute galois group"%(d),2)
try:
G = K.galois_group()
except:
self.__image_type[p] = "The image is a group of order %s."%d
return self.__image_type[p]
So what's happening is that K.is_galois()
(called via K.galois_group()
) is taking ages when my patch is implemented. The unqualified except:
is then catching the keyboard interrupt. But with the existing implementation of is_galois
applied to the degree 36 field in question, a NotImplementedError
is raised and caught.
Anyway, as you suggest, the way forward is a minimal patch which only changes is_galois_relative
. I'm attaching this.
Attachment: trac_9390-3rd_replacement.patch.gz
Replaces previous three patches
Too bad about the improvements to is_galois. I suppose that code from trac_9390-2nd_replacement.patch can go into a new ticket, if someone wants to revise image_type.
Apply trac_9390-3rd_replacement.patch
Merged: sage-4.6.2.alpha1
In 4.4.4 the following code produces a number field which is Galois over the rationals but (allegedly) not over an intermediate field.
CC: @sagetrac-cturner @mstreng
Component: number fields
Keywords: galois extension
Author: Francis Clarke
Reviewer: Marco Streng
Merged: sage-4.6.2.alpha1
Issue created by migration from https://trac.sagemath.org/ticket/9390