many missing class number 2 orders in CM j-invariant function over quadratic fields

[JohnCremona]

In sage/schemes/elliptic_curves/cm.py there is a list of imaginary quadratic orders with class number 2, introduced in #11220, but it is incomplete! Firstly, discriminant -72 is missing since the paper referred to omitted it in error; secondly, all 9 such orders whose maximal order has class number 1 were omitted by mistake.

The original patch (by JEC) adds the missing cases and adjusts the doctests (all for Q(sqrt(5)) whose output is now different as more cases are included. The later patches (by WAS) which are independent, do much much more, handling all class numbers up to 100.

Apply attachment: trac_12356-cm-rebase-sage5.0.patch and attachment: trac_12356-cm-review.patch

Component: elliptic curves

Author: John Cremona, William Stein

Reviewer: John Cremona, William Stein

Merged: sage-5.0.beta5

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

[JohnCremona]

Applies to 4.8

[JohnCremona]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
 In sage/schemes/elliptic_curves/cm.py there is a list of imaginary quadratic orders with class number 2, introduced in #11220, but it is incomplete!  Firstly, discriminant -72 is missing since the paper referred to omitted it in error; secondly, all 9 such orders whose maximal order has class number 1 were omitted by mistake.

-A patch will be provided shortly.
+The patch adds the missing cases and adjusts the doctests (all for Q(sqrt(5)) whose output is now different as more cases are included.

[JohnCremona]

Author: John Cremona

[JohnCremona]

comment:1

Attachment: trac_12356-cm.patch.gz

[williamstein]

comment:2

I found the code too hard to use in its current structure. I also think the whole approach of tables is brittle, when they are hand-typed in code, as evidenced by the mistakes so far. We should have general code, and if we want tables for optimization purposes, compute them, store them in SQLite, and put them in an spkg. I will post new code that does all this in a way that works for all degrees up to 100 (instead of just 2).

[williamstein]

apply only this: developed on 5.0, but should apply to 4.8

[williamstein]

comment:3

Attachment: trac_12356-extended.patch.gz

[williamstein]

comment:4

I've posted a patch that does the general case (up to degree 100) in a way that is refactored in a more usable way. This is in trac_12356-extended.patch, which does not depend on trac_12356.patch. For refereeing there are basically two mathematical arguments that are used in the code:

1. if a hilbert class polynomial F has a root in a field K of degree n, then the degree of F is at most n.

2. class_number(D) <= class_number(D*f^2) for fundamental D and integer f.

Of course, in 1, I think it would have to be a divisor of n, which could be used to optimize the code further. I hope these two statements are correct. I think I proved them to myself easily... but those are famous last words.

[williamstein]

Reviewer: John Cremona, William Stein

[williamstein]

comment:5

John Cremona found a mistake in my algorithm, which I've addressed via a new patch.

I've written a new version based on some of Cremona's comments and with a big comment explaining what I'm doing. Basically I just compute a pessimistic bound on the quotient (as you suggest) by applying a "big theorem" (probably from Hardy & Wright) bounding phi from below, and noting that phi_D(f) >= phi(f). The new code seems to work fine (and even found a class number 8 counterexample to the code I posted) and is pretty fast, but of course has plenty of room for optimization and improvement by your student, who could also run it to make tables, etc.

Of course, I very much hope John will extremely critically review this!

I didn't mention it, but the reason I wrote this code was not to scoop your student or something -- it was so I could better referee your patch!

[williamstein]

Changed author from John Cremona to John Cremona, William Stein

[williamstein]

Attachment: trac_12356-extended-part2.patch.gz

replacing part 2 with a refreshed patch that has a better reference.

[JohnCremona]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
 In sage/schemes/elliptic_curves/cm.py there is a list of imaginary quadratic orders with class number 2, introduced in #11220, but it is incomplete!  Firstly, discriminant -72 is missing since the paper referred to omitted it in error; secondly, all 9 such orders whose maximal order has class number 1 were omitted by mistake.

-The patch adds the missing cases and adjusts the doctests (all for Q(sqrt(5)) whose output is now different as more cases are included.
+The original patch (by JEC) adds the missing cases and adjusts the doctests (all for Q(sqrt(5)) whose output is now different as more cases are included.  The later patches (by WAS) which are independent, do much much more, handling all class numbers up to 100.

[JohnCremona]

comment:6

I have started to look at this. The patch applies fine to 4.8 and tests pass, and seem correct to me. I have quite a few suggestions for making the code run faster; the question is whether to insist on any of them now, or put all that into a follow-up ticket, so as not to delay correcting the wrong output which unpatched 4.8 gives.

[williamstein]

Attachment: trac_12356-cm-rebase-sage5.0.patch.gz

Rebased everything as a single patch against sage-5.0.beta2 -- apply only this.

[williamstein]

comment:7

Ping John -- I'm wondering if you're planning to continue reviewing this. I think I've fully dealt with the serious theoretical issue you pointed out. It would be great if this goes into sage-5.0.

[JohnCremona]

comment:8

Replying to @williamstein:

Ping John -- I'm wondering if you're planning to continue reviewing this. I think I've fully dealt with the serious theoretical issue you pointed out. It would be great if this goes into sage-5.0.

Agreed. Not forgotten. I'll be talking about to Janis again tomorrow and we'll see if any of the suggestions for speedups we have in mind are simple & urgent enough to be done right away, or whether they can wait for a follow-up ticket.

[JohnCremona]

comment:9

After all these years I still manage to lose large chunks of texts right after typing them. In this case I had been typing into this box, then clicked to upload a patch, after which the text had gone. So here's what the reviewer patch does:

1. trivial fixes to docstrings to keep Sphinx happy and tidy up

2. small change to code. There is a factor in the formula which is usually 1 but can be 2 or 3 and the factor is in the denominator so cannot be ignored without risking losing solutions. I have inserted it, though I did not come up with any case in which this would actually cause an error.

I also have several suggestions for making the new code more efficient, but it is fine for small h and the new code replaces wrong code for h=2 which did not work at all for h>2, so the efficiency question can be dealt with on a separate ticket.

I give a positive review apart from the issue in #2 above, so if William agrees with my change we can together give an overall positive review; or ask a 3rd party.

[williamstein]

comment:10

I fixed this one line in your patch (which was wrong, and simply reposted it with the line fixed):

                # we have h(D*f^2) >= (1/c)*h(D)*phi_D(f) >= h(D)*euler_phi(f), where 

changed to

                # we have h(D*f^2) >= (1/c)*h(D)*phi_D(f) >= (1/c)* h(D)*euler_phi(f), where 

With this change, I'm happy with your patch, so I think you can set it to positive review.

[williamstein]

Attachment: trac_12356-cm-review.patch.gz

change a line and the commit message

[williamstein]

comment:11

I also changed the commit message to "Trac #12356: fix Sphinx issues and one incorrect bound" instead of "trac 12356: fix Sphinx issues and one incorrect bound", because unbeknowst to us somebody seems to have decided that the canonical label for commit messages is "Trac #num: ...".

[jdemeyer]

comment:13

Please state clearly which patches have to be applied...

[JohnCremona]

Description changed:

--- 
+++ 
@@ -2,3 +2,5 @@

 The original patch (by JEC) adds the missing cases and adjusts the doctests (all for Q(sqrt(5)) whose output is now different as more cases are included.  The later patches (by WAS) which are independent, do much much more, handling all class numbers up to 100.

+Apply trac_12356-cm-rebase-sage5.0.patch and trac_12356-cm-review.patch 
+

[jdemeyer]

Description changed:

--- 
+++ 
@@ -2,5 +2,5 @@

 The original patch (by JEC) adds the missing cases and adjusts the doctests (all for Q(sqrt(5)) whose output is now different as more cases are included.  The later patches (by WAS) which are independent, do much much more, handling all class numbers up to 100.

-Apply trac_12356-cm-rebase-sage5.0.patch and trac_12356-cm-review.patch 
+Apply [attachment: trac_12356-cm-rebase-sage5.0.patch](https://github.com/sagemath/sage-prod/files/10654617/trac_12356-cm-rebase-sage5.0.patch.gz) and [attachment: trac_12356-cm-review.patch](https://github.com/sagemath/sage-prod/files/10654618/trac_12356-cm-review.patch.gz)

[jdemeyer]

comment:15

Thanks.

[JohnCremona]

comment:16

Comment: (1) running discriminants_with_bounded_class_number(hmax) creates a dict giving all the pairs (D,f) with class number h for h up to hmax. (2) running cm_orders(h) runs that with hmax=h and then throws away everything but the list for h itself; nothing is cached. This is rather inefficient! (3) I ran discriminants_with_bounded_class_number(100) -- 100 being teh largest value implemented -- and it took 19.5 hours; the output saves as a sobj file of size 630168 bytes.

Two possible speedups would be (1) cache all calls to pari's qfbclassno() which is where most of the time is spent, and (2) cache the dict produced and only do any computations if called with a larger value. And, now that this computation has been done once we could easily create a once-and-for-all Watkins-style table for non-maximal orders.

[jdemeyer]

Merged: sage-5.0.beta5