Implement David Zywina's new fast algorithm for determining surjectivity of Galois representations attached to elliptic curves

[williamstein]

This paper [1] has a much faster more precise algorithm than the one in Sage for accomplishing the following sort of thing:

sage: E = EllipticCurve('147b1')
sage: E.galois_representation().non_surjective()
[13]

The point of this ticket is to get this into Sage as the default algorithm (while keeping the old one, of course). I (William Stein) am working with Zywina on this (it is a little more involved than just copying things from his paper...)

[1] http://www.math.upenn.edu/~zywina/papers/EffectiveModl.pdf

Component: elliptic curves

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

[chriswuthrich]

comment:2

I tried to do this, but I ran into an inconsistency. I copied the first code of Zywina taken from

http://www.mast.queensu.ca/~zywina/papers/code/EffectiveModl.py

where for small primes, he uses explicit polynomials as criterions for non-surjectivity. When I did so, there were doctest failures that show that his program does not give the same answer as our sage implementation. I have checked in details these three cases and I found that our result is correct and his wrong. I contact him about this.

So until further notice, this is a ticket that we should NOT do.

[jdemeyer]

comment:3

In case you decide to continue working on Galois representations, please be so kind to wait for #11905 first.

[chriswuthrich]

comment:7

The situation of this ticket is still the same. I have sent (dec 13) the following email to David Zywina. He once replied (sep 14) that he did not have time to look at it now but he would do so later. I have not heard from him since.

---

Dear David,

I had some time and I decided to look at old trac tickets for sage. I
came acrose a few mentioning bugs and improvements to gal_rep.py, a
file that I had worked on earlier. So I tried to work on one that
suggest to implement your algorithm. It this ticket.

#11270

I started to do so, but then ran into a problem. I wanted first to
include into the function is_surjective(p) the criteria for small
primes that you have in your file

http://www.mast.queensu.ca/~zywina/papers/code/EffectiveModl.py

That concerns the primes 5,7,11,13,17,37 (as 2 and 3 are already
implemented). However, with your aglorithm I get a different result
than with the current implementation for some cases. I list three
below. I then did by hand find the splitting field of the p-division
polynomial and looked at its degree. I concluded that the current
implementation in sage is correct. Also the approximated distribution
of Frobenius in conjugacy classes in PGL_2 suggests that our answer is
right.

But to be honest. This file is a mess and I would not be surprised if
some of our results are wrong. Hence I don't mean to say that I am
right and your implementation is wrong, but certainly that there is
someting to look at which may be of interest to you.

I wish you a Happy New Year.

Chris.

---

 EllipticCurve([0,0,0,-56,4848]) at p=5

sage: 'The image is contained in the normalizer of a split Cartan group.'
zwyina: (False, 'S4')

---

    EllipticCurve([0,0,1,-25650,1570826]) at p=5

 sage:   'The image is contained in the normalizer of a split Cartan group.'
 zywina:  (False, 'Non-split')

---

   EllipticCurve([0,0,1,2580,549326]) at p=7

sage:    'The image is contained in the normalizer of a split Cartan group.'
zywina :  (True, 'None')

---