#8829: Saturation for curves over number fields.
-------------------------------+--------------------------------------------
Reporter: robertwb | Owner: cremona
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.4.2
Component: elliptic curves | Keywords:
Author: Robert Bradshaw | Upstream: N/A
Reviewer: John Cremona | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Changes (by newvalueoldvalue):
* status: needs_review => needs_work
* reviewer: => John Cremona
* author: => Robert Bradshaw
Comment:
Patch applies fine to 4.4.1 and tests pass.
This functionality is badly needed!
We now have heights for points on curves defined over number_fields
but no associated regulator function. I suggest that the function
regulator_of_points() be moved up from ell_rational_field to
ell_number_field. This tcan then be called instead of the code in
lines 424-432 [line numbers are from the patched file, not the patch].
Line 439 uses a function self.height_function() which does not exist.
This block needs to be replaced by something sensible. If one has a lower
bound on the height of non-torsion
points, then a bound on the index can be deduced from standard
geometry of numbers estimates. To get such a lower bound, see papers
of Cremona & Siksek (over Q) and Thongjunthug (over number fields) for
an algorithm which would need to be implemented. (Not hard over Q,
not much harder for totally real fields, quite a lot worse over fields
with a complex embedding). Until this is done, I don't think this
saturation function can allow maxprime==0.
In the rank one code: when large primes p (say, over 20!) are being
tested then the division_points code will be expensive since it
involves constructing the multiplication-by-p map. I would recommend
using a reduction strategy here just as in the general case. To check
p-saturation just find primes q such that #E(Fq) is divisible by p and
then see if the reduction of P mod q is a multiple of p. This will
almost always prove saturation very quickly. If it fails for several
(say 5) q then try to divide P by p; else use more q, and so on.
There is one theoretical drawback here: this strategy might fail if
there is a rational p-isogeny. Over Q, we know which p this might
happen for and I would first test for the existence of isogenies of
primes degree, and use the division test (as here) for any primes that
show up. Over number fields that's harder to deal with, but again we
can fall back on the division test to rpove that P cannot be divided
by p.
The function list_of_multiples(P,n) duplicated the generic function
multiples() which I wrote for just this sort of purpose!
I don't like the loop through all linear combinations for small
primes. Even with p=2 there are curves with 24 independent points out
there and {{{2^24}}} divisions is not nice to contemplate. If you want
this
short cut, do it based on the size of {{{p^r}}}.
The main code with reduction etc looks fine to me (but I did not check
the logic rigorously).
The gens function for E(K) when E is defined over Q and [K:Q]=2 looks
fine. For a more general case we could always try using
simon_two_descent (followed by saturation). Trying such an examples
led me to:
{{{
sage: K.<a> = NumberField(x^2-2)
sage: E = EllipticCurve([a,0])
sage: P = E(0,0)
sage: P.has_finite_order()
True
sage: P.order()
2
sage: P.height()
0
sage: E.saturation([P], verbose=True, max_prime=5)
## infinite loop
}}}
This is caused as follows: The height matrix is [0] with det=0 but
reg / min(heights) is NaN so reg / min(heights) < 1e-6 is False!.
This will need fixing. At the very least, I would discard any points
of finite order before doing anything else with them. Then
min(heights) will never be 0.
Most of the above is easy to deal with. The hard part is computing a
suitable max_prime form a lower height bound on points. I suggest
that for now you make it compulsory to have a positive max_prime and
add a TODO.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8829#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
