Opened 10 years ago

Last modified 4 years ago

#11270 new enhancement

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

Reported by: was Owned by: cremona
Priority: minor Milestone: sage-6.4
Component: elliptic curves Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges


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()

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


Change History (7)

comment:1 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 7 years ago by wuthrich

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

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.

comment:3 Changed 7 years ago by jdemeyer

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

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 4 years ago by wuthrich

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, a file that I had worked on earlier. So I tried to work on one that suggest to implement your algorithm. It this ticket.

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

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.


 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')

Note: See TracTickets for help on using tickets.