Opened 7 years ago

Closed 6 years ago

# Bug in elliptic curve Galois Representation

Reported by: Owned by: cremona major sage-7.1 elliptic curves Galois representations John Cremona Frédéric Chapoton N/A 8680baa 8680baa2190b4ba4c183ac1a44ce4a619e731256

```sage: K.<a> = NumberField(x^2-x+1)
sage: E = EllipticCurve([a+1,1,1,0,0])
sage: C = E.isogeny_class()
...
ValueError: 0 is not prime.
```

is caused by

```sage: from sage.schemes.elliptic_curves.isogeny_class import possible_isogeny_degrees
sage: possible_isogeny_degrees(E)
[0]
```

and in turn by

```sage: EG = E.galois_representation()
sage: EG.reducible_primes()
[0]
```

According to the documentation for the last function it should return [0] if and only if E has CM, which is does not:

```sage: E.has_cm()
False
sage: E.j_invariant().is_integral()
False
```

(CM curves certainly have integral j-invariant, so you don't need to trust the is_cm() method to believe that!)

### comment:1 Changed 7 years ago by cremona

Tracked down to {{{_semistable_reducible_primes()}} in line 801:

```F = NumberField(y**2 - a, 'a')
```

where a is an integer, but then the code base-changes the base field to this field Q(sqrt(a)), and there is a problem since 'a' is the name of K's generator. This causes a ValueError? which is caught in the wrong place in lines 292-4:

```        try:
except ValueError:
return [0]
```

I will fix this by putting in a test for CM much earlier (which did not exist when this code was written). Also when constructing F we can make sure that the name of iots generator is not the same as that of K.

### comment:2 Changed 7 years ago by cremona

• Authors set to John Cremona
• Description modified (diff)

### comment:3 Changed 7 years ago by cremona

• Branch set to u/cremona/19229
• Commit set to df3d3f7c5819198be47c0f3dc8d7419066cee34c

New commits:

 ​df3d3f7 `19229: e.c. gal.reps. bug fix`

### comment:4 Changed 7 years ago by cremona

• Status changed from new to needs_review

Fixed as follows: on construction of the GaloisRepresentation? object the CM status of the elliptic curve is assessed and cached. This enables some cleaning of the code later where we never have to rely on the raising of exceptions to catch situations which only happen in the CM case. This does not in itself fix the bug, we just get a different error, so the second fix is to make the variable name of a number field constructed on one function not clash.

Appropriate doctests added here and in the docstring for E.isogeny_class().

### comment:5 Changed 7 years ago by cremona

• Description modified (diff)

### comment:6 Changed 6 years ago by cremona

Anyone out there?

### comment:7 follow-up: ↓ 8 Changed 6 years ago by jdemeyer

What's the point of this "poor man's caching", why not use `cached_method`?

```+        self._has_cm = E.has_cm()
+        self._has_rational_cm = E.has_rational_cm()
```

There seems to be an indentation problem with

```+ # ramified primes
```

Funny spacing:

```+ if E .has_bad_reduction(P):
```

### comment:8 in reply to: ↑ 7 Changed 6 years ago by cremona

What's the point of this "poor man's caching", why not use `cached_method`?

```+        self._has_cm = E.has_cm()
+        self._has_rational_cm = E.has_rational_cm()
```

No reason, but that is how it was, and this is a bug fix.

There seems to be an indentation problem with

```+ # ramified primes
```

Funny spacing:

```+ if E .has_bad_reduction(P):
```

I will look at those.

### comment:9 Changed 6 years ago by git

• Commit changed from df3d3f7c5819198be47c0f3dc8d7419066cee34c to cbd7a97697c15edab51f836b2fd0f6e48d329bc6

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

 ​83f8108 `Merge branch 'u/cremona/19229' of trac.sagemath.org:sage into 19229` ​cbd7a97 `#19229: fixes after review`

### comment:10 Changed 6 years ago by cremona

I merged with current beta, fixed the two spacing issues, made 3 methods into cached_methods as suggested. I also tidied up imports in ell_number_field.

### comment:11 Changed 6 years ago by jdemeyer

• Milestone changed from sage-6.9 to sage-6.10
• Status changed from needs_review to needs_work

Did you do something while committing? I see you added files `src/sage/schemes/hyperelliptic_curves/hypellfrob.cpp` and `src/sage/schemes/toric/divisor_class.c`

I recommend to fix this using `--amend` to make sure these added files don't appear in the git history at all.

### comment:12 follow-up: ↓ 13 Changed 6 years ago by cremona

That was a mistake. git is showing up hundreds of .c, .cpp, .h files which makes "git status" hard to read and I added some files by mistake *but then thought that I had removed them again*. What a pain. I'll fix it.

### comment:13 in reply to: ↑ 12 ; follow-up: ↓ 15 Changed 6 years ago by jdemeyer

git is showing up hundreds of .c, .cpp, .h files which makes "git status" hard to read

This isn't supposed to be like that. Do yourself a favour and remove those files.

### comment:14 Changed 6 years ago by git

• Commit changed from cbd7a97697c15edab51f836b2fd0f6e48d329bc6 to 62accc077ff28e2306364abaa60199846e292fdd

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​62accc0 `19229: fixes after review`

### comment:15 in reply to: ↑ 13 ; follow-up: ↓ 16 Changed 6 years ago by cremona

• Status changed from needs_work to needs_review

git is showing up hundreds of .c, .cpp, .h files which makes "git status" hard to read

This isn't supposed to be like that. Do yourself a favour and remove those files.

Any idea how they got there? None have anything to do with anything I have done. I presume a simple rm (not git) will suffice?

I fixed the commit...

### comment:16 in reply to: ↑ 15 Changed 6 years ago by jdemeyer

Any idea how they got there?

Well, they are quite old. Note the header:

```/* Generated by Cython 0.20.1 on Fri May 2 15:58:45 2014 */
```

I guess you don't remember what you were doing with your Sage installation that day.

I wouldn't think about it too much. Just delete those files.

### comment:17 follow-up: ↓ 20 Changed 6 years ago by jdemeyer

• Status changed from needs_review to needs_work

Obvious question: what is the performance impact of the earlier CM checks? It seems that the old code was careful to postpone CM checks.

All the methods where you added a check for CM should have a doctest for the case when there is no CM. Many don't have such a doctest.

Like I said before, this should be replaced by real caching (you implemented the caching, but forgot to remove this part):

```+        self._has_cm = E.has_cm()
+        self._has_rational_cm = E.has_rational_cm()
```

I think this comment is not very clear:

```+        # See #19229: can cause problems if this name is 'a' but it has to be something!
+        F = NumberField(y**2 - a, 'grnf_a')
```

### comment:18 follow-up: ↓ 21 Changed 6 years ago by jdemeyer

Just a question (not something to do for this ticket): did you ever consider computing the CM discriminant using the period lattice? If you have a sufficiently good (I guess this is the hard part) approximation to τ, you can compute its minimal polynomial A τ2 + B τ + C and from that the discriminant.

### comment:19 Changed 6 years ago by jdemeyer

In `src/sage/schemes/elliptic_curves/ell_number_field.py`, there are two lines

```         """
```

indented by 9 spaced instead of 8.

### comment:20 in reply to: ↑ 17 Changed 6 years ago by cremona

Obvious question: what is the performance impact of the earlier CM checks? It seems that the old code was careful to postpone CM checks.

Good question. When the code was first written there was no CM check available, so the presence of CM was detected indirectly; not that for CM curves the output will always be trivial. So I thought it simpler to put the CM check in early. On the other hand, whil it is often easy to see that a curve does *not* have CM (e.g. if j is not an algebraic integer), proving that it does have CM is harder. So perhaps it was better to discover the presence of CM the old way. I will investigate that.

All the methods where you added a check for CM should have a doctest for the case when there is no CM. Many don't have such a doctest.

OK.

Like I said before, this should be replaced by real caching (you implemented the caching, but forgot to remove this part):

```+        self._has_cm = E.has_cm()
+        self._has_rational_cm = E.has_rational_cm()
```

To be fixed.

I think this comment is not very clear:

```+        # See #19229: can cause problems if this name is 'a' but it has to be something!
+        F = NumberField(y**2 - a, 'grnf_a')
```

I'll explain here and also make the comment clearer. The original bug was only triggered when the base field already had 'a' as the name for its generator. Here we need to construct a number field and so we need a name which must not be a name used before in a similar context. So I cam up with such a name (I think grnfstands for "Galois Rep Number Field").

### comment:21 in reply to: ↑ 18 Changed 6 years ago by cremona

Just a question (not something to do for this ticket): did you ever consider computing the CM discriminant using the period lattice? If you have a sufficiently good (I guess this is the hard part) approximation to τ, you can compute its minimal polynomial A τ2 + B τ + C and from that the discriminant.

Interesting idea. Note that the existing code involves computing Hilbert Class Polynomials which does something similar. We can get tau to high precision easily since there is such a fast convergence for the periods. But some care would be needed to make this rigorous.

Improving the detection of CM would certainly be useful.

### comment:22 Changed 6 years ago by cremona

The new commit addresses the caching issue and the testing of the CM special cases. I also improved CM detection simply by caching the relevant functions. Testing whether one algebraic integer j of degree h is CM involves computing the quadratic orders of class number h: this is now cached so only done once for each h; and then computing the Hilbert class polynomials for each of these: now also cached, so as soon as a non-CM j of degree h is tested then testing any others of the same degree is no harder than checking whether its absolute minimal polynomial is in a cached list.

Pushing the new commit once tests have completed.

### comment:23 Changed 6 years ago by git

• Commit changed from 62accc077ff28e2306364abaa60199846e292fdd to e640e422ac1d54987a281130630d36a6a712c500

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

 ​521dac6 `19229: e.c. gal.reps. bug fix` ​fffbfed `19229: fixes after review` ​e640e42 `#19229: more improvements after review`

### comment:24 Changed 6 years ago by cremona

• Status changed from needs_work to needs_review

### comment:25 Changed 6 years ago by chapoton

• Status changed from needs_review to needs_work

does no longer apply.

### comment:26 Changed 6 years ago by cremona

Dammit, I thought this was merged ages ago. So I'll fix it -- I am using it every day!

### comment:27 Changed 6 years ago by git

• Commit changed from e640e422ac1d54987a281130630d36a6a712c500 to de3fdf1f0a502f5f9aaa75c835be91573d1cbe6a

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

 ​3ce177a `Merge branch 'develop' into 19229` ​de3fdf1 `minor changes to imports in one file`

### comment:28 Changed 6 years ago by cremona

• Status changed from needs_work to needs_review

OK, I merged into 7.0.beta1 and make some import adjustments so it now works.

New commits:

 ​3ce177a `Merge branch 'develop' into 19229` ​de3fdf1 `minor changes to imports in one file`

### comment:29 Changed 6 years ago by chapoton

two failing doctests !

### comment:30 Changed 6 years ago by cremona

I can guess which ones wince I noticed that there are two which sometoimes do work and sometimes do not. Since you do not tell me, I guess that these are the 2 6x6 matrices for the CM isogeny class example with class number 6.

In my defence, I can assure you that on my machine the tests *did* pass before I uploaded the branch....

### comment:31 Changed 6 years ago by chapoton

To know the failing doctest, you have to click on the patchbot icon (currently yellow with a question mark) at the top right of this page.

Then click on the "shortlog" link of the next-to-last report by "poseidon" patchbot.

This is indeed a 6*6 matrix of numbers and a 6*6 matrix of lists.

Last edited 6 years ago by chapoton (previous) (diff)

### comment:32 Changed 6 years ago by cremona

Yes that is the thing I was expecting. Note that there is another bot on which the test passes. It's something nondeterministic in how I sort the curves in an isogeny class.

### comment:33 Changed 6 years ago by cremona

By the, this (sometimes) failing doctest has nothing whatsoever to do with the changes on this ticket, but there is some randomness creeping into the sorting of curves.

### comment:34 Changed 6 years ago by chapoton

I have found a typo (several times):

```infintely many primes
```

Otherwise looks good to me (but I am no expert)

### comment:35 Changed 6 years ago by chapoton

• Milestone changed from sage-6.10 to sage-7.1

### comment:36 follow-up: ↓ 37 Changed 6 years ago by cremona

Would people be bothered if I marked the two strange doctests as "random" for the time being? Otherwise this sorting issue is delaying the merging of a genuine bug-fix. I have a strong personal incentive to get the sorting issue dealt with, but that should not be on this ticket anyway.

I plan to update the branch accordingly.

### comment:37 in reply to: ↑ 36 ; follow-up: ↓ 38 Changed 6 years ago by jdemeyer

Would people be bothered if I marked the two strange doctests as "random" for the time being?

With proper documentation and a reference to the discussion, no problem.

### comment:38 in reply to: ↑ 37 Changed 6 years ago by cremona

Would people be bothered if I marked the two strange doctests as "random" for the time being?

With proper documentation and a reference to the discussion, no problem.

OK, I'll see if I can meet your high standards or "proper"!

I corrected all occurrences of "infintely" also (2 here, but a few a other places).

### comment:39 Changed 6 years ago by git

• Commit changed from de3fdf1f0a502f5f9aaa75c835be91573d1cbe6a to 8680baa2190b4ba4c183ac1a44ce4a619e731256

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

 ​226821f `corrected typo infinite(ly) in a few places` ​8680baa `made two doctests random pending #20028`

### comment:40 Changed 6 years ago by cremona

I opened a new ticket #20028 for the issue of sorting number field elements. Th ebranch now marks thoe tests as #random and refers to the discussion on this ticket.

New commits:

 ​226821f `corrected typo infinite(ly) in a few places` ​8680baa `made two doctests random pending #20028`

### comment:41 Changed 6 years ago by chapoton

• Reviewers set to Frédéric Chapoton
• Status changed from needs_review to positive_review

ok, good enough for me

### comment:42 Changed 6 years ago by vbraun

• Branch changed from u/cremona/19229 to 8680baa2190b4ba4c183ac1a44ce4a619e731256
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.