EllipticCurveIsogeny raising a value error that an isogeny doesn't exist while it most certainly does!

[koffie]

sage: E = EllipticCurve_from_j(0)
sage: E
Elliptic Curve defined by y^2 + y = x^3 over Rational Field
sage: phi = E.isogenies_prime_degree(3)[1]
sage: phi
Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 7 over Rational Field
sage: EllipticCurveIsogeny(E,None,codomain=phi.codomain(),degree=3)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-58-7c6e8f3f3fa6> in <module>()
----> 1 EllipticCurveIsogeny(E,None,codomain=phi.codomain(),degree=Integer(3))

/Applications/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in __init__(self, E, kernel, codomain, degree, model, check)
   1008             old_codomain = codomain
   1009 
-> 1010             (pre_isom, post_isom, E, codomain, kernel) = compute_sequence_of_maps(E, codomain, degree)
   1011 
   1012         self.__init_algebraic_structs(E)

/Applications/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in compute_sequence_of_maps(E1, E2, ell)
   4003     (E1pr, E2pr, pre_isom, post_isom) = compute_intermediate_curves(E1, E2)
   4004 
-> 4005     ker_poly = compute_isogeny_kernel_polynomial(E1pr, E2pr, ell)
   4006 
   4007     return (pre_isom, post_isom, E1pr, E2pr, ker_poly)

/Applications/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in compute_isogeny_kernel_polynomial(E1, E2, ell, algorithm)
   3831         x^3 + x
   3832     """
-> 3833     return split_kernel_polynomial(compute_isogeny_starks(E1, E2, ell))
   3834 
   3835 def compute_intermediate_curves(E1, E2):

/Applications/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in compute_isogeny_starks(E1, E2, ell)
   3735         if (n == ell+1 or T == 0):
   3736             if (T == 0 or T.valuation()<2):
-> 3737                 raise ValueError("The two curves are not linked by a cyclic normalized isogeny of degree %s" % ell)
   3738             break
   3739 

ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 3

The above might seem like a silly example, since I am asking for an object I already know. But it is the underlying problem of why:

sage: phi.dual()
...
ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 3

is also broken.

Component: elliptic curves

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

[defeo]

comment:1

Weird. I thought this used to work, but now I am having a very hard time finding an example that does. I managed to compute this one (a multiplication endomorphism):

sage: E = EllipticCurve([1,1])
sage: F = E.change_weierstrass_model([1/3,0,0,0])
sage: EllipticCurveIsogeny(E,None,codomain=F,degree=9)
Isogeny of degree 9 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Rational Field to Elliptic Curve defined by y^2 = x^3 + 81*x + 729 over Rational Field

but many similar examples fail. Note that "normalized" is very important here:

sage: EllipticCurveIsogeny(E,None,codomain=E,degree=9)
...
ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 9

Given two isogenous elliptic curves, Sage only knows how to compute an isogeny between them if the models are normalized (isogeny sends invariant differential of codomain onto invariant differential of domain). Actually, I think the best algorithm to compute non-normalized isogenies between elliptic curves in characteristic 0 is still factoring the division polynomial, which Sage does not implement. There are better algorithms for finite fields (Couveignes, Lercier-Sirvent), but they are a pain to implement.

Note that you can do better if your goal is to compute the dual: choose enough points (about 2 times deg φ), for each of them compute φ(P) and [deg φ]P, and deduce φ by interpolation.

Sadly, Sage has many specialized algorithms for isogenies, but is severly lacking generic ones.

[JohnCremona]

comment:2

1. It does not make sense to talk about a normalised model here, unless by "model" you mean "Weierstrass equation and a choice of invariant differential" (which you probably do. Isogenies can be normalised, while means that the pull-back of a standard differential on the codomain is the standard differential on the domain (in general it is a scalar multiple of it, nonzero for separable isogenies).
2. For any isogeny of phi degree d from E1 to E2 it makes sense to ask if it is normalised (in the example, phi.is_normalised() does return True) and more generally what the scaling factor is (phi.formal()[1] -- which should have a method to get more easily).

Since this phi is normalised this is just a plain Bug.

The sentence "Actually, ..." is extremely misleading. Sage absolutely does implement the computation of isogenies via finding appropriate factors of the division polynomial. I spent a long time (and supervised part of a PhD thesis) showing how to do this -- picking an appropriate subset of the factors of the division polynomial is not trivial. But is is also very slow which is why the rest of the aforementioned thesis which is all implemented in Sage -- has been here for years now -- does this for all isogenies of prime degree p such that X_0^+(p) has genus 0.

Sage's isogeny capabilities are in my opinion very good. It is the only software in which one can compute isogenies as easily, or compute complete isogeny classes over arbitrary number fields -- there are hundreds (or more) lines devoted to this in several files. I implemented all that because I needed it in my own work (e.g. to compute the full isogeny classes for all the elliptic curves in the LMFDB, which are defined over number fields of degree up to 6). If other people need different capabilities, for example implementations which work better over large finite fields, they are welcome to implement them. But the fact that not everything of this type has been implemented does not imply that "Sage is severely lacking generic [algorithms]". I strongly dispute that statement, even without "severely".

Constructing isogenies given only domain and codomain and degree is something which is important for elliptic curves over finite fields because of elliptic curve cryptography, but much less so over number fields. So someone else can implement it.

Now I will put on my to-do list to actually fix the bug which leads to the reported behaviour.

[defeo]

comment:3

Hi John. I'm sorry if you got offended by my comment. It's 3 years old, I did not know about your code for grouping factors of the division polynomial back then (if it was already in Sage at the time).

I realize now that my diagnosis was misguided: indeed, phi.dual() seems to be correctly computing normalized models, so I'm not sure what's causing this failure. If you find the root cause of the bug, I'll be happy to review the fix.

Constructing isogenies given only domain and codomain and degree is something which is important
for elliptic curves over finite fields because of elliptic curve cryptography, but much less so
over number fields. So someone else can implement it.

I haven't really had any time to do "maths" developement in Sage in the past 3 years, but I hope things to change soon...

I'll open a separate ticket for my suggestion of falling back to the generic code when the models are not normalized.

[JohnCremona]

comment:4

No worries -- I just did not want the misleading impression to go uncorrected. The code I mentioned went in soon after Kimi's thesis was finished in 2013.

[JohnCremona]

I had forgotten all about this but it really needs to be fixed. Trying all curves of conductor <1000 and all prime degrees of isogeny, the ones where computing the dual fails are these (only degree 3 for some reason):

27a1, phi of degree 3, dual fails
27a3, phi of degree 3, dual fails
36a1, phi of degree 3, dual fails
36a3, phi of degree 3, dual fails
108a1, phi of degree 3, dual fails
108a2, phi of degree 3, dual fails
144a1, phi of degree 3, dual fails
144a3, phi of degree 3, dual fails
225a1, phi of degree 3, dual fails
225a2, phi of degree 3, dual fails
225b1, phi of degree 3, dual fails
225b2, phi of degree 3, dual fails
243a1, phi of degree 3, dual fails
243a2, phi of degree 3, dual fails
243b1, phi of degree 3, dual fails
243b2, phi of degree 3, dual fails
432a1, phi of degree 3, dual fails
432a3, phi of degree 3, dual fails
432b1, phi of degree 3, dual fails
432b2, phi of degree 3, dual fails
441a1, phi of degree 3, dual fails
441a2, phi of degree 3, dual fails
441b1, phi of degree 3, dual fails
441b2, phi of degree 3, dual fails
576a1, phi of degree 3, dual fails
576a3, phi of degree 3, dual fails
576e1, phi of degree 3, dual fails
576e3, phi of degree 3, dual fails
675a1, phi of degree 3, dual fails
675a2, phi of degree 3, dual fails
675c1, phi of degree 3, dual fails
675c2, phi of degree 3, dual fails
675e1, phi of degree 3, dual fails
675e2, phi of degree 3, dual fails
900a1, phi of degree 3, dual fails
900a2, phi of degree 3, dual fails
900b1, phi of degree 3, dual fails
900b3, phi of degree 3, dual fails
900c1, phi of degree 3, dual fails
900c2, phi of degree 3, dual fails
972a1, phi of degree 3, dual fails
972a2, phi of degree 3, dual fails
972b1, phi of degree 3, dual fails
972b2, phi of degree 3, dual fails
972c1, phi of degree 3, dual fails
972c2, phi of degree 3, dual fails
972d1, phi of degree 3, dual fails
972d2, phi of degree 3, dual fails

[yyyyx4]

This appears to be a precision issue in compute_isogeny_stark() which apparently only affects curves with 𝑗‑invariant 0 and isogenies of degree ℓ=3. I'll create a pull request with a simple fix shortly.