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)

11936.patch (1.7 KB) - added by johanbosman 8 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 8 years ago by wuthrich

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...

comment:2 Changed 8 years ago by dkrenn

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 wuthrich

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:4 Changed 8 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:5 Changed 8 years ago by dkrenn

  • Milestone set to sage-4.8

comment:6 Changed 8 years ago by johanbosman

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 johanbosman

comment:7 Changed 8 years ago by johanbosman

  • Authors set to Johan Bosman
  • 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 dkrenn

  • 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 jdemeyer

  • Merged in set to sage-4.8.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.