Opened 11 years ago

Closed 11 years ago

# image_type of galois_representation of EllipticCurve hangs on first call

Reported by: Owned by: dkrenn cremona minor sage-4.8 elliptic curves ellipitc curve, galois_representation, image_type, kash sage-4.8.alpha3 Johan Bosman Daniel Krenn N/A #11937

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

### comment:1 Changed 11 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 11 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 11 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 11 years ago by jdemeyer

• Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

### comment:5 Changed 11 years ago by dkrenn

• Milestone set to sage-4.8

### comment:6 Changed 11 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.

### comment:7 Changed 11 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 11 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 11 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.