Opened 11 years ago

Closed 11 years ago

#9247 closed enhancement (fixed)

A collection of little improvements to elliptic curves

Reported by: rlm Owned by: cremona
Priority: major Milestone: sage-4.5.3
Component: elliptic curves Keywords:
Cc: wuthrich Merged in: sage-4.5.3.alpha0
Authors: Robert Miller, John Cremona Reviewers: John Cremona, Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by rlm)

These are some of the things I did while working on my thesis. Dependencies, in order:

#9441 (patch)

#9476 (patch and eclib spkg!)

Apply the patches in this order:

trac_9247.patch

trac_9247-saturation.patch

Attachments (2)

trac_9247-saturation.patch (2.7 KB) - added by cremona 11 years ago.
Apply after previous
trac_9247.patch (8.9 KB) - added by rlm 11 years ago.
Apply before saturation patch

Download all attachments as: .zip

Change History (21)

comment:1 Changed 11 years ago by rlm

  • Status changed from new to needs_review

comment:2 Changed 11 years ago by cremona

Looks like a job for me -- but probably not until I have finished preparing for SD22!

comment:3 follow-up: Changed 11 years ago by rlm

I'm wondering if by default, E.saturate() shouldn't print all that stuff from mwrank. Oddly, it doesn't show up in doctests, since it goes straight to the terminal.

There are also still failures in:

sage -t -long "devel/sage-main/sage/schemes/elliptic_curves/ell_rational_field.py"
sage -t -long "devel/sage-main/sage/schemes/elliptic_curves/padics.py"

John, Can you give some opinion on those?

comment:4 Changed 11 years ago by rlm

  • Status changed from needs_review to needs_work

comment:5 follow-up: Changed 11 years ago by cremona

  • Cc wuthrich added
  • Milestone set to sage-4.4.4
  • Reviewers set to John Cremona

Looks good and applies to 4.4.4.alpha0. I am currently testing all sage/schemes/elliptic_curves.

One point about the (good) new rank_bound parameter for the point_search function: is it not rather inefficient to saturate completely after every point found? In my code (in eclib's points own search function) I only partially saturate after each point, using a bound (i.e. max_prime) of 19. Then one the rank bound is reached (or at the end, if rank_bound is None) so a complete saturation.

I also think we should have an option for this function to not do the saturation step (which also discards all points found and replaces them for a Z-basis for their saturation), and just returns a list of the raw points actually found. If you agree, we should open a new ticket. (Obviously the current behaviour would be the default, for backward compatibility).

Test failure in sha_tate:

File "/home/john/sage-4.4.4.alpha0/devel/sage-tests/sage/schemes/elliptic_curves/sha_tate.py", line 637:
    sage: e.sha().an_padic(7)
Exception raised:
    Traceback (most recent call last):
      File "/home/john/sage-current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/john/sage-current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/john/sage-current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_5[14]>", line 1, in <module>
        e.sha().an_padic(Integer(7))###line 637:
    sage: e.sha().an_padic(7)
      File "/home/john/sage-current/local/lib/python/site-packages/sage/schemes/elliptic_curves/sha_tate.py", line 464, in an_padic
        ms = self.E.modular_symbol(sign=+1, normalize='L_ratio')
      File "/home/john/sage-current/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell_rational_field.py", line 1277, in modular_symbol
        M = ell_modular_symbols.ModularSymbolECLIB(self, sign, normalize=normalize)
      File "/home/john/sage-current/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell_modular_symbols.py", line 474, in __init__
        self._modsym = ECModularSymbol(E)
      File "newforms.pyx", line 75, in sage.libs.cremona.newforms.ECModularSymbol.__init__ (sage/libs/cremona/newforms.cpp:1794)
    OverflowError: long int too large to convert to int

and similar in padics:

File "/home/john/sage-4.4.4.alpha0/devel/sage-tests/sage/schemes/elliptic_curves/padics.py", line 91:
    sage: [ms(1/11), ms(1/3), ms(0), ms(oo)]
Exception raised:
    Traceback (most recent call last):
      File "/home/john/sage-current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/john/sage-current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/john/sage-current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_1[7]>", line 1, in <module>
        [ms(Integer(1)/Integer(11)), ms(Integer(1)/Integer(3)), ms(Integer(0)), ms(oo)]###line 91:
    sage: [ms(1/11), ms(1/3), ms(0), ms(oo)]
      File "/home/john/sage-current/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell_modular_symbols.py", line 523, in __call__
        return (self._atzero - self._modsym(r))*self._scaling
      File "newforms.pyx", line 130, in sage.libs.cremona.newforms.ECModularSymbol.__call__ (sage/libs/cremona/newforms.cpp:2024)
      File "rational.pyx", line 367, in sage.rings.rational.Rational.__init__ (sage/rings/rational.c:5781)
      File "rational.pyx", line 521, in sage.rings.rational.Rational.__set_value (sage/rings/rational.c:7052)
    TypeError: Unable to coerce +Infinity (<class 'sage.rings.infinity.PlusInfinity'>) to Rational

but I have no idea what in the patch could have caused this! And finally:

File "/home/john/sage-4.4.4.alpha0/devel/sage-tests/sage/schemes/elliptic_curves/ell_rational_field.py", line 1211:
    sage: M=E.modular_symbol()
Expected nothing
Got:
    Warning : Could not normalize the modular symbols, maybe all further results will be multiplied by -1, 2 or -2.
**********************************************************************
File "/home/john/sage-4.4.4.alpha0/devel/sage-tests/sage/schemes/elliptic_curves/ell_rational_field.py", line 1212:
    sage: M(1/7)
Expected:
    2
Got:
    -2
**********************************************************************

comment:6 in reply to: ↑ 5 Changed 11 years ago by rlm

Replying to cremona:

... the (good) new rank_bound parameter ... is it not rather inefficient to saturate completely after every point found? In my code (in eclib's points own search function) I only partially saturate after each point, using a bound (i.e. max_prime) of 19. Then one the rank bound is reached (or at the end, if rank_bound is None) so a complete saturation.

Sounds like a better option to me!

I also think we should have an option for this function to not do the saturation step (which also discards all points found and replaces them for a Z-basis for their saturation), and just returns a list of the raw points actually found. If you agree, we should open a new ticket. (Obviously the current behaviour would be the default, for backward compatibility).

I do agree!

... but I have no idea what in the patch could have caused this!

E.modular_symbol() now uses eclib if the sign is +1, for efficiency purposes. It is probably what is causing all the failures... I'm not sure whether this is practical or not, but it definitely sped up E.sha().p_primary_bound(p) in the cases I was looking at.

comment:7 in reply to: ↑ 3 Changed 11 years ago by rlm

Replying to rlm:

I'm wondering if by default, E.saturate() shouldn't print all that stuff from mwrank. Oddly, it doesn't show up in doctests, since it goes straight to the terminal.

More specifically, with the patch here applied to sage-4.4.4.alpha1 the following doctest illustrates the printing I'm talking about:

sage: EllipticCurve([0, 0, 1, -79, 342]).regulator(proof=False)  # long time (seconds)
Saturation index bound = 265
WARNING: saturation at primes p > 100 will not be done;  
points may be unsaturated at primes between 100 and index bound
Failed to saturate MW basis at primes [ ]
*** saturation possibly incomplete at primes [ ]
14.7905275701311

When I do this from the command line, that is exactly what I get. However, when I run long doctests in ell_rational_field.py the following part appears in the terminal from which I'm running the tests, and is a little misleading:

**********************************************************************
File "/Users/rlmill/sage-4.4.4.alpha1/devel/sage-main/sage/schemes/elliptic_curves/ell_rational_field.py", line 1212:
    sage: M(1/7)
Expected:
    2
Got:
    -2
Saturation index bound = 265
WARNING: saturation at primes p > 100 will not be done;  
points may be unsaturated at primes between 100 and index bound
Failed to saturate MW basis at primes [ ]
*** saturation possibly incomplete at primes [ ]
**********************************************************************

comment:8 Changed 11 years ago by cremona

OK, so the problem is that the warning output from the regulator call appears in the wrong place in the output -- right?

I have solved this by avoiding it as follows. The gens() function uses mwrank_lib (default) or mwrank_console to do a two-descent after constructing the mwrank_EllipticCurve C. But it was failing to call the saturate function on C. Some default saturation is done by the gens() call (on C), but the default saturation bound is rather low (100, set in eclib).

So I added a new parameter sat_bound to the gens() function in ell_rational_field, default 1000, and made sure that both mwrank_lib and mwrank_console option use it. Now we have

sage: E = EllipticCurve([0, 0, 1, -79, 342])
sage: E.gens()
[(-10 : 11 : 1), (-39/4 : 105/8 : 1), (-8 : 21 : 1), (-7 : 23 : 1), (-6 : 24 : 1)]
sage: E = EllipticCurve([0, 0, 1, -79, 342])
sage: E.gens(algorithm='mwrank_console')
[(-10 : 11 : 1), (-39/4 : 105/8 : 1), (-8 : 21 : 1), (-7 : 23 : 1), (-6 : 24 : 1)]

compared with

sage: E = EllipticCurve([0, 0, 1, -79, 342])
sage: E.gens(sat_bound=100)
Saturation index bound = 265
WARNING: saturation at primes p > 100 will not be done;  
points may be unsaturated at primes between 100 and index bound
Failed to saturate MW basis at primes [ ]
*** saturation possibly incomplete at primes [ ]
[(-10 : 11 : 1), (-39/4 : 105/8 : 1), (-8 : 21 : 1), (-7 : 23 : 1), (-6 : 24 : 1)]

I will post an additional patch in a minute.

Changed 11 years ago by cremona

Apply after previous

comment:9 Changed 11 years ago by cremona

My patch solves the issue with annoying output of warnings from saturation, since we now use a higher bound for saturation primes in finding the gens of an elliptic curve. (This provides useful functionality as well as fixing this particular case).

The other issues remain, but I think that Robert could review my patch!

comment:10 Changed 11 years ago by rlm

  • Authors changed from Robert Miller to Robert Miller, John Cremona
  • Reviewers changed from John Cremona to John Cremona, Robert Miller

New patch looks good. What to do about the others...

comment:11 follow-up: Changed 11 years ago by wuthrich

I would suggst to remove the modification to padic_lseries.py. In the future we should use eclib by default, but currently eclib does not provide negative modular symbols and they are needed in some cases (e.g. twisting by a negative D). A careful user can currently choose to use eclib, if he knows that he will not need negative modular symbols.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 11 years ago by cremona

Replying to wuthrich:

I would suggst to remove the modification to padic_lseries.py. In the future we should use eclib by default, but currently eclib does not provide negative modular symbols and they are needed in some cases (e.g. twisting by a negative D).

Yes it does now! Review my patch and you can have them! I implemented this while at MSRI. See #9476

A careful user can currently choose to use eclib, if he knows that he will not need negative modular symbols.

comment:13 in reply to: ↑ 12 Changed 11 years ago by wuthrich

Replying to cremona:

Yes it does now! Review my patch and you can have them! I implemented this while at MSRI. See #9476

Ohhh, I did not know. I hope I will have time to look at that tomorrow.

comment:14 Changed 11 years ago by rlm

  • Description modified (diff)

Changed 11 years ago by rlm

Apply before saturation patch

comment:15 Changed 11 years ago by rlm

  • Status changed from needs_work to needs_review

Okay, I've changed the default for elliptic curve modular symbols back to what it originally was. Now all tests pass, and this ticket is ready for a review.

comment:16 Changed 11 years ago by rlm

See also #9535

comment:17 Changed 11 years ago by was

  • Status changed from needs_review to positive_review

Works and seems reasonable in light of the above remarks.

comment:18 Changed 11 years ago by rlm

  • Description modified (diff)

comment:19 Changed 11 years ago by mpatel

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