there is a serious bug in the documentation or code for is_surjective for Galois representations attached to elliptic curves

[williamstein]

David Zywina pointed out to me that the docstring for the Sage function clearly states: "Return True if the mod-p 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 re-call 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:

1. Probably the function as is can never ever prove non-surjectivity, except in various special cases. It should be changed to a better one that can prove non-surjectivity maybe following [1], or at least using division polynomials (since p<=37 anyways).

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

Component: elliptic curves

Author: Chris Wuthrich

Branch/Commit: u/wuthrich/ticket/11271 @ 4c57ec0

Reviewer: John Cremona

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

[williamstein]

comment:1

A relevant email from another David:

Professor Stein,

In relation to your recently-opened ticket about Sage's elliptic curve galois representation code (https://github.com/sagemath/sage-prod/issues/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 p-division 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

[williamstein]

comment:2

That was pretty illegible. Let me try again:

"Professor Stein,

In relation to your recently-opened ticket about Sage's elliptic curve galois representation code (#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 p-division 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

"

[sagetrac-dpathakjee]

comment:3

Not long after writing that, I was able to get a trac account and reported this as #11276.

Replying to @williamstein:

That was pretty illegible. Let me try again:

"Professor Stein,

In relation to your recently-opened ticket about Sage's elliptic curve galois representation code (#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 p-division 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

"

[chriswuthrich]

Branch: u/wuthrich/ticket/11271

[chriswuthrich]

Author: Chris Wuthrich

[chriswuthrich]

Commit: c3ae100

[chriswuthrich]

comment:6

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.

[JohnCremona]

comment:7

Reviewer's comments (not only on the proposed changes, sorry):

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

2. There are quite a few little typos in the docstrings and comments (and at least one verbose message). Worth taking this opportunity to fix.

3. 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 read-only, so I think the way to do this is to return copy(E) in the function elliptic_curve().

4. G.reducible_primes() only returns a list of the primes p for which there is a p-isogeny 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...

[JohnCremona]

comment:8

[Continued]

5. The p=2 case could be simplified using E.two_torsion_rank() and E.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!

[chriswuthrich]

comment:9

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 Implement division_field() for elliptic curves #11905 on the splitting field. I agree that division field could become a visible function. I opened a ticket on it : Division field for an elliptic curve #15610.

2. Yes, I will do that. Is there a python rule about this in general?

3. Oh, that is a left over from a further change towards Implement David Zywina's new fast algorithm for determining surjectivity of Galois representations attached to elliptic curves #11270. Sorry.

I'd proof-read the documentation as well as I can.

[chriswuthrich]

comment:10

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

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4c57ec0

Trac #11271: making the curve inaccessible + documentation

[sagetrac-git]

Changed commit from c3ae100 to 4c57ec0

[JohnCremona]

comment:12

Replying to @categorie:

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 Implement division_field() for elliptic curves #11905 on the splitting field. I agree that division field could become a visible function. I opened a ticket on it : Division field for an elliptic curve #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 a-invariants 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 Implement David Zywina's new fast algorithm for determining surjectivity of Galois representations attached to elliptic curves #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 proof-read 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

[JohnCremona]

comment:13

I did not see your new changes until after posting my comments. I expect to be happy with them and will just check...

[JohnCremona]

comment:14

...done. I am happy with the last commit which addresses the points I made (at least, the valid ones). Good!

[JohnCremona]

Reviewer: John Cremona

[jdemeyer]

comment:16

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