Calling mwrank(-10) hangs Sage, but uses very little CPU time

[sagetrac-drkirkby]

Following some very quick hacks at using "fuzz testing" techniques, I found that

sage: mwrank(-10)

just hangs, but does not appear to be using any CPU time. Although I don't know what this is supposed to do, from discussions on sage-devel, I understand my suspicions this behavior is an error were correct.

Can someone please select the component appropriately, as I don't have a clue myself.

CC: @JohnCremona

Component: elliptic curves

Keywords: mwrank

Author: John Cremona

Branch/Commit: u/wuthrich/ticket/10108 @ 0fb4c7d

Reviewer: Mike Hansen, Chris Wuthrich

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

[JohnCremona]

Changed keywords from none to mwrank

[JohnCremona]

comment:1

I have a patch for this which I will post soon.

[JohnCremona]

comment:2

Replying to @JohnCremona:

I have a patch for this which I will post soon.

Delays caused by break in internet access -- hope to post patch Sunday.

[JohnCremona]

applies to 4.6.alpha3

[JohnCremona]

comment:3

Attachment: trac_10108-mwrank.patch.gz

This was harder than expected. Without either (1) rewriting mwrank's in put parser or (2) writing a full parser within Sage and only sending to mwrank when certainly correct, which I do not want to do. If you feed mwrank correct but incomplete input (such as <5 integers separated by whitespace) it quietly waits for the rest of the input (with no prompts).

To get around this I pad the strings sent to mwrank with ' 0 0 0 0 0 ' which means that this never happens, and then to get repeated calls to mwrank to work properly need a bit of fiddling. I tested the patch on two machines (4.6.alpha3).

[JohnCremona]

Author: John Cremona

[sagetrac-drkirkby]

comment:4

Replying to @JohnCremona:

This was harder than expected. Without either (1) rewriting mwrank's in put parser or (2) writing a full parser within Sage and only sending to mwrank when certainly correct, which I do not want to do. If you feed mwrank correct but incomplete input (such as <5 integers separated by whitespace) it quietly waits for the rest of the input (with no prompts).

If this hard, then perhaps it's more effort to fix properly than it is worth. You are a better judge of that than me.

I can't help feeling if this is supposed to take 5 integers then it should take 5, and not accept fewer or more, as it does. For example:

sage: mwrank('1 2 3')
"Curve [0,0,0,1,2] :     \n1 points of order 2:\n[-1:0:1]\n\nUsing 2-isogenous curve [0,6,0,-7,0] (minimal model [0,0,0,-19,30])\n-------------------------------------------------------\nFirst step, determining 1st descent Selmer groups\n-------------------------------------------------------\nAfter first local descent, rank bound = 0\nrk(S^{phi}(E'))=        1\nrk(S^{phi'}(E))=        1\n\n-------------------------------------------------------\nSecond step, determining 2nd descent Selmer groups\n-------------------------------------------------------\n...skipping since we already know rank=0\nAfter second local descent, rank bound = 0\nrk(phi'(S^{2}(E)))=     1\nrk(phi(S^{2}(E')))=     1\nrk(S^{2}(E))=   1\nrk(S^{2}(E'))=  2\n\nThird step, determining E(Q)/phi(E'(Q)) and E'(Q)/phi'(E(Q))\n-------------------------------------------------------\n1. E(Q)/phi(E'(Q))\n-------------------------------------------------------\n(c,d)  =(-3,4)\n(c',d')=(6,-7)\nThis component of the rank is 0\n-------------------------------------------------------\n2. E'(Q)/phi'(E(Q))\n-------------------------------------------------------\nThis component of the rank is 0\n\n-------------------------------------------------------\nSummary of results:\n-------------------------------------------------------\n        rank(E) = 0\n        #E(Q)/2E(Q) = 2\n\nInformation on III(E/Q):\n        #III(E/Q)[phi']    = 1\n        #III(E/Q)[2]       = 1\n\nInformation on III(E'/Q):\n        #phi'(III(E/Q)[2]) = 1\n        #III(E'/Q)[phi]    = 1\n        #III(E'/Q)[2]      = 1\n\n\nUsed descent via 2-isogeny with isogenous curve E' = [0,0,0,-19,30]\nRank = 0\nRank of S^2(E)  = 1\nRank of S^2(E') = 2\nRank of S^phi(E') = 1\nRank of S^phi'(E) = 1\n\nSearching for points (bound = 8)...done:\n  found points of rank 0\n  and regulator 1\nProcessing points found during 2-descent...done:\n  now regulator = 1\nSaturating (bound = 100)...done:\n  points were already saturated.\n\n\nRegulator = 1\n\nThe rank and full Mordell-Weil basis have been determined unconditionally.\n (0.055625 seconds)"

(It would also be nice if those \n's actually created a new line, as I expect they are supposed to do, but that's another issue entirely.)

Again, I don't feel able to review the Python.

[mwhansen]

comment:5

Attachment: trac_10108-mwrank.2.patch.gz

Looks good to me. I added a patch which fixes the indentation of the options blocks.

[mwhansen]

Reviewer: Mike Hansen

[jdemeyer]

comment:6

Please fix the ticket number (10108, NOT 10105) in the patch

[JohnCremona]

Attachment: trac_10105-mwrank.patch.gz

renamed version of previous -- applies to 4.6.rc0

[JohnCremona]

comment:7

Attachment: trac_10108-mwrank.3.patch.gz

Apply only trac_10108-mwrank.3.patch (and sorry for the mess -- previous ones can be deleted).

[jdemeyer]

Ticket number fixed, apply only this patch

[jdemeyer]

comment:8

Attachment: trac_10108-mwrank.4.patch.gz

John, I seem to have confused you :-)
Never mind, I made the fix myself.

[JohnCremona]

comment:9

Replying to @jdemeyer:

John, I seem to have confused you :-)
Never mind, I made the fix myself.

Very sorry - -first I thought it was the patch's name, then the comment in the doctest... but at least the bugfix works!

[jdemeyer]

comment:10

This patch gives trouble for me when merging it as part of a potential sage-4.6.1.alpha0. For some reason I cannot explain, I get the following error when running sage -t devel/sage/sage/interfaces/mwrank.py:

sage -t  "devel/sage/sage/interfaces/mwrank.py"
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/devel/sage/sage/interfaces/mwrank.py", line 111:
    sage: mwrank([0,-1,1,0,0])
Exception raised:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_4[3]>", line 1, in <module>
        mwrank([Integer(0),-Integer(1),Integer(1),Integer(0),Integer(0)])###line 111:
    sage: mwrank([0,-1,1,0,0])
      File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/local/lib/python/site-packages/sage/interfaces/mwrank.py", line 139, in __call__
        raise ValueError, 'Invalid input (%s) to mwrank'%cmd
    ValueError: Invalid input ([0, -1, 1, 0, 0]) to mwrank
**********************************************************************

What is strange is that simply doing

sage: mwrank([0,-1,1,0,0])

in a "real" Sage session works. So it works in Sage, but not in a doctest. I will need to investigate further.

[chriswuthrich]

comment:15

I have two tests that do not pass. (I have rebased the branch to 6.1.rc0; so maybe mwrank changed in the meantime.) I looks like

**********************************************************************
File "mwrank.py", line 233, in sage.interfaces.mwrank.Mwrank_class.__call__
Failed example:
    mwrank('0 -1 1 0 0')
Expected:
    'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304\ndisc=-76032\n2-adic index bound = 2\nBy Lemma 5.1(a), 2-adic index = 1\n2-adic index = 1\nOne (I,J) pair\nLooking for quartics with I = 16, J = -304\nLooking for Type 3 quartics:\nTrying positive a from 1 up to 1 (square a first...)\n(1,0,-4,4,0)\t--trivial\n(1,0,2,4,1)\t--trivial\nTrying positive a from 1 up to 1 (...then non-square a)\nFinished looking for Type 3 quartics.\nMordell rank contribution from B=im(eps) = 0\nSelmer  rank contribution from B=im(eps) = 0\nSha     rank contribution from B=im(eps) = 0\nMordell rank contribution from A=ker(eps) = 0\nSelmer  rank contribution from A=ker(eps) = 0\nSha     rank contribution from A=ker(eps) = 0\n\nUsed full 2-descent via multiplication-by-2 map\nRank = 0\nRank of S^2(E)  = 0\n\nProcessing points found during 2-descent...done:\n  now regulator = 1\n\n\nRegulator = 1\n\nThe rank has been determined unconditionally.\n\n...'
Got:
    'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304\ndisc=-76032\n2-adic index bound = 2\nBy Lemma 5.1(a), 2-adic index = 1\n2-adic index = 1\nOne (I,J) pair\nLooking for quartics with I = 16, J = -304\nLooking for Type 3 quartics:\nTrying positive a from 1 up to 1 (square a first...)\n(1,0,-4,4,0)\t--trivial\n(1,0,2,4,1)\t--trivial\nTrying positive a from 1 up to 1 (...then non-square a)\nFinished looking for Type 3 quartics.\nMordell rank contribution from B=im(eps) = 0\nSelmer  rank contribution from B=im(eps) = 0\nSha     rank contribution from B=im(eps) = 0\nMordell rank contribution from A=ker(eps) = 0\nSelmer  rank contribution from A=ker(eps) = 0\nSha     rank contribution from A=ker(eps) = 0\n\nUsed full 2-descent via multiplication-by-2 map\nRank = 0\nRank of S^2(E)  = 0\n\nProcessing points found during 2-descent...done:\n  now regulator = 1\n\n\nRegulator = 1\n\nThe rank and full Mordell-Weil basis have been determined unconditionally.\n (0.006 seconds)'
**********************************************************************
File "mwrank.py", line 239, in sage.interfaces.mwrank.Mwrank_class.__call__
Failed example:
    "Rank = 0" in s and "The rank has been determined unconditionally" in s
Expected:
    True
Got:
    False
**********************************************************************

[chriswuthrich]

Changed reviewer from Mike Hansen to Mike Hansen, Chris Wuthrich

[chriswuthrich]

Changed commit from 5b664d9 to e4f365a

[chriswuthrich]

Changed branch from u/cremona/ticket/10108 to u/wuthrich/ticket/10108

[JohnCremona]

comment:17

Thanks. Since you did a rebase I can't see what you changed additionally, but I seem to have slipped up in testing (in one example) that the long-winded mwrank output is good where because of the time output one cannot just do a literal comparison.
Testing...

[JohnCremona]

comment:18

OK, works for me (though I think my earlier branch did too!). I have set this back to "needs review" and Chris you can set it to positive review.

[chriswuthrich]

comment:19

Ah interesting.

I did not change anything. I litterally took your mwrank.py and copied it into a branch based at develop, checking that this file was not touch on since then.

So I get the above errors and you do not get them. So it seems that mwrank does not give back the same string for you than for me. The issue (in both failures) is the final sentence. I get

"The rank and full Mordell-Weil basis have been determined unconditionally."

while we test for

"The rank has been determined unconditionally."

Is there a change in mwrank that I have missed?

(I revert back to needs_work).

[JohnCremona]

comment:20

That is weird; I misunderstood. No changes at all in mwrank. But when I switch branches there is more recompilation than I would have expected (mpir rebuilds) for this. Very odd! I'll look into it further.

[chriswuthrich]

comment:21

From my develop to this branch u/wuthrich/..., it only compiles mwrank.py (as I would expect).

[JohnCremona]

comment:22

I think there was some conflict between the state of the original branch of mine called ticket/10108 and the branch I had after checking out yours. So I switched back to develop, deleted the branch ticket/10108 altogether and re-pulled it. Now my git log has the right look to it:

commit e4f365ae32a8804072b839205566fede75066431
Author: Chris Wuthrich <christian.wuthrich@gmail.com>
Date:   Sat Jan 25 20:33:23 2014 +0000

    Trac #10108: more robust interface to mwrank

commit 1bd331978c99681b70e4877fa3149b0c9adf47ce
Author: Volker Braun <vbraun.name@gmail.com>
Date:   Sat Jan 25 01:41:12 2014 +0000

    Updated Sage version to 6.1.rc0

so I rebuild (i.e. "make"). And sage/interfaces/mwrank.py passes its tests. And specifically when in Sage I run

sage: mwrank('0 -1 1 0 0')

the output string is

'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304\ndisc=-76032\n2-adic index bound = 2\nBy Lemma 5.1(a), 2-adic index = 1\n2-adic index = 1\nOne (I,J) pair\nLooking for quartics with I = 16, J = -304\nLooking for Type 3 quartics:\nTrying positive a from 1 up to 1 (square a first...)\n(1,0,-4,4,0)\t--trivial\n(1,0,2,4,1)\t--trivial\nTrying positive a from 1 up to 1 (...then non-square a)\nFinished looking for Type 3 quartics.\nMordell rank contribution from B=im(eps) = 0\nSelmer  rank contribution from B=im(eps) = 0\nSha     rank contribution from B=im(eps) = 0\nMordell rank contribution from A=ker(eps) = 0\nSelmer  rank contribution from A=ker(eps) = 0\nSha     rank contribution from A=ker(eps) = 0\n\nUsed full 2-descent via multiplication-by-2 map\nRank = 0\nRank of S^2(E)  = 0\n\nProcessing points found during 2-descent...done:\n  now regulator = 1\n\n\nRegulator = 1\n\nThe rank has been determined unconditionally.\n\n (0.004001 seconds)'

Now I see what is happening! The curve has rank 0; so mwrank does not do the usual saturation step of making sure that we have the full MW group and not a subgroup of finite index; there is a flag (in my C++ code) called sat_ok which is set to 1 if saturation suceeds, 0 if it fails -- and is uninitialized otherwise! So it will be random for a rank 0 curve where one sees the additional string "The rank and full Mordell-Weil basis have been determined" or "The rank and full Mordell-Weil basis have been determined".

Obviously I will correct this in eclib, which is timely since I was planning tp update Sage's version sson anyway. Meanwhile we'll have to sidestep this by changing that doctest sneakily. I suggest first deleting the variable sentence, effectively moving the "..." forward; and in the next line just test for "Rank = 0" in s.

Shall I do that or will you?

[chriswuthrich]

comment:23

I can do it.

Do you want to keep the lengthy output to be tested ? Or would not
'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304 ... determined unconditionally ...'
be enough ?

[JohnCremona]

comment:24

Replying to @categorie:

I can do it.

Thanks.

Do you want to keep the lengthy output to be tested ? Or would not
'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304 ... determined unconditionally ...'
be enough ?

That would be enough, certainly as we also check that "Rank = 0" is in there.

[sagetrac-git]

Changed commit from e4f365a to 0fb4c7d

[sagetrac-git]

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

0fb4c7d

Trac 10108: Change and shorten one doctest

[chriswuthrich]

comment:26

I run the tests now.

[JohnCremona]

comment:27

Replying to @JohnCremona:

Obviously I will correct this in eclib, which is timely since I was planning to update Sage's version soon anyway.

The eclib patch is visible here:

JohnCremona/eclib@d1ab6a5

and the new version (with a lot more than just this change) is in a new spkg at #15738. But this ticket does not need that.

[vbraun]

comment:31

See #15798 for a followup ticket