Opened 12 years ago
Closed 9 years ago
#11271 closed defect (fixed)
there is a serious bug in the documentation or code for is_surjective for Galois representations attached to elliptic curves
Reported by:  William Stein  Owned by:  John Cremona 

Priority:  critical  Milestone:  sage6.1 
Component:  elliptic curves  Keywords:  
Cc:  Merged in:  
Authors:  Chris Wuthrich  Reviewers:  John Cremona 
Report Upstream:  N/A  Work issues:  
Branch:  u/wuthrich/ticket/11271 (Commits, GitHub, GitLab)  Commit:  4c57ec058d7033b233b60b35993fb1e55d6982d1 
Dependencies:  Stopgaps: 
Description
David Zywina pointed out to me that the docstring for the Sage function clearly states: "Return True if the modp representation is surjective onto Aut(E[p])=GL2(Fp). False if it is not, or None if we were unable to determine whether it is or not." So according to the docstring, if the functions returns either True or False, then it returns the right answer. The documentations suggests that if the function returns None (which is completely different than True/False? in Python), then you have to recall it with a bigger parameter. That said, I just looked through the actual source code, and this simply isn't true at all!
sage: E = EllipticCurve('147b1') sage: rho = E.galois_representation() sage: rho._is_surjective?? ... while ell < A: ell = arith.next_prime(ell) if Np % ell != 0: ... return False #, signs
That "return False" at the end should be "return None" according to the docstring. So this is a serious bug in the Sage documentation or in the function. The options for a fix are:
 Probably the function as is can never ever prove nonsurjectivity, except in various special cases. It should be changed to a better one that can prove nonsurjectivity maybe following [1], or at least using division polynomials (since p<=37 anyways).
 Change the lying docstring a lot to agree with the code. NOTE: One should probably also change the docstring for the deprecated "E.is_surjective()" which is also misleading.
[1] http://www.math.upenn.edu/~zywina/papers/EffectiveModl.pdf
I could imagine doing 2 above quickly, then opening another ticket for 1, or even having 1 as part of #11270 later.
I'm marking this as "critical" since it is a major misleading mathematical bug, and it is functionality that gets used as a hypothesis for computational papers a lot (though in practice always in the direction that is safe, but who knows?).
See also: #11270
Change History (17)
comment:1 Changed 12 years ago by
comment:2 followup: 3 Changed 12 years ago by
That was pretty illegible. Let me try again:
"Professor Stein,
In relation to your recentlyopened ticket about Sage's elliptic curve galois representation code (http://trac.sagemath.org/sage_trac/ticket/11271): not only is is_surjective's docstring wrong, but non_surjective()'s docstring is also wrong. It says the function can be inconclusive at 2, but in fact it calls is_surjective(), which is always right at 2 and 3 since it determines the size of the Galois group of the pdivision polynomial. Probably someone wrote that before the special cases for 2 and 3 in is_surjective() had been implemented.
I don't yet have a trac account to report this, or I would've just opened a ticket. (I've requested an account.) But since you opened the ticket, I thought you might like to know of this bug as well.
Also, regarding the other ticket (implementing the algorithm in Zywina's paper): I've already written code that takes care of some (easy) cases in the paper, and is pretty fast compared to the existing is_surjective. (Specifically, just checking for surjectivity mod 8, 9 by first checking mod 2, 4, 3 in appropriate cases with a view to determining whether a curve is a Serre curve.) If you haven't already written it, I can clean it up and send it to you. I'm also willing to help further.
David Pathakjee
"
comment:3 Changed 12 years ago by
Not long after writing that, I was able to get a trac account and reported this as #11276.
Replying to was:
That was pretty illegible. Let me try again:
"Professor Stein,
In relation to your recentlyopened ticket about Sage's elliptic curve galois representation code (http://trac.sagemath.org/sage_trac/ticket/11271): not only is is_surjective's docstring wrong, but non_surjective()'s docstring is also wrong. It says the function can be inconclusive at 2, but in fact it calls is_surjective(), which is always right at 2 and 3 since it determines the size of the Galois group of the pdivision polynomial. Probably someone wrote that before the special cases for 2 and 3 in is_surjective() had been implemented.
I don't yet have a trac account to report this, or I would've just opened a ticket. (I've requested an account.) But since you opened the ticket, I thought you might like to know of this bug as well.
Also, regarding the other ticket (implementing the algorithm in Zywina's paper): I've already written code that takes care of some (easy) cases in the paper, and is pretty fast compared to the existing is_surjective. (Specifically, just checking for surjectivity mod 8, 9 by first checking mod 2, 4, 3 in appropriate cases with a view to determining whether a curve is a Serre curve.) If you haven't already written it, I can clean it up and send it to you. I'm also willing to help further.
David Pathakjee
"
comment:4 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:5 Changed 9 years ago by
Branch:  → u/wuthrich/ticket/11271 

Modified:  Aug 13, 2013, 3:34:36 PM → Aug 13, 2013, 3:34:36 PM 
comment:6 Changed 9 years ago by
Authors:  → Chris Wuthrich 

Commit:  → c3ae100155d686452e326d0dc4662a1c7378e61c 
Status:  new → needs_review 
Finally !! I corrected this.
So I decided to change the code. It now returns True False or None, depending if the algorithm can prove that it is surjective, can prove that it is not or if it is indecisive. I think this is more useful than the previous version.
Of course, I also altered the documentation to make sure the issue with 2 and 3 is correctly stated.
As discussed above. After this ticket a natural step would be to implement Zywina's bounds and criterions in his paper. I have tried so and that is documented on the ticket #12270 and should not concern this ticket any more. The ticket #11276 should be closed as a duplicate.
New commits:
c3ae100  Trac #11271: Corrections to is_surjective in Galois representations over Q.

comment:7 Changed 9 years ago by
Reviewer's comments (not only on the proposed changes, sorry):
 The functions
_splitting_field()
and_division_field()
would be used a lot if they were more visible! Please please please open two tickets dependent on this one to move these!
 There are quite a few little typos in the docstrings and comments (and at least one verbose message). Worth taking this opportunity to fix.
 It is very dangerous to store the underlying elliptic curve as G.E and the return it when asked since it can be changed!
sage: E = EllipticCurve('11a1') sage: G = E.galois_representation() sage: G.E Elliptic Curve defined by y^2 + y = x^3  x^2  10*x  20 over Rational Field sage: G.is_surjective(5) False sage: G.E = EllipticCurve('14a1') sage: G Compatible family of Galois representations associated to the Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x  6 over Rational Field sage: G.is_surjective(5) False
I don't know how to make a data field readonly, so I think the way to do this is to return copy(E) in the function elliptic_curve().
 G.reducible_primes() only returns a list of the primes p for which there is a pisogeny from E to some other curve, so ignores the CM case. This should be corrected, or at least the documentation changed!
sage: E = EllipticCurve('27a1') sage: E.has_cm() True sage: G = E.galois_representation() sage: G.reducible_primes() [3]
Of course it is not clear what the output should be here. We could follow the LMFDB route (see http://www.lmfdb.org/EllipticCurve/Q/27.a3) and only list the primes up to 37, with proper documentation of course. Otherwise we could try to be too clever and return (in that example) [3, Mod(1,3)].
More comments to follow  I don't trust trac not to lose all thet I have written so far...
comment:8 Changed 9 years ago by
Status:  needs_review → needs_work 

[Continued]
 The p=2 case could be simplified using
E.two_torsion_rank()
andE.discriminant().is_square()
. Then I don't think you need to explicitly construct the polynomial ring and x.
Otherwise, i.e. all that you actually did for this ticket, fine. So if I make this "needs work" please don't be angry!
comment:9 followup: 12 Changed 9 years ago by
I am certainly not angry, but thankful for your work.
I don't understand 4). Being reducible for the Galois module E[p] is equivalent to E having an isogeny defined over Q and so the answer is ok in all cases, including cm and including 27a. Did you get confused with non_surjective. There is should return [0] as documented.
1) There is already #11905 on the splitting field. I agree that division field could become a visible function. I opened a ticket on it : #15610.
3) Yes, I will do that. Is there a python rule about this in general?
5) Oh, that is a left over from a further change towards #11270. Sorry.
I'd proofread the documentation as well as I can.
comment:10 Changed 9 years ago by
Status:  needs_work → needs_review 

OK. 1) Opened a new ticket 2) I found a few misprints in the documentation. 3) I changed .E to ._E and returned copy for .elliptic_curve(). I hope that is what you had in mind. 4) no change as explained above 5) I don't think it makes a big difference. I would rather leave the welltested current version even if it is slightly too complicated. It is still easy to read from the code what it does. If you insist, I can change that, too, but it will be in the new year.
comment:11 Changed 9 years ago by
Commit:  c3ae100155d686452e326d0dc4662a1c7378e61c → 4c57ec058d7033b233b60b35993fb1e55d6982d1 

Branch pushed to git repo; I updated commit sha1. New commits:
4c57ec0  Trac #11271: making the curve inaccessible + documentation

comment:12 Changed 9 years ago by
Replying to wuthrich:
I am certainly not angry, but thankful for your work.
I don't understand 4). Being reducible for the Galois module E[p] is equivalent to E having an isogeny defined over Q and so the answer is ok in all cases, including cm and including 27a. Did you get confused with non_surjective. There is should return [0] as documented.
Sorry, just a stupid mistake on my part.
1) There is already #11905 on the splitting field. I agree that division field could become a visible function. I opened a ticket on it : #15610.
OK, good.
3) Yes, I will do that. Is there a python rule about this in general?
I don't know of a rule, but one has to be careful. Similarly, elliptic curves used to cache their ainvariants as a list and return them which meant that they could be changed; to avoid that the invariants are cached as a tuple which is immutable. But here it is the curve itself which is being cached. I also realise that the same problem exists with, for example, the period lattice of an elliptic curve. Sometimes people use a double underscore attribute name (e.g. EllipticCurveTorsionSubgroup
has an attribute __E
to store its curve, but that in itself does not stop it being maliciously (or by mistake) changed.
We may need to consult experts on this.
5) Oh, that is a left over from a further change towards #11270. Sorry.
OK, it is fairly harmless but if #11270 is stalled then perhaps it is worth changing here. Later: no need, it is harmless.
I'd proofread the documentation as well as I can.
OK, thanks  sorry I was lazy and did not give line numbers.
New commits:
4c57ec0  Trac #11271: making the curve inaccessible + documentation

comment:13 Changed 9 years ago by
I did not see your new changes until after posting my comments. I expect to be happy with them and will just check...
comment:14 Changed 9 years ago by
...done. I am happy with the last commit which addresses the points I made (at least, the valid ones). Good!
comment:15 Changed 9 years ago by
Reviewers:  → John Cremona 

Status:  needs_review → positive_review 
comment:16 Changed 9 years ago by
If you plan to continue working on Galois representations, please be aware that I am working on #11905 (which also touches that code and conflicts with this patch).
comment:17 Changed 9 years ago by
Resolution:  → fixed 

Status:  positive_review → closed 
A relevant email from another David: