Opened 8 years ago

Closed 8 years ago

#12356 closed defect (fixed)

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

Reported by: cremona Owned by: cremona
Priority: critical Milestone: sage-5.0
Component: elliptic curves Keywords:
Cc: Merged in: sage-5.0.beta5
Authors: John Cremona, William Stein Reviewers: John Cremona, William Stein
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

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 trac_12356-cm-rebase-sage5.0.patch and trac_12356-cm-review.patch

Attachments (5)

trac_12356-cm.patch (6.9 KB) - added by cremona 8 years ago.
Applies to 4.8
trac_12356-extended.patch (22.2 KB) - added by was 8 years ago.
apply only this: developed on 5.0, but should apply to 4.8
trac_12356-extended-part2.patch (6.4 KB) - added by was 8 years ago.
replacing part 2 with a refreshed patch that has a better reference.
trac_12356-cm-rebase-sage5.0.patch (25.1 KB) - added by was 8 years ago.
Rebased everything as a single patch against sage-5.0.beta2 -- apply only this.
trac_12356-cm-review.patch (5.3 KB) - added by was 8 years ago.
change a line and the commit message

Download all attachments as: .zip

Change History (22)

Changed 8 years ago by cremona

Applies to 4.8

comment:1 Changed 8 years ago by cremona

  • Authors set to John Cremona
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by was

  • Priority changed from major to critical
  • Status changed from needs_review to needs_work

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

Changed 8 years ago by was

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

comment:3 Changed 8 years ago by was

  • Status changed from needs_work to needs_review

comment:4 Changed 8 years ago by was

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

comment:5 Changed 8 years ago by was

  • Authors changed from John Cremona to John Cremona, William Stein
  • Reviewers set to John Cremona, William Stein

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!

Changed 8 years ago by was

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

comment:6 Changed 8 years ago by cremona

  • Description modified (diff)

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.

Changed 8 years ago by was

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

comment:7 follow-up: Changed 8 years ago by was

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.

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

Replying to was:

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.

comment:9 Changed 8 years ago by cremona

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

comment:10 Changed 8 years ago by was

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.

Changed 8 years ago by was

change a line and the commit message

comment:11 Changed 8 years ago by was

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

comment:12 Changed 8 years ago by cremona

  • Status changed from needs_review to positive_review

comment:13 Changed 8 years ago by jdemeyer

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

comment:14 Changed 8 years ago by cremona

  • Description modified (diff)

comment:15 Changed 8 years ago by jdemeyer

  • Description modified (diff)

Thanks.

comment:16 Changed 8 years ago by cremona

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.

comment:17 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.