Opened 8 years ago
Closed 8 years ago
#11936 closed defect (fixed)
image_type of galois_representation of EllipticCurve hangs on first call
Reported by: | dkrenn | Owned by: | cremona |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.8 |
Component: | elliptic curves | Keywords: | ellipitc curve, galois_representation, image_type, kash |
Cc: | Merged in: | sage-4.8.alpha3 | |
Authors: | Johan Bosman | Reviewers: | Daniel Krenn |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #11937 | Stopgaps: |
Description
In gal_reps.py we have
sage: EllipticCurve([1,-1,0,-107,-379]).galois_representation().image_type(7) # long time 'The image is a group of order 36.'
as doctest. I always get a timeout in a doctest with -long. I tried the command in a sage shell, but no result within one day, so I interrupted with Ctrl+C
and got the following:
^CInterrupting Kash... 'The image is a group of order 36.'
i.e., the correct result. After trying the command again, I got the result without hanging within a short time.
Attachments (1)
Change History (10)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
sage: set_verbose(2) sage: EllipticCurve([1,-1,0,-107,-379]).galois_representation().image_type(7) verbose 1 (1331: free_module.py, coordinate_module) rational in-place Gauss elimination on 0 x 0 matrix verbose 1 (1331: free_module.py, coordinate_module) done with gauss echelon form (time = 0.0) verbose 1 (1331: free_module.py, coordinate_module) rational in-place Gauss elimination on 0 x 0 matrix verbose 1 (1331: free_module.py, coordinate_module) done with gauss echelon form (time = 0.0) verbose 1 (805: gal_reps.py, image_type) the image cannot be non-split, found u=1 (time = -0.031877) verbose 1 (225: gal_reps.py, _division_field) trying to build the extension by adjoining the 7-torsion poitns (time = 0.076129) verbose 1 (170: gal_reps.py, _splitting_field) polynomial changed to X^24 - 42*X^23 - 230251*X^22 - 69533303*X^21 - 8922533774*X^20 + 347214199528*X^19 + 286338627568224*X^18 + 41629615315907472*X^17 + 3108220855196029216*X^16 + 122316792051635948928*X^15 - 4520750190750939811456*X^14 - 1804229340708484633384448*X^13 - 224151265240179594471852544*X^12 - 15517866240175312371054405632*X^11 - 573518329951131274679784851456*X^10 - 5793224956125895412494849712128*X^9 + 228526103828692771157402376626176*X^8 - 14135660323094856284334906260815872*X^7 - 2416289128770519856029858966252322816*X^6 - 131374567677496568053592598343642185728*X^5 - 4111917752635666789463237955234875572224*X^4 - 81967433407110205420237005816145633083392*X^3 - 1040145626904817944512274612355466016587776*X^2 - 7776955374441598739723910668195770718486528*X - 26550411922404424048904353608400249053773824 (time = -0.91587) verbose 1 (170: gal_reps.py, _splitting_field) degree of the field is now 6 (time = 0.100131) verbose 1 (170: gal_reps.py, _splitting_field) degree of the field is now 18 (time = 0.348146) verbose 1 (225: gal_reps.py, _division_field) the y-coordinate need to be adjoined, too (time = 3.732357) verbose 1 (805: gal_reps.py, image_type) field of degree 36. try to compute galois group (time = 4.676417)
Using trace
, it turns out that it hangs at the following position:
> /usr/opt/Sage-4.7.1-amd64/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/gal_reps.py(1159)image_type() 1158 try: -> 1159 G = K.galois_group() 1160 except:
comment:3 Changed 8 years ago by
Thanks. The reason it hangs for you and not for me is that I don't have the optional package KASH installed. For me it raises the NotImplemented
error and it passes to the except.
So this is not a problem of galois representations, but of how Galois groups are calculated, I fear. Here is the command that is called:
R.<x> = QQ[] f = x^36 + 232*x^35 - 1409590*x^34 - 208771080*x^33 + 542002034595*x^32 + 36849258927684*x^31 - 28701669009468742*x^30 - 1696654153633045980*x^29 + 733820474374957876065*x^28 + 40734331558473487809840*x^27 - 11465777486812349057484526*x^26 - 644250813449703542918356892*x^25 + 125177336158984809052605425600*x^24 + 7693565456991227136062966261700*x^23 - 1116530121510329941650665203053550*x^22 - 72071805573472538906636525663956020*x^21 + 9247213638567012639899553190096543060*x^20 + 489070230674343941519687717200037034600*x^19 - 63821424089313130077462129567772086334300*x^18 - 2076960734134142012731684732329794421249300*x^17 + 262061131595952754895901016203359127399833635*x^16 + 5147227487591445981717637850998628590176666520*x^15 - 185570840529826733080990829035096852217828321100*x^14 - 14878238968057089923405449092346290005791654017200*x^13 - 1547964860908179062293039197523670128542795694054325*x^12 + 34667825973614327709199311382710180266142624053184472*x^11 - 7770857837470021854621559660984035253823067605233925446*x^10 + 332496595306827138498694624156463235069407086237978206720*x^9 + 50515743005409091880315980155729585601028981868957828356515*x^8 - 1488439010064063165131003688799387682254808807901674208959260*x^7 + 11989258410297219585803474836805748253128362834002738889049838*x^6 + 11756542465546263464703460049021530422982958442853357231814356*x^5 + 113628831616635393026353283720453609974562180685019518331117688690*x^4 - 1493996526282733423722228420360775582764552584088512647233847040320*x^3 + 26598660230348604947516388314265739137380307179828340819884014361980*x^2 - 201214061751046506338009477533304151375139639284039242526562543549292*x + 40745133036885593180393722044782759619921619610745354128620011908847961 K.<t> = NumberField(f) K.galois_group()
I won't be able to chase if this is a problem in KASH or if the computation is just extremely difficult with KASH. Magma gives me the answer
Permutation group acting on a set of cardinality 36 Order = 36 = 2^2 * 3^2 (1, 3, 14, 19, 21, 32)(2, 4, 13, 20, 22, 31)(5, 15, 35, 23, 34, 17)(6, 16, 36, 24, 33, 18)(7, 10, 11, 26, 27, 30)(8, 9, 12, 25, 28, 29) (1, 17, 9, 2, 18, 10)(3, 31, 12, 7, 6, 34)(4, 32, 11, 8, 5, 33)(13, 29, 26, 24, 15, 21)(14, 30, 25, 23, 16, 22)(19, 35, 28, 20, 36, 27) ...
relatively quickly.
If it is a bug somewhere else it has to be fixed there. If instead the computation is not feasable when having KASH installed, then we best take this example out of the testing.
comment:5 Changed 8 years ago by
- Milestone set to sage-4.8
comment:6 Changed 8 years ago by
Let us look at the source code:
1158 try: 1159 G = K.galois_group() 1160 except: 1161 self.__image_type[p] = "The image is a group of order %s."%d 1162 return self.__image_type[p] 1163 1164 else: 1165 if G.is_abelian(): 1166 ab = "" 1167 else: 1168 ab = "non-" 1169 self.__image_type[p] = "The image is a " + ab + "abelian group of order %s."%G.order() 1170 return self.__image_type[p]
The only thing that the Galois group computation using Kash adds is checking whether the group is Abelian or not. I've tried this example with Kash installed. It seems that the Kash process runs very briefly and then crashes or so (?); in any case, Sage keeps waiting for a result that it will never get. Magma supports Galois group computation for irreducible polynomials of any degree over Q using an implementation of Claus Fieker and Juergen Klueners; I guess Kash only goes up to a certain degree. In any case, there's something wrong with Sage's interface to Kash.
Changed 8 years ago by
comment:7 Changed 8 years ago by
- Status changed from new to needs_review
Kash does not support Galois group computations if the degree is larger than 23. I've attached a patch that avoids this.
comment:8 Changed 8 years ago by
- Dependencies set to #11937
- Reviewers set to Daniel Krenn
- Status changed from needs_review to positive_review
Added the dependency #11937 to pass doctest.
comment:9 Changed 8 years ago by
- Merged in set to sage-4.8.alpha3
- Resolution set to fixed
- Status changed from positive_review to closed
I cannot reproduce this. Could you run it with set_verbose at least 2 to see where it hangs ? I don't know which line uses KASH...