Opened 5 years ago

Closed 3 years ago

#12880 closed defect (fixed)

Inconsistent domain, codomain and parent in EllipticCurveIsogeny

Reported by: nthiery Owned by: cremona
Priority: minor Milestone: sage-6.3
Component: elliptic curves Keywords: isogeny
Cc: sage-combinat, pbruin, defeo, sbesnier Merged in:
Authors: Sébastien Besnier Reviewers: Peter Bruin
Report Upstream: N/A Work issues:
Branch: 02bc412 (Commits) Commit: 02bc4122b7a49400e327f3a0259890eb0cce6705
Dependencies: #11474 Stopgaps:

Description (last modified by pbruin)

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

Change History (32)

comment:1 Changed 4 years ago by davidloeffler

  • Component changed from number theory to elliptic curves
  • Owner changed from was to cremona

comment:2 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 4 years ago by pbruin

  • Cc pbruin added

comment:5 Changed 4 years ago by 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.

comment:6 Changed 4 years ago by pbruin

  • Dependencies set to #11474
  • Description modified (diff)
  • Priority changed from major to minor

It should be very easy to fix in principle:

  • src/sage/schemes/elliptic_curves/ell_curve_isogeny.py

    diff --git a/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py b/src/sage/schemes/e
    index 5cdbbdf..a729d3a 100644
    a b class EllipticCurveIsogeny(Morphism): 
    13221322        self._codomain = self.__E2
    13231323
    13241324        # sets up the parent
    1325         parent = homset.Hom(self.__E1(0).parent(), self.__E2(0).parent())
     1325        parent = homset.Hom(self.__E1, self.__E2)
    13261326        Morphism.__init__(self, parent)
    13271327
    1328         return
    1329 
    1330 
    13311328    # initializes the base field
    13321329    def __init_algebraic_structs(self, E):
    13331330        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.

comment:7 Changed 4 years ago by defeo

  • Cc defeo sbesnier added

comment:8 Changed 3 years ago by sbesnier

  • Branch set to u/sbesnier/ticket/12880
  • Commit set to e623041b239f32098efb927f68a240529644b625

New commits:

de687fcCorrecting the ticket 12880. I've also make some modifications in order
e623041Merge remote-tracking branch 'origin/develop'

comment:9 Changed 3 years ago by sbesnier

  • Authors set to Sébastien Besnier

comment:10 follow-up: Changed 3 years ago by sbesnier

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

comment:11 Changed 3 years ago by sbesnier

  • Status changed from new to needs_review

comment:12 Changed 3 years ago by defeo

  • Status changed from needs_review to needs_work

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'>

comment:13 Changed 3 years ago by sbesnier

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

comment:14 Changed 3 years ago by git

  • Commit changed from e623041b239f32098efb927f68a240529644b625 to b486f244b98a16b144cd45399eee3112ed5f824b

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

b486f24Fix parents, domain, codomain and _composition_ isogenies.

comment:15 Changed 3 years ago by sbesnier

  • Status changed from needs_work to needs_review

comment:16 Changed 3 years ago by sbesnier

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!

comment:17 in reply to: ↑ 10 ; follow-up: Changed 3 years ago by pbruin

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

    diff --git a/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py b/src/sage/schemes/elliptic_
    curves/ell_curve_isogeny.py
    index 101b81e..8b18590 100644
    a b class EllipticCurveIsogeny(Morphism): 
    33423301            ...
    33433302            NotImplementedError
    33443303
    3345         The following should test that :meth:`_composition_` is called
    3346         upon a product. However phi is currently improperly
    3347         constructed (see :trac:`12880`), which triggers an assertion
    3348         failure before the actual call ::
     3304        The following tests that :meth:`_composition_` is called upon
     3305        a product (see :trac:`12880`)::
    33493306
    33503307            sage: phi*phi
    33513308            Traceback (most recent call last):
    33523309            ...
    3353             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
    3354 
    3355         Here would be the desired output::
    3356 
    3357             sage: phi*phi            # not tested
    3358             Traceback (most recent call last):
    3359             ...
    33603310            NotImplementedError
    33613311        """
    33623312        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?

comment:18 Changed 3 years ago by pbruin

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.

comment:19 Changed 3 years ago by pbruin

  • Status changed from needs_review to needs_work

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

comment:20 Changed 3 years ago by pbruin

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.

comment:21 in reply to: ↑ 17 Changed 3 years ago by defeo

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.

comment:22 follow-up: Changed 3 years ago by sbesnier

  • Status changed from needs_work to needs_review

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?

Last edited 3 years ago by sbesnier (previous) (diff)

comment:23 Changed 3 years ago by sbesnier

  • Branch u/sbesnier/ticket/12880 deleted
  • Commit b486f244b98a16b144cd45399eee3112ed5f824b deleted

comment:24 Changed 3 years ago by sbesnier

  • Branch set to u/sbesnier/ticket/12880
  • Commit set to b486f244b98a16b144cd45399eee3112ed5f824b

New commits:

b486f24Fix parents, domain, codomain and _composition_ isogenies.

comment:25 Changed 3 years ago by sbesnier

New commits:

b486f24Fix parents, domain, codomain and _composition_ isogenies.

comment:26 in reply to: ↑ 22 Changed 3 years ago by defeo

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).

Last edited 3 years ago by defeo (previous) (diff)

comment:27 Changed 3 years ago by sbesnier

  • Branch changed from u/sbesnier/ticket/12880 to u/sbesnier/ticket12880
  • Commit changed from b486f244b98a16b144cd45399eee3112ed5f824b to 73d99af403e760801ae2576dfbb6f7629d629f30

New commits:

73d99afCorrects the precedent commit.

comment:28 Changed 3 years ago by pbruin

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 : ; ? !

comment:29 Changed 3 years ago by git

  • Commit changed from 73d99af403e760801ae2576dfbb6f7629d629f30 to 09fdbedfa23931be1035e8860c61eb4a233b61ea

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

09fdbedCorrects stylistic staff in doctests.

comment:30 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:31 Changed 3 years ago by pbruin

  • Branch changed from u/sbesnier/ticket12880 to u/pbruin/12880-isogeny_parent
  • Commit changed from 09fdbedfa23931be1035e8860c61eb4a233b61ea to 02bc4122b7a49400e327f3a0259890eb0cce6705
  • Keywords isogeny added
  • Reviewers set to Peter Bruin
  • Status changed from needs_review to positive_review

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.

comment:32 Changed 3 years ago by vbraun

  • Branch changed from u/pbruin/12880-isogeny_parent to 02bc4122b7a49400e327f3a0259890eb0cce6705
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.