image_type of galois_representation of EllipticCurve hangs on first call

[dkrenn]

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.

Depends on #11937

Component: elliptic curves

Keywords: ellipitc curve, galois_representation, image_type, kash

Author: Johan Bosman

Reviewer: Daniel Krenn

Merged: sage-4.8.alpha3

Issue created by migration from https://trac.sagemath.org/ticket/11936

[chriswuthrich]

comment:1

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

[dkrenn]

comment:2

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:

[chriswuthrich]

comment:3

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.

[jdemeyer]

Milestone sage-4.7.3 deleted

[1659f18b-8e7f-4ace-87e0-ea435f3ce618]

comment:6

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.

[1659f18b-8e7f-4ace-87e0-ea435f3ce618]

comment:7

Attachment: 11936.patch.gz

Kash does not support Galois group computations if the degree is larger than 23. I've attached a patch that avoids this.

[1659f18b-8e7f-4ace-87e0-ea435f3ce618]

Author: Johan Bosman

[dkrenn]

comment:8

Added the dependency #11937 to pass doctest.

[dkrenn]

Dependencies: #11937

[dkrenn]

Reviewer: Daniel Krenn

[jdemeyer]

Merged: sage-4.8.alpha3