John Cremona's profile - activity

Thanks David for improvng my rather hasty asnwer and for clearing up the follow-up questions.

The solution is to use modular symbols: sage: N=120                                                                    

The solution is to use modular symbols: `sage: N=120                                                                  

The solution is to use modular symbols: sage: N=120                                                                    

Looking at the code, it seems to me that the functions implementing local and global heights are wrong. The global height of an individual algebraic number is, I think, correct (and I seem to remember that I wrote it) but the height of a point is projective space is certainly not the max of the heights of the coordinates -- for a start that is not well-defined, as already remarked. I'll make a sage trac ticket for this, and may even fix it myself.

In cidentally, all plane cubics given by Weierstrass equations are irreducible, even when singular. Since elliptic curves in Sage are Weierstrass cubics, the code for E.is_irreducible should just return True without bothering to call the generic irreducibility test.

Actually no -- as just explained by me also on Math.Stackexchange!

If yo upick random points on E rather than random elements of the abelian group then I think you will find that the time taken is longer. In your code you are only doing group operations in an abstract abelian group (either cyclic or possibly with two cyclic factors) so the operation is just one (or at most 2) integer modular multiplcations.

Sage does have p-adic fields, but no-one has yet implemented completions of number fields at finite places (see K.completeion? where K is a number field). You should still be able to manually construct the apprpriate p-adic field and base-change the elliptic curve to it.

Here's an example with a split prime, which is easier:

sage: K.<a> = NumberField(x^2 - x + 1)
sage: Q7 = Qp(7, prec=20)
sage: e1, e2 = K.embeddings(Q7)
sage: E = EllipticCurve('389a1').change_ring(K)
sage: Q = E.gens()[0]; Q
(-1 : 1 : 1)
sage: Q.division_points(5)
[]
sage: E.change_ring(e1)(Q).division_points(5)
[(2*7 + 5*7^2 + 3*7^4 + 6*7^5 + 3*7^6 + 4*7^7 + 7^8 + 7^9 + 4*7^10 + 3*7^11 + 4*7^12 + 3*7^13 + 7^14 + 5*7^16 + 4*7^18 + 5*7^19 + O(7^20) : 6 + 3*7 + 7^2 + 4*7^3 + 5*7^5 + 5*7^7 + 2*7^8 + 6*7^9 + 6*7^10 + 3*7^11 + 5*7^12 + 6*7^14 + 5*7^15 + 4*7^16 + 7^17 + 6*7^18 + O(7^20) : 1 + O(7^20))]

You can see how division polynomial is implemented using E.division_polynomial??. With just one ? you can see its parameters. The second optional paramater defaults to a variable x. The documentation (which I wrote, I think) says

 "x" - optional ring element to use as the "x" variable. If x is
 None, then a new polynomial ring will be constructed over the
 base ring of the elliptic curve, and its generator will be used
 as x. Note that x does not need to be a generator of a polynomial
 ring; any ring element is ok. This permits fast calculation of
 the torsion polynomial *evaluated* on any element of a ring.

i.e. in your code you could compute E.division_polynomial(N,z) for each z.

If P is the generator, use this:

sage: P.is_on_identity_component()
False

You can also see it with E.plot()+P.plot()!

In the second example the curve has cardinality 8245498483844445086274997696534494324318871629323439587180432555305925857658038158971493931464052751511244450366220997579222992221013001791913941608268032 which is hard to factor. The computation of the order of a point will be trying to factor it.

How would you find the order of the point? Suppose the group order is n=a*b where a and b are primes, but you do not know this factorization, and I give you a point of order a. How could you find that order more easily than factoring n?

I don't really understand the problems here. When you write E.quadratic_twist(d) you are defining an elliptic curve which is only defined up to isomorphism, and whose isomorphism class only depends on d modulo squares (assuming characteristic not 2 here). So twisting by d and d/4 give isomorphic curves. The code is written to work well with long as well as short Weierstrass equations.

I think that the modular functions giving the modular parametrization (the two power series in q returned by phi.power_series()) will converge very slowly.

Heights of points are defined for elliptic curves over globa; fields, e.g. QQ or number fields, not over finite fields.

What did you mean by the height of a point on an elliptic curve over a finite field?

E.gens() gives a list of generators for E(Q) modulo torsion. You can get the generators of the torsion subgroup with E.torsion_subgroup().gens().

It would be possible to add an option to E.gens() to include torsion generators. Right now (Sage 9.1) E.gens() is a list while E.torsion_subgroup().gens() is a tuple so it is a bit awkward:

sage: E.gens()+list(E.torsion_subgroup().gens()) 
[(3 : 2 : 1), (-1 : 0 : 1)]

If E is your elliptic curve and P is a point on E then P.division_points(2) returns a list of solutions Q to 2*Q=P.

In your starting_node function you are constructing points of order 3 but it seems that the function E_i(0).division_points(3) returns points whose order attribute is not set. That should be considered a bug, and probably my fault, certainly fixable. You can get around it rather easily if instead of constructing the isogenies as you do you call the method E_i.isogenies_prime_degree(3) which returns (quickly) a list of all 3-isogenies from E_i. This will include 3-isogenies whose kernel points are not in GF(p) (only their x-coordinates will certainly be), so if that matters you'll need to add a little more.

In the code as is Sage is computing the order of the point P before constructing the 3-isogeny, with no clue as to what that order might be or any bound on it, which may well cause the computation of the cardinality of the curve and its factorization.

The above output shows that the rank is at least 7, but mwrank has not finished. Each increase in A gives one more independent point (as shown in the output). The size of B is a power of 2, in this case 2^2 so far indicating another 2 in the rank. It is more efficient to increase one of mwrank's parameters (-x in the command line) as that shifts more of the rank into A away from B.

Magma gives the rank as 9 rather more quickly. It uses a different method in this case, the same as that used by E.simon_two_descent() but that does not work here for some reason. The method implemented in mwrank (used by Sage by default) can get slow for elliptic curves with large coefficients since it does some searching and the bounds are large.

The additional point is found with Sage version 7.5.rc2 so will be there in the next release. There was a bug fix since 7.4. However the MW basis used is the same in each case, with regulator 5.695... and this is also what mwrank gives, with a claim that the given points are saturated. I also just checked by hand that the generators are OK.

I think that your diagnosis was put off by a misleading message printed with verbose=True: the curve has 2 real components and there are rational points on the non-identity component (the "egg"). In the algorithm, the first step is to replace the full MW basis with a basis for the index 2 subgroup $E(\mathbb{Q})\cap E^0(\mathbb{R}}$, but this is allowed for later.

In fact the bug was quite different, and due to a precision problem which has been fixed.

This is a bug and is being dealt with at https://trac.sagemath.org/ticket/22164

By issuing the command "search_src("fundamental_domain") I found several examples to follow all from the modular/arithgroup/farey_symbol module so I suggest looking at that.

Probably not a useful answer 4 years later though.

The exact answer to your question is to use the mehod division_field, for example

sage: E = EllipticCurve([0,-1,1,-10,-20])
sage: E.division_field(5,'a')
Number Field in a with defining polynomial x^4 - x^3 + x^2 - x + 1

so that

sage: len(E.change_ring(K).torsion_points())
25

but as Nils said the degree is in general very large -- I chose an example where the degree of the 5-division field is only 4, which is as small as possible over QQ.