Opened 12 years ago

Closed 9 years ago

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

Reported by: Owned by: William Stein John Cremona critical sage-6.1 elliptic curves Chris Wuthrich John Cremona N/A u/wuthrich/ticket/11271 4c57ec058d7033b233b60b35993fb1e55d6982d1

Description

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

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

comment:1 Changed 12 years ago by William Stein

A relevant email from another David:

```Professor Stein,

In relation to your recently-opened 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 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
```

comment:2 follow-up:  3 Changed 12 years ago by William Stein

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

"

comment:3 in reply to:  2 Changed 12 years ago by David Pathakjee

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

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

"

comment:4 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11 → sage-5.12

comment:5 Changed 9 years ago by wuthrich

Branch: → u/wuthrich/ticket/11271 Aug 13, 2013, 3:34:36 PM → Aug 13, 2013, 3:34:36 PM

comment:6 Changed 9 years ago by wuthrich

Authors: → Chris Wuthrich → c3ae100155d686452e326d0dc4662a1c7378e61c 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 John Cremona

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!
1. There are quite a few little typos in the docstrings and comments (and at least one verbose message). Worth taking this opportunity to fix.
1. 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().

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

comment:8 Changed 9 years ago by John Cremona

Status: needs_review → needs_work

[Continued]

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

comment:9 follow-up:  12 Changed 9 years ago by 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.

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.

5) Oh, that is a left over from a further change towards #11270. Sorry.

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

comment:10 Changed 9 years ago by wuthrich

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

comment:11 Changed 9 years ago by git

Commit: c3ae100155d686452e326d0dc4662a1c7378e61c → 4c57ec058d7033b233b60b35993fb1e55d6982d1

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

 ​4c57ec0 `Trac #11271: making the curve inaccessible + documentation`

comment:12 in reply to:  9 Changed 9 years ago by John Cremona

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.

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 #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`
Last edited 9 years ago by John Cremona (previous) (diff)

comment:13 Changed 9 years ago by John Cremona

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 John Cremona

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

Last edited 9 years ago by John Cremona (previous) (diff)

comment:15 Changed 9 years ago by John Cremona

Reviewers: → John Cremona needs_review → positive_review

comment:16 Changed 9 years ago by Jeroen Demeyer

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 Volker Braun

Resolution: → fixed positive_review → closed
Note: See TracTickets for help on using tickets.