Opened 12 years ago
Closed 12 years ago
#9390 closed defect (fixed)
is_galois_relative() not always right
Reported by: | arminstraub | Owned by: | davidloeffler |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.2 |
Component: | number fields | Keywords: | galois extension |
Cc: | cturner, mstreng | Merged in: | sage-4.6.2.alpha1 |
Authors: | Francis Clarke | Reviewers: | Marco Streng |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
In 4.4.4 the following code produces a number field which is Galois over the rationals but (allegedly) not over an intermediate field.
sage: K.<a>=NumberField(x^2+1) sage: Kt.<t> = K[] sage: L.<b> = K.extension(t^3-3*t-1) sage: L.is_galois_absolute() True sage: L.is_galois_relative() False
Attachments (4)
Change History (19)
comment:1 Changed 12 years ago by
comment:2 Changed 12 years ago by
- Cc mstreng added
comment:3 Changed 12 years ago by
- Status changed from new to needs_review
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.
Changed 12 years ago by
comment:4 follow-up: ↓ 5 Changed 12 years ago by
- Milestone set to sage-4.6.1
- Reviewers set to Marco Streng
- Status changed from needs_review to needs_work
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::")
comment:5 in reply to: ↑ 4 Changed 12 years ago by
- Status changed from needs_work to needs_review
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.
comment:6 follow-up: ↓ 7 Changed 12 years ago by
- Status changed from needs_review to needs_work
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().
comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 12 years ago by
- Status changed from needs_work to needs_review
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.
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 12 years ago by
Replying to 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.
comment:9 in reply to: ↑ 8 Changed 12 years ago by
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.
comment:10 follow-up: ↓ 11 Changed 12 years ago by
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
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 12 years ago by
- Status changed from needs_review to needs_work
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.
comment:12 in reply to: ↑ 11 Changed 12 years ago by
- Status changed from needs_work to needs_review
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.
comment:13 Changed 12 years ago by
- Status changed from needs_review to positive_review
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
comment:14 Changed 12 years ago by
- Milestone changed from sage-4.6.1 to sage-4.6.2
comment:15 Changed 12 years ago by
- Merged in set to sage-4.6.2.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
This fails because the present definition for relative number fields:
is completely wrong. In the case above
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
I'll do some testing and post a patch later today.