Isogeny small degree improvement

[user202729]

Allow the following to be called without error.

sage: EllipticCurve(GF(31).algebraic_closure(), [0, 6, 0, 1, 0]).isogenies_prime_degree(5)

Inspired from, but independent from, https://github.com/sagemath/sage/issues/38373 . Whatever consensus on that issue might be.

---

Would be good if someone can sanity check that the output is actually correct. (although it looks correct to me.)

Strangely enough there is

        if isinstance(F, sage.rings.abc.AlgebraicField):
            raise NotImplementedError("This code could be implemented for QQbar, but has not been yet.")

even though when I comment that part out, the code seems to work well.

:memo: Checklist

• [x] The title is concise and informative.
• [x] The description explains in detail what this PR is about.
• [x] I have linked a relevant issue or discussion.
• [x] I have created tests covering the changes.
• [x] I have updated the documentation and checked the documentation preview.

[github-actions[bot]]

Documentation preview for this PR (built with commit 1464c6a9641ee33752365a1d9b60b174a17c5e57; changes) is ready! :tada: This preview will update shortly after each push to this PR.

[JohnCremona]

About correctness: looks reasonable to me. Over GF(31) there are only 2 5-isogenies, the others are defined over GF(31^2) and the output from that looks just like this output. Perhaps it would be safer to have the doctest just report that there are six 5-isogenies, to guard against future versions making different choices? My familiarity with the supersingular case is less than perfect! I note that of the 6 isogenous curves there are only 3 isomorphism classes, E itself (@3) another @2 and another unique.

I think it is great that this works as it should making only a trivial change to the code in isogenies_small_degree which I wrote years ago.

Can you explain the need for the new copy methods?

[user202729]

The copy is from https://github.com/sagemath/sage/pull/38994 . Basically it's needed to make it work at all because of some implementation detail.

Specifically, some part of the code requires making a new isogeny with a different pre-composed isomorphism, so it calls the internal method _set_pre_isomorphism (which mutates the isogeny (!)), but it wants a modified copy so it does deepcopy on the isogeny. Without special handling, deepcopy on the isogeny copies all the members, including the base field.

I think it's desirable for arbitrary objects to be copyable anyway, so I can't see any harm. (Or at least if it's desirable to make algebraic closure of finite field not copyable then at least raise a meaningful error, but at the moment loads(dumps(GF(p).algebraic_closure())) makes a copy anyway)

It might separately be a good idea to refactor the code to avoid mutable state in isogeny objects (easy to introduce accidental bugs), but currently it's just internal implementation detail anyway.

[S17A05]

Since this PR contains the code from #38994, which does not have its own positive review yet, it probably makes sense to close that PR and integrate the "Fixes #38988" into this PR to avoid clutter/confusion (alternatively @JohnCremona could also add a positive review to #38994)

[user202729]

Since figuring out what to do with Conway polynomial and non-unique representation of algebraic closure of finite field might take a long time, I decide to modify the thing to just use shallow copy instead.

As far as I can see this doesn't cause any trouble (the whole reason we need the copy in the first place is because _set_post_isomorphism() mutates the object, but it only mutates direct members, so it should be safe. If for some reason some future implementer __copy__ method can always be implemented for EllipticCurveIsogeny that properly copies that part)

[user202729]

Should be fixed now.

Summary:

• implement _compose_with_isomorphism() to replace _set_pre_isomorphism and _set_post_isomorphism, now isogenies are effectively immutable
• avoid calling __perform_inherentance_housekeeping from these method, because technically it's illegal to call __init__ of parent method more than once
• side change: use @cached_method to implement dual()
• side change: modify composite isogeny to detect simplification by attempt to compute the product directly and check subclass of EllipticCurveHom_composite, instead of hasattr()
• there's one behavioral change where the new code appears to be simplifying more than the old code, but I think this can't be a bad thing (see 71*1^2 changed to 71*1 and a few other similar changes)

The reason why shallow copy doesn't work is explained in https://github.com/sagemath/sage/pull/39061 . Deep copy may work eventually (when https://github.com/sagemath/sage/pull/38994 is fixed), but fundamentally we don't need a deep copy anyway.

… actually what is the pre/post isomorphism used for anyway? Can't you just adjust the internal parameters to fit the isomorphism somehow?

---

The tests are preserved to the best of my ability. Some tests in _set_pre_isomorphism and _set_post_isomorphism methods (now deleted) are moved to __set_pre_isomorphism and __set_post_isomorphism respectively.

---

On a separate note, it may be also interesting to consider making shallow copies work correctly on object types that has cached methods.

[JohnCremona]

About the pre- and post-isomorphisms: the original implementation of isogenies was done by someone who was only interested in curves over finite fields, who wanted all isogenies to be normalised (i.e. inverse image of the standard invariantdifferential on the codomain is exactly the standard differential on the domain). In reviewing that original code I pointed out that it all worked fine over arbitrary fields, for example over QQ and over number fields, but that in such situtations we don't want to restrict to normalised isogenies as instead we want to normalise the curve models, e.g. making them integral and globally inimal where possible. That led to the pre and post-isomorphism stuff being tacked on. If starting from scratch now, I am sure it would look different.

[JohnCremona]

As I gave this a positive review several months ago it would be helpful for someone to tell me what now needs to be checked, as otherwise I'll have to start again.

[JohnCremona]

@user202729 Why is your username anonymous?

[user202729]

As I gave this a positive review several months ago it would be helpful for someone to tell me what now needs to be checked, as otherwise I'll have to start again.

Several months ago you positive-review the implementation that just makes algebraic closure of finite field an identity.

In https://github.com/sagemath/sage/pull/38994 no consensus was reached (as far as I can tell), so I decide to change the implementation here that avoids the deepcopy entirely. Doing that turns out to be surprisingly difficult and requires a rather large modification.

The current situation is (as far as I remember… it's been a few months ago)

• _set_pre_isomorphism and _set_post_isomorphism is gone, instead we have _compose_with_isomorphism which returns a modified copy. So isomorphism is "more" immutable now.
  • consequently, _compose_with_isomorphism needs to do some ugly monkey patching thing to copy the attributes over. (deepcopy doesn't work.)
  • at least the positive side is __clear_cached_values is gone now, since isomorphism is immutable except at object construction.
• Of course it still need to be set at object construction, so __set_pre_isomorphism and __set_post_isomorphism remains.

I really can't see a better way to implement it without https://github.com/sagemath/sage/pull/38994 being available.

[JohnCremona]

Thanks for the explanation.

I think that the changes around line 330 (where the first error occurs in the current Sage version) are fine, but an alternative is to change line 325 to jt=f/t. (Explanation: Fricke_module(ell) = Fricke_polynomial(ell)/t and Fricke_polynomial(ell) is a monic polynomial in ZZ[t], of degree ell+1, for ell in [2,3,5,7,13].)

So in the definition of the polynomial f (defined in line 330) you could replace jt by f and kt by (f-1728*t) and leave out the coercion into R.

I think this is easier than what the current code does (my bad) which is to factor two rational functions in QQ(t) whose denominator is t and whose numerators are monic integer polynomials, pick out the factors of multiplicity 3 and 2 (which are certainly monic integer polynomials), multiply them together, getting a result whose parent is QQ[t] but which lies in ZZ[t], the coerce into ZZ[t] and then into F[t]!

Of course that is the easy part. Your work on getting the pre and post isomorphisms to work over this field was harder.