#26677 closed defect (fixed)

rational_points for some elliptic curves fails

Reported by: alexjbest Owned by:
Priority: major Milestone: sage-8.5
Component: algebraic geometry Keywords: rational points, elliptic curves
Cc: raghukul01, bhutz Merged in:
Authors: Alex J. Best Reviewers: Ben Hutz
Report Upstream: N/A Work issues:
Branch: b6a6e97 (Commits) Commit: b6a6e9793ca6be1a9635bc8d5505d60970e81367
Dependencies: Stopgaps:

Description (last modified by alexjbest)

sage: E = EllipticCurve("11a1")
sage: E.rational_points(bound=5)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-1-892e6de8bab5> in <module>()
----> 1 E.rational_points("11a1")

AttributeError: 'function' object has no attribute 'rational_points'
sage: E = EllipticCurve("11a1")
sage: E.rational_points(bound=5)
Exception raised by child process with pid=90565:
Traceback (most recent call last):
  File "/Users/alex/sage/local/lib/python2.7/site-packages/sage/parallel/use_fork.py", line 177, in __call__
    self._subprocess(f, dir, *v0)
  File "/Users/alex/sage/local/lib/python2.7/site-packages/sage/parallel/use_fork.py", line 302, in _subprocess
    value = f(*args, **kwds)
  File "/Users/alex/sage/local/lib/python2.7/site-packages/sage/schemes/projective/projective_rational_point.py", line 460, in parallel_function
    Xp = X.change_ring(GF(p))
  File "/Users/alex/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_generic.py", line 1347, in change_ring
    return self.base_extend(R)
  File "/Users/alex/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_number_field.py", line 151, in base_extend
    E = super(EllipticCurve_number_field, self).base_extend(R)
  File "/Users/alex/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_generic.py", line 1329, in base_extend
    return constructor.EllipticCurve([R(a) for a in self.a_invariants()])
  File "sage/structure/factory.pyx", line 369, in sage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:2046)
    return self.get_object(version, key, kwds)
  File "sage/structure/factory.pyx", line 412, in sage.structure.factory.UniqueFactory.get_object (build/cythonized/sage/structure/factory.c:2422)
    obj = self.create_object(version, key, **extra_args)
  File "/Users/alex/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/constructor.py", line 471, in create_object
    return EllipticCurve_finite_field(R, x)
  File "/Users/alex/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_generic.py", line 149, in __init__
    raise ArithmeticError("invariants " + str(ainvs) + " define a singular curve")
ArithmeticError: invariants (0, 10, 1, 1, 2) define a singular curve
<---------SNIP----------->
/Users/alex/sage/local/lib/python2.7/site-packages/sage/schemes/generic/algebraic_scheme.pyc in rational_points(self, **kwds)
   1828                 return X.points(**kwds) # checks for proper bound done in points functions
   1829             except TypeError:
-> 1830                 raise TypeError("Unable to enumerate points over %s."%F)
   1831         elif (self.base_ring() in NumberFields() or self.base_ring() == ZZ)\
   1832           and hasattr(F, 'precision'):

TypeError: Unable to enumerate points over Rational Field.
sage: 

Miraculously this works for the curve that is currently doctested 37a,

The issue is that elliptic curves don't like to be base changed to bad primes, however for the purposes of sieving this is fine. So elliptic curves need to be convinced they are just curves for the purposes of sieving for points.

Precisely

Curve(E).rational_points(bound=5)

works even when E.rational_points(bound=5) does not. Not sure if a change should be made to elliptic curves (to have a special rational_points method, or to the generic sieving code to first change the input to a rather generic type of scheme. I like the former more as the latter causes friction if people want to add special methods that speed up base_change or whatever.

Change History (19)

comment:1 Changed 10 months ago by alexjbest

  • Description modified (diff)

comment:2 Changed 10 months ago by bhutz

As stated above, the problem is that the sieving method is not considering whether a prime could be bad. I also prefer the suggestion of elliptic curves having their own method; if for no other reason that the method could be significantly improved in the case of the elliptic curves. In the short term, the elliptic curve method could just call the current method as a generic 'curve' until a faster specialized algorithm is implemented.

comment:3 Changed 10 months ago by alexjbest

  • Branch set to u/alexjbest/elliptic-rational-pts

comment:4 Changed 10 months ago by alexjbest

  • Commit set to d22933248279eb613b11a1ba8e77d527de037aaf

Ok I added a patch, let me know if anyone thinks of a better solution, or if this should be somewhere more generic that elliptic_curve_number_field (thats just the situation I care about where I believe rational points is most common).


New commits:

d229332Add custom rational_points for elliptic curves

comment:5 Changed 10 months ago by alexjbest

  • Authors set to Alex J. Best
  • Status changed from new to needs_review

comment:6 Changed 10 months ago by alexjbest

  • Work issues set to wait for patchbot results

comment:7 Changed 10 months ago by bhutz

I didn't pull the branch to test, but don't you need to coerce the points back to original elliptic curve before returning.

comment:8 Changed 10 months ago by git

  • Commit changed from d22933248279eb613b11a1ba8e77d527de037aaf to 92354caf0e78c671fe0c77bac36ad785e0626c3d

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

92354cacoerce results back onto the curve

comment:9 Changed 10 months ago by alexjbest

Good point!

comment:10 Changed 10 months ago by alexjbest

  • Status changed from needs_review to needs_work

Actually this requires some more code as we need to allow

sage: E = EllipticCurve([1,0])
sage: E.rational_points(bound=2, F= QuadraticField(-1))

which currently fails

comment:11 Changed 10 months ago by git

  • Commit changed from 92354caf0e78c671fe0c77bac36ad785e0626c3d to 92587ffb817d566e1f49657e2e1e4141cb021d3b

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

92587ffallow for different field to be specified

comment:12 Changed 10 months ago by alexjbest

  • Status changed from needs_work to needs_review
  • Work issues changed from wait for patchbot results to wait for patchbot results again?

comment:13 Changed 10 months ago by bhutz

  • Reviewers set to Ben Hutz
  • Status changed from needs_review to needs_work

You need to get the keyword 'F' before it can be used.

Maybe change the last example to

sage: E = EllipticCurve([1,0])
sage: E.rational_points(F=QuadraticField(-1))

so an error like this shows up.

comment:14 Changed 10 months ago by git

  • Commit changed from 92587ffb817d566e1f49657e2e1e4141cb021d3b to b6a6e9793ca6be1a9635bc8d5505d60970e81367

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

c611533Add custom rational_points for elliptic curves
ea5cdbfcoerce results back onto the curve
f173817allow for different field to be specified
28e91adfix to getting field
b6a6e97Merge branch 'u/alexjbest/elliptic-rational-pts' of git://trac.sagemath.org/sage into elliptic-rational-pts

comment:15 Changed 10 months ago by alexjbest

  • Status changed from needs_work to needs_review

Yikes, thanks.

comment:16 Changed 10 months ago by bhutz

I think this is fine now. If we can get an all tests pass on the patchbot, I'll mark it positive.

comment:17 Changed 10 months ago by alexjbest

  • Work issues wait for patchbot results again? deleted

comment:18 Changed 10 months ago by bhutz

  • Status changed from needs_review to positive_review

ran the long tests on my machine. All passed.

comment:19 Changed 10 months ago by vbraun

  • Branch changed from u/alexjbest/elliptic-rational-pts to b6a6e9793ca6be1a9635bc8d5505d60970e81367
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.