elliptic-curve isogenies probably shouldn't be mutable

[yyyyx4]

Right now, isogenies of elliptic curves are slightly mutable:
The three methods switch_sign, set_post_isomorphism, and set_pre_isomorphism all modify self.

As usual, this alone already causes bugs because it breaks hashing:

sage: E = EllipticCurve(GF(431), [1,0])
sage: phi = E.isogeny(E.lift_x(277))
sage: my_isogenies = {phi}
sage: iso = phi.codomain().isomorphism_to(phi.codomain().change_weierstrass_model(1,2,3,4))
sage: phi.set_post_isomorphism(iso)
sage: phi in my_isogenies
False
sage: phi in list(my_isogenies)
True

The bigger issue is that it breaks other constructions that use EllipticCurveIsogenies as a building block: The easiest example is the existing FormalCompositeMap we already get from composing two isogenies. Mutability means that the factors of the map can be changed after the composition has been constructed, with weird and buggy results:

sage: psi = E.multiplication_by_m_isogeny(2)
sage: f = phi * psi
sage: f(E(0,0))
(0 : 1 : 0)
sage: iso = phi.domain().change_weierstrass_model(1,2,3,4).isomorphism_to(phi.domain())
sage: psi.set_pre_isomorphism(iso)
sage: f(E(0,0))
# ...
TypeError: Coordinates [11, 145, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 431
sage: f.domain()
Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 431
sage: f[0].domain()
Elliptic Curve defined by y^2 + 6*x*y + 8*y = x^3 + 428*x^2 + 420*x + 425 over Finite Field of size 431

The main reason I care about this is because I'm working on parts of #7368, and this precise issue is causing quite a bit of headache. I suggest deprecating the set_*_isomorphism() and switch_sign() methods as soon as possible so that isogenies can stop mutating in-place at some point in the not too distant future.

Since I'm sure composing isogenies with isomorphisms will be sorely missed (I use this feature a lot myself), the patch does introduce new syntax for the same operations: We can simply write iso * phi to post-compose phi with iso, and similarly for pre-composition. The switch_sign method can already be substituted by the unary negation operator.
(Note that composing isogenies and isomorphisms using * does not result in a generic formal composition, but in an EllipticCurveIsogeny like before.)

To facilitate these "mixed" compositions, the patch reparents WeierstrassIsomorphism and EllipticCurveIsogeny under a common parent class EllipticCurveHom (mostly just a Morphism with a different name). This should also make implementing other classes of elliptic-curve morphisms (e.g., purely inseparable isogenies, formal sums of isogenies for endomorphism rings, etc.) easier in the future. As part of this change, WeierstrassIsomorphisms now have actual curves rather than groups of points as their (co)domains. This was the mathematically right choice all along and is consistent with EllipticCurveIsogenies.

Note: This patch is intentionally kept small. I'm aware of other things in the elliptic-curve isogeny code that need refactoring or fixing. My hope is that making small changes one at a time has a better chance of actually getting things done.

Also note: The patch is probably easiest to review by looking at the individual commits rather than the overall diff.

CC: @defeo @JohnCremona @tscrim

Component: elliptic curves

Keywords: isogenies, mutability

Author: Lorenz Panny

Branch/Commit: 40081c7

Reviewer: Travis Scrimshaw, John Cremona

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

[yyyyx4]

Author: Lorenz Panny

[yyyyx4]

Commit: 69a15a2

[yyyyx4]

Branch: public/deprecate_mutable_elliptic_curve_isogenies

[sagetrac-git]

Changed commit from 69a15a2 to b2d61b8

[sagetrac-git]

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

c24d57f	Revert "hack to make * compose isogenies and isomorphisms correctly"
5714eaa	make * compose isogenies and isomorphisms correctly
b2d61b8	make patchbot plugins happier

[yyyyx4]

comment:4

Replaced the previous, very hacky implementation of compositions between different types of EllipticCurveHoms by a slightly less hacky version that should make it easier to get compositions to work with new subclasses of EllipticCurveHom.

[sagetrac-git]

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

bb8c235

return NotImplemented instead of raising NotImplementedError

[sagetrac-git]

Changed commit from b2d61b8 to bb8c235

[yyyyx4]

comment:6

Yet another example where this causes things to break:

sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
sage: E = EllipticCurve([1,0])
sage: phi = E.isogeny(E(0,0))
sage: psi = phi.dual(); psi
Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field to Elliptic Curve defined by y^2 = x^3 + x over Rational Field
sage: psi.set_post_isomorphism(WeierstrassIsomorphism(E, (1,2,3,4)))
sage: phi.dual()
Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field to Elliptic Curve defined by y^2 + 6*x*y + 8*y = x^3 - 3*x^2 - 11*x - 6 over Rational Field

[mkoeppe]

comment:7

For composition you can also consider offering the _matmul_ operator (#30244, #32212)

[sagetrac-git]

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

207d534

add EllipticCurveHom to documentation

[sagetrac-git]

Changed commit from bb8c235 to 207d534

[yyyyx4]

comment:9

Replying to @mkoeppe:

For composition you can also consider offering the _matmul_ operator (#30244, #32212)

Sounds reasonable, but feels somewhat orthogonal to this ticket. In any case, to avoid fixing an interface prematurely, we should think about whether we'd like @ and * to do different things, in particular regarding #31850. (Personally, I think they should be the same and create isogeny-esque formal composite maps, as outlined in #31850 comment:6.)

[tscrim]

comment:10

For the internal call to _switch_sign, I think you should just explicitly replace it with the function call and get rid of _switch_sign as it is only called in one place in non-deprecated code.

[sagetrac-git]

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

c6b8f66

feedback from #32388: inline _switch_sign()

[sagetrac-git]

Changed commit from 207d534 to c6b8f66

[tscrim]

comment:12

Only other thing that needs to be done is make sure every method has a doctest.

[sagetrac-git]

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

fdc6117

#32388: more doctests

[sagetrac-git]

Changed commit from c6b8f66 to fdc6117

[yyyyx4]

comment:14

Done, I believe.

[sagetrac-git]

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

40081c7

not necessary

[sagetrac-git]

Changed commit from fdc6117 to 40081c7

[JohnCremona]

comment:16

Thanks to those who have been working on this and related tickets. I have just been looking at the threads after returning from holiday and am happy with what is being proposed.

The issue regarding normalization of isogenies is almost entirely restricted to isogenies over finite fields, where it is easy to achieve by changing the model used for the domain or codomain, but is almost irrelevant for isogenies over Q and other number fields, which I have done most with (and use most), where you often have few units around to scale modles by, and do not care whether the isogenies are normalised.

Secondly, composing with isomorphisms in general is used a lot in the code I wrote for compstructing isogenies over number fields, where there's a generic formula for short Weiertstrass equations but one want an isogeny between other (say minimal) models. In particular, pre- and post-composing by automorphisms was implemented the way it is (I seem to remember) by the original implemented, who worked over finite fields, and added some features at my request before the first versions of all this were merged years ago.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:17

Thank you. This LGTM.

John, forgive me as this is a bit outside my mathematical area, is there something with this ticket, such as removing the pre/post-compose with mutation that you disagree with, such as for performance reasons?

[JohnCremona]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, John Cremona

[JohnCremona]

comment:18

Replying to @tscrim:

Thank you. This LGTM.

John, forgive me as this is a bit outside my mathematical area, is there something with this ticket, such as removing the pre/post-compose with mutation that you disagree with, such as for performance reasons?

No, not at all. I really like these changes, and also the move towards unifying isogenies with isomorphisms (of Weierstrass models) which always were a special case. This is much better. I think that implementing W. isomorphisms was the very first thing I ever did in Sage, in 2007, so probably my first ever Python programming, and hence almost certainly in need of attention -- that was before isogenies were implemented at all, and was desperately needed at the time!

I have looked at the changes and am happy to add my name to the reviewers, and give this a positive review.

[tscrim]

comment:19

Great, thank you for clarifying and reviewing.

[yyyyx4]

comment:20

Thanks both of you! I'm glad you agree that these changes are a step towards making things better. :-)

[vbraun]

Changed branch from public/deprecate_mutable_elliptic_curve_isogenies to 40081c7