Inconsistent domain, codomain and parent in EllipticCurveIsogeny

[Nicolas M. Thiéry]

In the following example, the domain and codomain of phi do not match those of its parent::

sage: E = EllipticCurve(j=GF(7)(0))
sage: phi = EllipticCurveIsogeny(E, [E(0), E((0,1)), E((0,-1))])
sage: phi.parent()
Set of Morphisms from Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 to Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 in Category of hom sets in Category of Schemes
sage: phi.parent().domain()
Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7
sage: phi.domain()
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7
sage: phi.parent().codomain()
Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7
sage: phi.codomain()
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7

[John Cremona]

I have used elliptic curve isogenies a huge amount and this has never bothered me, presumably because it never occurred to me to ask for the parent of an isogeny. If anyone wants to change this without breaking anything they are welcome, but I don't care very much.

[Peter Bruin]

It should be very easy to fix in principle:

src/sage/schemes/elliptic_curves/ell_curve_isogeny.py

@@ -1322 +1322 @@
         self._codomain = self.__E2
 
         # sets up the parent
-        parent = homset.Hom(self.__E1(0).parent(), self.__E2(0).parent())
+        parent = homset.Hom(self.__E1, self.__E2)
         Morphism.__init__(self, parent)
 
-        return
-
-
     # initializes the base field
     def __init_algebraic_structs(self, E):
         r"""

The only problem is that this breaks testing for equality of isogenies, due to #11474. Suppose E -> E1 is an isogeny and E2 is an elliptic curve that is equal but not identical to E1. Then Hom(E, E1) and Hom(E, E2) will also be equal but not identical; since the coercion model assumes uniqueness of parents, it will never regard corresponding elements of Hom(E, E1) and Hom(E, E2) as equal.

For some reason the Hom sets between the groups of points, on the other hand, are identical, which explains why equality testing currently is not broken.

[Sebastien Besnier]

New commits:

​de687fc	Correcting the ticket 12880. I've also make some modifications in order
​e623041	Merge remote-tracking branch 'origin/develop'

[Sebastien Besnier]

I've also make some modifications in order to make the composition working (essentially, remove the overload of `_composition_').

[Luca De Feo]

Wow. It's so cool to be finally able to compose isogenies!

There's various doctests failing in ell_curve_isogeny.py. Most of them are because of #11474, so they should be ok once that one's fixed. However there's one weird failure, not sure if it depends on #11474 too:

File "src/sage/schemes/elliptic_curves/ell_curve_isogeny.py", line 945, in sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny._call_
Failed example:
    phi(E(15,20), output_base_ring=GF(23^2,'alpha'))
Exception raised:
    Traceback (most recent call last):
      File "/home/dfl/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/home/dfl/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny._call_[6]>", line 1, in <module>
        phi(E(Integer(15),Integer(20)), output_base_ring=GF(Integer(23)**Integer(2),'alpha'))
      File "map.pyx", line 764, in sage.categories.map.Map.__call__ (sage/categories/map.c:5434)
      File "map.pyx", line 797, in sage.categories.map.Map._call_with_args (sage/categories/map.c:5698)
    NotImplementedError: _call_with_args not overridden to accept arguments for <class 'sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny'>

[Sebastien Besnier]

Oh I think I'm responsible for that. I've brutally renamed "__call__" to "_call_". I try to look at this.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​b486f24

Fix parents, domain, codomain and _composition_ isogenies.

[Sebastien Besnier]

I've moved the "weird failure" reported at the comment 12 in #16238. Currently, the only failures on doctests depend on #11474.

It's one of the first time I use git and I had to change the history of the branch because of bad manipulations. I hope it won't bother anybody... Promise I won't do that again!

[Peter Bruin]

Replying to sbesnier:

I've also make some modifications in order to make the composition working (essentially, remove the overload of `_composition_').

This looks good to me overall. The main thing I am wondering about is if it wouldn't make sense to keep the current version of _composition_ (raise a NotImplementedError) until we have real composition of isogenies. What I mean is that with your change, we just get a "formal" composition of two isogenies. Although this may be good enough for some applications, what we really want is to compute the actual polynomials defining the composed isogeny. From that perspective I wouldn't say that removing the method "makes composition work".

The question is whether it is worth having a "formal" composition in the (hopefully short!) time interval until we have "flesh-and-blood" composition of isogenies. In other words, wouldn't it be reasonable to just make the following doctest change instead of removing the _composition_() method?

src/sage/schemes/elliptic_curves/ell_curve_isogeny.py

@@ -3342 +3301 @@
             ...
             NotImplementedError
 
-        The following should test that :meth:`_composition_` is called
-        upon a product. However phi is currently improperly
-        constructed (see :trac:`12880`), which triggers an assertion
-        failure before the actual call ::
+        The following tests that :meth:`_composition_` is called upon
+        a product (see :trac:`12880`)::
 
             sage: phi*phi
             Traceback (most recent call last):
             ...
-            TypeError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 is not in Category of hom sets in Category of Schemes
-
-        Here would be the desired output::
-
-            sage: phi*phi            # not tested
-            Traceback (most recent call last):
-            ...
             NotImplementedError
         """
         raise NotImplementedError

Another small request: would it be possible to keep the doctests of domain() and codomain() and move them to another place, instead of deleting them together with the methods?

[Peter Bruin]

Alternatively, instead of the NotImplementedError, we could temporarily "implement" _composition_() as

return super(EllipticCurveIsogeny, self)._composition_(self, right, homset)`

This just calls the method of the superclass and hence is practically the same as deleting the method, but it makes it clearer where the "real" _composition_() will have to be implemented.

[Peter Bruin]

One last thing: whatever the fate of _composition_(), can we at least keep the doctests for that method too?

[Peter Bruin]

By the way, there is a "wishlist" ticket at #7368 that also includes composition of isogenies. I think we should open a separate ticket for composition, since we are obviously not going to do all of #7368 at the same time.

[Luca De Feo]

This looks good to me overall. The main thing I am wondering about is if it wouldn't make sense to keep the current version of _composition_ (raise a NotImplementedError) until we have real composition of isogenies. What I mean is that with your change, we just get a "formal" composition of two isogenies. Although this may be good enough for some applications, what we really want is to compute the actual polynomials defining the composed isogeny. From that perspective I wouldn't say that removing the method "makes composition work".

I'd rather say the opposite. There are applications where formal composition is the desired result.

Formal composition is essentially free, while "flesh-and-blood" composition may be expensive (exponential in the length of the chain). There are cryptosystems that exploit this fact, Sage should make it easy to implement them in a few lines of code.

I'm more in favour of using formal composition by default, and having a method (.normalize(), maybe?) to compute the "flesh-and-blood" version. Subsidiary question : what should equality do in this case?

I think we should open a separate ticket for composition, since we are obviously not going to do all of #7368 at the same time.

Agreed. It would be a better place to continue this discussion.

[Sebastien Besnier]

I've corrected the things pointed by Peter (essentially, doctests).I've made a "push" but it doesnt seem to appear here...

Edit: hum... I think I have to update the "commit" attribute of the ticket, but it always fails. The new commit is : 73d99af403e760801ae2576dfbb6f7629d629f30, it's visible from sage.git : ​http://git.sagemath.org/sage.git/commit/?id=73d99af403e760801ae2576dfbb6f7629d629f30

What am I doing wrong?

[Sebastien Besnier]

New commits:

​b486f24

Fix parents, domain, codomain and _composition_ isogenies.

[Sebastien Besnier]

New commits:

​b486f24

Fix parents, domain, codomain and _composition_ isogenies.

[Luca De Feo]

Edit: hum... I think I have to update the "commit" attribute of the ticket, but it always fails. The new commit is : 73d99af403e760801ae2576dfbb6f7629d629f30, it's visible from sage.git : ​http://git.sagemath.org/sage.git/commit/?id=73d99af403e760801ae2576dfbb6f7629d629f30

The 'commit' field is not meant to be edited manually. Changing it has no effect.

There are two similarly named branches on trac: u/sbesnier/ticket/12880 and u/sbesnier/ticket12880. Maybe you wanted the second one (change the 'branch' field in this case).

[Sebastien Besnier]

New commits:

​73d99af

Corrects the precedent commit.

[Peter Bruin]

A few small stylistic comments about docstrings:

• To refer to Trac tickets, use the syntax :trac:`12880` (in the HTML documentation, this is expanded to "Trac ticket 12880" and becomes a link).
• Usually TESTS: or TESTS:: is kept on a line by itself and, if relevant, there is a separate line of explanation referring to the specific issue, i.e. one of the following:

  TESTS::
  
      sage: 2 + 2
      4
  
  ----
  
  TESTS:
  
  Check that `2 + 2 = 4` (see :trac:`12880`)::
  
      sage: 2 + 2
      4
  

• In English, unlike in French, there is no space before the punctuation marks : ; ? !

[git]

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

​09fdbed

Corrects stylistic staff in doctests.

[Peter Bruin]

I'm happy with this and it passes all tests (when the dependencies are merged, of course). The reviewer patch just fixes a trivial merge conflict and whitespace.