clean up ell_curve_isogeny.py

[yyyyx4]

The core of the elliptic-curve isogeny functionality in Sage is from #5976 — almost 13 years old! — and quite a few things in the EllipticCurveIsogeny class look somewhat dated by now.

In this patch, we make an effort to clean up ell_curve_isogeny.py. Besides plenty of style improvements, the main changes are:

• The documentation used to claim that only normalized, cyclic isogenies are supported. This is false for most of the codebase; these limitations only apply to a few selected algorithms (Kohel's formulas, Starks).

• The EllipticCurveIsogeny class contained some unused member variables, and some whose design choices seemed a bit random at times. I've streamlined the fields used to store the data of EllipticCurveIsogeny; among other things, this means we can unify the implementation of .degree() for all EllipticCurveHom children.

• The degree parameter for the isogeny_codomain method was unused; I've removed it.

• The split_kernel_polynomial() function appears to be equivalent to calling .radical() on the polynomial, which also seems a little bit faster.

• The .n() method only raised a NotImplementedError, but simply letting the call fall through to the parent class also fails gracefully. I've thus removed the specialized implementation.

• The .get_{pre,post}_isomorphism() methods won't really make sense once the corresponding (already deprecated) setters are removed. I added a remark to that effect.

Depends on #33582
Depends on #33214

CC: @shumow @JohnCremona @categorie @defeo @fchapoton @tscrim @videlec @slel @seblabbe

Component: elliptic curves

Author: Lorenz Panny

Branch/Commit: 2833869

Reviewer: John Cremona, Kwankyu Lee

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

[sagetrac-git]

Changed commit from d11e46d to fe19afa

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

09c3718	simplify 2tors/non2tors logic
52e6b02	remove obsolete __kernel_polynomial_list member
5709c30	remove obsolete __intermediate_codomain member
41d6c70	convert various [xy]_rational_maps fields into tuples
ca50d62	deduplicate __E1,__E2/_domain,_codomain members
a822059	rename __degree->_degree and move .degree() up to EllipticCurveHom
3071445	clarify that {pre,post}-isomorphisms are an implementation detail
b67b1e9	no need to override .n(); the default implementation fails gracefully
c4cd839	replace split_kernel_polynomial() by .radical()
fe19afa	add this spring cleaning to the file history

[JohnCremona]

comment:3

Thanks for doing this. I won't have time to review properly for a while, but as I wrote a lot of code (in Sage library for isogenies over Q and number fields) which uses this, if all those tests pass I'm sure I'll be happy. I have wanted to do some of the things suggested here since this class was created.

[chriswuthrich]

comment:4

Same here. This looks like very good work, but it will take to look through all and I doubt I have time to do it soon.

[sagetrac-git]

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

42f64e4	Merge tag '9.6.rc0' into public/clean_up_ell_curve_isogeny_file
1439e54	fix one minor patchbot warning

[sagetrac-git]

Changed commit from fe19afa to 1439e54

[yyyyx4]

comment:7

Thanks for your responses!

In order to alleviate the burden of reviewing this admittedly rather large patch, how about splitting the review load by commits? This could be especially useful as some of the biggest changes are generic code quality improvements which shouldn't require any specific elliptic-curve expertise.

It's also worth noticing that the vast majority of the changes belong to only two commits:

• 472c1629198, which contains mostly style and phrasing tweaks, with the only real difference being in the claims about requiring separable and/or normalized isogenies.
• 5c527009396, which consists of generic code tweaks.

Of course, none of this is urgent in principle, but it will keep causing merge conflicts with pretty much anything touching this file down the line, so it'd be nice to get it merged sooner rather than later.

Bottom line: If any of you happens to find a moment to look at just one or a few of the commits, please do, and comment here which part you've reviewed.

I'm also adding a few more people to Cc who've recently been active reviewing elliptic-curve tickets.

[JohnCremona]

comment:8

I'll be able to look at some of this, if not all, over the next couple of days

[tscrim]

comment:9

Just a quick comment from a very quick look: Removing arguments from public functions breaks backwards compatibility. They should be deprecated (with saying it is unused).

[sagetrac-git]

Changed commit from 1439e54 to e698562

[sagetrac-git]

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

6093062	Merge tag '9.6.rc1' into public/clean_up_ell_curve_isogeny_file
e698562	add deprecation warnings for obsolete "degree" argument

[kwankyu]

comment:12

I think it is a convention to write a condition in this way:

--- a/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
+++ b/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
@@ -217,7 +217,7 @@ def isogeny_codomain_from_kernel(E, kernel, degree=None):
 
     algorithm = isogeny_determine_algorithm(E, kernel)
 
-    if "velu" == algorithm:
+    if algorithm == "velu":
         # if we are using Velu's formula, just instantiate the isogeny
         # and return the codomain
         return EllipticCurveIsogeny(E, kernel).codomain()

in many places.

[JohnCremona]

Reviewer: John Cremona

[JohnCremona]

comment:13

This all looks good to me (I did read all the changes). The following suggestions are very minor and only affect docstrings. Otherwise, positive review (please add more names to the reviewers list too).

I agree with the previous comment but do not feel strongly enough about it to change it myself (as I never have all the other times I have worked on this file!)

"little-endian"? I don't think saying this helps much. In Sage, coefficient lists are always such that the i'th entry (indexed from 0 of course) is the coefficient of x^i. Perhaps remove it.

The _latex and _repr methods for some reason describe themselves as "Sage-specific": surely a redundant thing to do.

The line

sage: P, = E.gens()

surprised me! I would have written P = E.gens()[0], so I have learnt something, though I am not sure that the version with a comma on the left looks great.

[sagetrac-git]

Changed commit from e698562 to 0d8b6c8

[sagetrac-git]

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

4e5816d	Merge tag '9.7.beta2' into public/clean_up_ell_curve_isogeny_file
3dc4316	more standard order for variable-to-constant comparisons
d103a7e	clarify docstrings for ._repr_() and ._latex_()
0d8b6c8	little-endian is standard for polynomials in Sage; specifying this again might be more confusing than helpful

[yyyyx4]

comment:15

Thanks a lot for your time, everyone. I've applied all suggested changes.

Replying to @JohnCremona:

The line

sage: P, = E.gens()

surprised me! I would have written P = E.gens()[0], so I have learnt something, though I am not sure that the version with a comma on the left looks great.

I agree that the comma is not very pretty, and it's easy enough to miss at a quick glance. But there's a real difference between the two styles: x, = xs will throw an exception if xs has more than one element, whereas xs[0] will simply ignore everything after the first element. This can cause subtle bugs by breaking an unstated assumption of the code; by contrast, the tuple syntax makes explicit that a singleton list is expected and causes the assignment to fail loudly if this assumption is violated. We can think of it as a shorthand for assert len(xs) == 1; x = xs[0]. (The variant (x,) = xs also works.)

[kwankyu]

comment:16

Change of pre isomorphism to pre-isomorphism: I think the former is better since the latter wrongly suggests there is a mathematical notion pre-isomorphism.

__prei_ratl_maps: Why is this plural? There is one rational map (the isogeny), which consists of several rational functions (rational map components). No?

Perhaps you can write about the degree option in a similar format to

    - ``codomain`` -- an elliptic curve (default: ``None``).

      - If ``kernel`` is ``None``, ...
 
      - If ``kernel`` is not ``None``, ...

These hyphens are not necessary. Not improvements.

-    A more complicated example of a characteristic 2 field::
+    A more complicated example of a characteristic-2 field::

-        Function that implements the call-ability of elliptic curve
-        isogenies.
+        Implement evaluation of elliptic-curve isogenies using the
+        function-call syntax.

     def __getitem__(self, i):
         r"""
-        Return one of the rational map components.
+        Return one of the rational-map components.
 
         .. NOTE::

I doubt this change is an improvement. The names E1 and E2 are consistenly used internally throughout the code while domain() and codomain() are the method names for a user. With this change, E* and *domain are mixed in the code.

-    __E1 = None  # domain curve
-    __E2 = None  # codomain curve
+    _domain = None
+    _codomain = None

The original author protected __E* by using double underscores from subclasses. Is it intentional that you use single-underscored names?

"using the unary - operator" is not better?

     def __neg__(self):
         r"""
-        Function to implement unary negation (-) operator on
-        isogenies. Return a copy of this isogeny that has been
-        negated.
+        Implement negation of isogenies using the unary `-` syntax.
 
         EXAMPLES:

I don't see the value of these changes. The latter is hard to read:

-        a1 = E.a1()
-        a3 = E.a3()
+        a1, a3 = E.a1(), E.a3()

Similarly

-        self.__psi = psi
-        self.__phi = phi
-        self.__omega = omega
+        self.__psi, self.__phi, self.__omega = psi, phi, omega
 
-        self.__v = v
-        self.__w = w
+        self.__v, self.__w = v, w

Removing spaces after commas are hardly improvements.

-        b2, b4, b6, _ = E.b_invariants()
+        b2,b4,b6,_ = E.b_invariants()

Similarly here

-        a1, a2, a3, a4, a6 = E.ainvs()
-        b2, b4, _, _ = E.b_invariants()
+        a1,a2,a3,a4,a6 = E.a_invariants()
+        b2,b4,_,_ = E.b_invariants()

The comment about 'velu' == algorithm applies here:

-        if (0 != psi_G.degree()): # even degree case
+        if 0 != psi_G.degree(): # even degree case

[sagetrac-git]

Changed commit from 0d8b6c8 to 68cfda6

[sagetrac-git]

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

0973c01	swap another bunch of variable-to-constant comparisons
8f445a9	individual assignments may be more readable
206f62a	spaces after commas
68cfda6	small tweaks in docstring

[yyyyx4]

comment:18

Replying to @kwankyu:

Change of pre isomorphism to pre-isomorphism: I think the former is better since the latter wrongly suggests there is a mathematical notion pre-isomorphism.

It doesn't suggest that to me. I think of it as shorthand for "isomorphism that we pre-compose with". Either way, this part of the functionality is being phased out with the more general composite-morphism class added in #32744. We shouldn't waste much energy on it.

__prei_ratl_maps: Why is this plural? There is one rational map (the isogeny), which consists of several rational functions (rational map components). No?

There is also a .rational_maps() method, and an .x_rational_map() method. It may be considered an abuse of language, but it's in line with terminology used elsewhere in Sage. I don't have strong feelings about it.

Perhaps you can write about the degree option in a similar format to

    - ``codomain`` -- an elliptic curve (default: ``None``).

      - If ``kernel`` is ``None``, ...
 
      - If ``kernel`` is not ``None``, ...

Done.

These hyphens are not necessary. Not improvements.

-    A more complicated example of a characteristic 2 field::
+    A more complicated example of a characteristic-2 field::

-        Function that implements the call-ability of elliptic curve
-        isogenies.
+        Implement evaluation of elliptic-curve isogenies using the
+        function-call syntax.

     def __getitem__(self, i):
         r"""
-        Return one of the rational map components.
+        Return one of the rational-map components.
 
         .. NOTE::

All of these are examples of compound modifiers. Hyphenating them or not is fundamentally a question of personal style, but at least to my eyes the version with the hyphen is easier to parse. Your eyes seem to disagree. :-) Does "not improvements" mean you think the change makes it worse or just not better?

I doubt this change is an improvement. The names E1 and E2 are consistenly used internally throughout the code while domain() and codomain() are the method names for a user. With this change, E* and *domain are mixed in the code.

-    __E1 = None  # domain curve
-    __E2 = None  # codomain curve
+    _domain = None
+    _codomain = None

The original author protected __E* by using double underscores from subclasses. Is it intentional that you use single-underscored names?

I don't think there was any reason for the double underscores. The names
_domain and _codomain are inherited from the parent class. Previously, EllipticCurveIsogeny was duplicating __E1,__E2 into _domain,_codomain each time they changed, an unnecessary complication which does nothing useful while increasing the risk of mistakes.

"using the unary - operator" is not better?

     def __neg__(self):
         r"""
-        Function to implement unary negation (-) operator on
-        isogenies. Return a copy of this isogeny that has been
-        negated.
+        Implement negation of isogenies using the unary `-` syntax.
 
         EXAMPLES:

Rephrased.

I don't see the value of these changes. The latter is hard to read:

-        a1 = E.a1()
-        a3 = E.a3()
+        a1, a3 = E.a1(), E.a3()

Similarly

-        self.__psi = psi
-        self.__phi = phi
-        self.__omega = omega
+        self.__psi, self.__phi, self.__omega = psi, phi, omega
 
-        self.__v = v
-        self.__w = w
+        self.__v, self.__w = v, w

Reverted.

Removing spaces after commas are hardly improvements.

-        b2, b4, b6, _ = E.b_invariants()
+        b2,b4,b6,_ = E.b_invariants()

Similarly here

-        a1, a2, a3, a4, a6 = E.ainvs()
-        b2, b4, _, _ = E.b_invariants()
+        a1,a2,a3,a4,a6 = E.a_invariants()
+        b2,b4,_,_ = E.b_invariants()

Changed it to commas with spaces throughout.

The comment about 'velu' == algorithm applies here:

-        if (0 != psi_G.degree()): # even degree case
+        if 0 != psi_G.degree(): # even degree case

Fixed (here and elsewhere).

[kwankyu]

comment:19

Replying to @yyyyx4:

There is also a .rational_maps() method, and an .x_rational_map() method.

Right. It was already there.

All of these are examples of compound modifiers. Hyphenating them or not is fundamentally a question of personal style, but at least to my eyes the version with the hyphen is easier to parse. Your eyes seem to disagree. :-) Does "not improvements" mean you think the change makes it worse or just not better?

It makes it worse "to me", perhaps because it is rare (if not none) in sage source files to see both adjective form ("rational map") and compound modifier ("rational-map") in one place. As you think this is a personal style, I would not insist on it.

I don't think there was any reason for the double underscores. The names
_domain and _codomain are inherited from the parent class. Previously, EllipticCurveIsogeny was duplicating __E1,__E2 into _domain,_codomain each time they changed, an unnecessary complication which does nothing useful while increasing the risk of mistakes.

Okay as you know what you are doing.

Thanks for the fixes.

[kwankyu]

Changed reviewer from John Cremona to John Cremona, Kwankyu Lee

[kwankyu]

comment:21

Please consider this change:

--- a/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
+++ b/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
@@ -628,17 +628,19 @@ class EllipticCurveIsogeny(EllipticCurveHom):
 
     We can create an isogeny whose kernel equals the full 2-torsion::
 
-        sage: E = EllipticCurve(GF(3), [0,0,0,1,1])
+        sage: k = GF(3).algebraic_closure()
+        sage: E = EllipticCurve(k, [0,0,0,1,1])
         sage: ker_list = E.division_polynomial(2).list()
         sage: phi = EllipticCurveIsogeny(E, ker_list); phi
-        Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3 to Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3
+        Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x + 1 over
+        Algebraic closure of Finite Field of size 3 to Elliptic Curve
+        defined by y^2 = x^3 + x + 1 over Algebraic closure of Finite Field of size 3
         sage: phi(E(0))
         (0 : 1 : 0)
-        sage: phi(E((0,1)))
-        (1 : 0 : 1)
-        sage: phi(E((0,2)))
-        (1 : 0 : 1)
-        sage: phi(E((1,0)))
+        sage: (x1,_), (x2,_), (x3,_) = E.division_polynomial(2).roots()
+        sage: phi(E((x1,0)))
+        (0 : 1 : 0)
+        sage: phi(E((x2,0)))
+        (0 : 1 : 0)
+        sage: phi(E((x3,0)))
         (0 : 1 : 0)
         sage: phi.degree()
         4

or k = GF((3,2)).

[sagetrac-git]

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

cdab998	demonstrate vanishing on full 2-torsion in example
37346c8	remove some unnecessary polynomial-to-list conversions

[sagetrac-git]

Changed commit from 68cfda6 to 37346c8

[yyyyx4]

comment:23

Done. Also removed some unnecessary calls to Polynomial.list().

[kwankyu]

comment:24

Q is a tuple explicitly

--- a/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
+++ b/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
@@ -1065,7 +1065,7 @@ class EllipticCurveIsogeny(EllipticCurveHom):
         try:
             Q = compute(*Q)
         except ZeroDivisionError:
-            Q = 0, 1, 0
+            Q = (0, 1, 0)
 
         if self.__post_isomorphism is not None:
             Q = baseWI.__call__(self.__post_isomorphism, Q)

Unary operator?

--- a/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
+++ b/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
@@ -1229,7 +1229,7 @@ class EllipticCurveIsogeny(EllipticCurveHom):
         r"""
         Return a copy of the isogeny that has been negated.
 
-        This implements the unary `-` syntax.
+        This implements the unary `-` operator.
 
         EXAMPLES:

How about codomain or codomain_elliptic_curve, for consistency?

--- a/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
+++ b/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py 
@@ -1814,7 +1814,7 @@ class EllipticCurveIsogeny(EllipticCurveHom):
     #
     # Velu's formula computing the codomain curve
     #
-    def __compute_E2_via_velu(self):
+    def __compute_codomain_elliptic_curve_via_velu(self):
         r"""
         Private function that computes the codomain via Vélu's
         formulas.

Other suggestions (but subject to your discretion as always):

--- a/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
+++ b/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
@@ -1862,7 +1862,7 @@ class EllipticCurveIsogeny(EllipticCurveHom):
             sage: phi._EllipticCurveIsogeny__velu_sum_helper(0, Qvals, 0, 0, x, y)
             (1/x, y/x^2)
         """
-        yQ,gxQ,gyQ,vQ,uQ = Qvalues
+        yQ, gxQ, gyQ, vQ, uQ = Qvalues
 
         t1 = x - xQ
         inv_t1 = t1**-1
@@ -1965,9 +1965,11 @@ class EllipticCurveIsogeny(EllipticCurveHom):
         else:
             E = self.__pre_isomorphism.codomain()
 
-        a1, a3 = E.a1(), E.a3()
+        a1 = E.a1()
+        a3 = E.a3()
 
-        X, Y = xP, yP
+        X = xP
+        Y = yP
 
         for xQ, Qvalues in self.__kernel_mod_sign.items():
             tX, tY = self.__velu_sum_helper(xQ, Qvalues, a1, a3, xP, yP)
@@ -2088,7 +2090,8 @@ class EllipticCurveIsogeny(EllipticCurveHom):
         # Set up the necessary instance variables
         #
 
-        self.__kernel_polynomial = self.__inner_kernel_polynomial = psi
+        self.__kernel_polynomial = psi
+        self.__inner_kernel_polynomial = psi
 
         self._degree = Integer(d)  # degree of the isogeny
 
@@ -2359,7 +2362,9 @@ class EllipticCurveIsogeny(EllipticCurveHom):
             sage: phi._EllipticCurveIsogeny__compute_omega_fast(E, psi, psi_pr, fi, fi_pr)
             x^3*y - 3*x^2*y + x*y
         """
-        a1, a3 = E.a1(), E.a3()
+        a1 = E.a1()
+        a3 = E.a3()
+
         x, y = self.__mpoly_ring.gens()
 
         psi_2 = 2*y + a1*x + a3
@@ -2510,7 +2515,7 @@ class EllipticCurveIsogeny(EllipticCurveHom):
         a = self.__phi(xP)
         b = self.__omega(xP, yP)
         c = self.__psi(xP)
-        return a/c**2, b/c**3
+        return a / c**2, b / c**3
 
     def __initialize_rational_maps_via_kohel(self):
         r"""
@@ -2536,7 +2541,7 @@ class EllipticCurveIsogeny(EllipticCurveHom):
     #
     # Kohel's formula computing the codomain curve
     #
-    def __compute_E2_via_kohel(self):
+    def __compute_codomain_elliptic_curve_via_kohel(self):
         r"""
         Private function that computes and initializes the codomain of
         the isogeny (via Kohel's.)
@@ -3300,9 +3305,11 @@ def compute_isogeny_starks(E1, E2, ell):
 
     INPUT:
 
-    - ``E1``  -- an elliptic curve in short Weierstrass form, the domain.
-    - ``E2``  -- an elliptic curve in short Weierstrass form, the codomain.
-    - ``ell`` -- the degree of an isogeny from E1 to E2.
+    - ``E1``  -- an elliptic curve in short Weierstrass form, the domain
+
+    - ``E2``  -- an elliptic curve in short Weierstrass form, the codomain
+
+    - ``ell`` -- the degree of an isogeny from E1 to E2
 
     OUTPUT:
 
@@ -3433,8 +3440,8 @@ def split_kernel_polynomial(poly):
         True
     """
     from sage.misc.superseded import deprecation
-    deprecation(33619, 'The split_kernel_polynomial() function is obsolete.' \
-                      ' Use .radical() instead.')
+    deprecation(33619, 'The split_kernel_polynomial() function is obsolete. '
+                       'Use .radical() instead.')
     from sage.misc.misc_c import prod
     return prod([p for p,e in poly.squarefree_decomposition()])

diff --git a/src/sage/schemes/elliptic_curves/ell_field.py b/src/sage/schemes/elliptic_curves/ell_field.py
index d2d8dc0334..e7f56fa78a 100644
--- a/src/sage/schemes/elliptic_curves/ell_field.py
+++ b/src/sage/schemes/elliptic_curves/ell_field.py
@@ -855,7 +855,9 @@ class EllipticCurve_field(ell_generic.EllipticCurve_generic, ProjectivePlaneCurv
             this case, the isogeny is post-composed with an isomorphism so
             that the codomain equals the given curve.
 
-        - ``degree`` -- an integer (default: ``None``).  If ``kernel`` is
+        - ``degree`` -- an integer (default: ``None``).
+
+          - If ``kernel`` is ...

diff --git a/src/sage/schemes/elliptic_curves/hom.py b/src/sage/schemes/elliptic_curves/hom.py
index 4156e595bd..de40a53422 100644
--- a/src/sage/schemes/elliptic_curves/hom.py
+++ b/src/sage/schemes/elliptic_curves/hom.py
@@ -32,7 +32,6 @@ class EllipticCurveHom(Morphism):
     """
     Base class for elliptic-curve morphisms.
     """
-
     def _repr_type(self):
         """
         Return a textual representation of what kind of morphism

[sagetrac-git]

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

454f3ed	E2 -> codomain in method names
f131ae3	code style tweaks
de6552e	hide internal helper function
2833869	some doc tweaks

[sagetrac-git]

Changed commit from 37346c8 to 2833869

[yyyyx4]

comment:26

Thanks. Done, and also cleaned up the docstrings some more.

I've also prefixed an underscore to isogeny_determine_algorithm, as I can't imagine any way in which it could be helpful to users. In fact, I'd personally consider hiding some more of the helper functions in this module, but have resisted the temptation so far.

[kwankyu]

comment:27

Replying to @yyyyx4:

Thanks. Done, and also cleaned up the docstrings some more.

Thank you.

I've also prefixed an underscore to isogeny_determine_algorithm, as I can't imagine any way in which it could be helpful to users. In fact, I'd personally consider hiding some more of the helper functions in this module, but have resisted the temptation so far.

Okay.

I have no more comments. This looks good. I believe John amply checked the mathematics.

[yyyyx4]

comment:28

Thanks a lot!

[vbraun]

Changed branch from public/clean_up_ell_curve_isogeny_file to 2833869