Opened 8 years ago
Closed 6 years ago
#12880 closed defect (fixed)
Inconsistent domain, codomain and parent in EllipticCurveIsogeny
Reported by:  nthiery  Owned by:  cremona 

Priority:  minor  Milestone:  sage6.3 
Component:  elliptic curves  Keywords:  isogeny 
Cc:  sagecombinat, 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 )
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 7 years ago by
 Component changed from number theory to elliptic curves
 Owner changed from was to cremona
comment:2 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:3 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:4 Changed 6 years ago by
 Cc pbruin added
comment:5 Changed 6 years ago by
comment:6 Changed 6 years ago by
 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): 1322 1322 self._codomain = self.__E2 1323 1323 1324 1324 # sets up the parent 1325 parent = homset.Hom(self.__E1 (0).parent(), self.__E2(0).parent())1325 parent = homset.Hom(self.__E1, self.__E2) 1326 1326 Morphism.__init__(self, parent) 1327 1327 1328 return1329 1330 1331 1328 # initializes the base field 1332 1329 def __init_algebraic_structs(self, E): 1333 1330 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 6 years ago by
 Cc defeo sbesnier added
comment:8 Changed 6 years ago by
 Branch set to u/sbesnier/ticket/12880
 Commit set to e623041b239f32098efb927f68a240529644b625
comment:9 Changed 6 years ago by
comment:10 followup: ↓ 17 Changed 6 years ago by
I've also make some modifications in order to make the composition working (essentially, remove the overload of `_composition_').
comment:11 Changed 6 years ago by
 Status changed from new to needs_review
comment:12 Changed 6 years ago by
 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/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/dfl/sage/local/lib/python2.7/sitepackages/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 6 years ago by
Oh I think I'm responsible for that. I've brutally renamed "__call__" to "_call_". I try to look at this.
comment:14 Changed 6 years ago by
 Commit changed from e623041b239f32098efb927f68a240529644b625 to b486f244b98a16b144cd45399eee3112ed5f824b
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b486f24  Fix parents, domain, codomain and _composition_ isogenies.

comment:15 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:16 Changed 6 years ago by
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 ; followup: ↓ 21 Changed 6 years ago by
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 "fleshandblood" 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): 3342 3301 ... 3343 3302 NotImplementedError 3344 3303 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`):: 3349 3306 3350 3307 sage: phi*phi 3351 3308 Traceback (most recent call last): 3352 3309 ... 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 Schemes3354 3355 Here would be the desired output::3356 3357 sage: phi*phi # not tested3358 Traceback (most recent call last):3359 ...3360 3310 NotImplementedError 3361 3311 """ 3362 3312 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 6 years ago by
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 6 years ago by
 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 6 years ago by
comment:21 in reply to: ↑ 17 Changed 6 years ago by
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 aNotImplementedError
) 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 "fleshandblood" 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 "fleshandblood" 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 followup: ↓ 26 Changed 6 years ago by
 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...
comment:23 Changed 6 years ago by
 Branch u/sbesnier/ticket/12880 deleted
 Commit b486f244b98a16b144cd45399eee3112ed5f824b deleted
comment:24 Changed 6 years ago by
 Branch set to u/sbesnier/ticket/12880
 Commit set to b486f244b98a16b144cd45399eee3112ed5f824b
New commits:
b486f24  Fix parents, domain, codomain and _composition_ isogenies.

comment:25 Changed 6 years ago by
New commits:
b486f24  Fix parents, domain, codomain and _composition_ isogenies.

comment:26 in reply to: ↑ 22 Changed 6 years ago by
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).
comment:27 Changed 6 years ago by
 Branch changed from u/sbesnier/ticket/12880 to u/sbesnier/ticket12880
 Commit changed from b486f244b98a16b144cd45399eee3112ed5f824b to 73d99af403e760801ae2576dfbb6f7629d629f30
New commits:
73d99af  Corrects the precedent commit.

comment:28 Changed 6 years ago by
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:
orTESTS::
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 6 years ago by
 Commit changed from 73d99af403e760801ae2576dfbb6f7629d629f30 to 09fdbedfa23931be1035e8860c61eb4a233b61ea
Branch pushed to git repo; I updated commit sha1. New commits:
09fdbed  Corrects stylistic staff in doctests.

comment:30 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:31 Changed 6 years ago by
 Branch changed from u/sbesnier/ticket12880 to u/pbruin/12880isogeny_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 6 years ago by
 Branch changed from u/pbruin/12880isogeny_parent to 02bc4122b7a49400e327f3a0259890eb0cce6705
 Resolution set to fixed
 Status changed from positive_review to closed
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.