Implement kernel_points and inverse_image for elliptic curve hom #40251

user202729 · 2025-06-13T11:21:47Z

Ideally I want to implement .kernel_gens() (and eventually .kernel()) but that requires a lot of framework (subgroup of E.abelian_group(), etc.)

Also it may be possible to use a more efficient algorithm for EllipticCurveHom_composite, but I haven't worked out the math yet. (if you're lucky then taking the inverse image over each successtive φ works, but otherwise…) Currently it takes successive image, but might have bad worst case behavior.

📝 Checklist

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

⌛ Dependencies

github-actions · 2025-06-13T12:07:02Z

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

…om-inverse

tscrim

A bunch of minor things.

src/sage/schemes/elliptic_curves/hom_composite.py

src/sage/schemes/elliptic_curves/hom.py

tscrim · 2025-07-01T04:04:33Z

src/sage/schemes/elliptic_curves/hom.py

+        if Q not in self.codomain():
+            raise TypeError('input must be a point in the codomain')


Should we explicitly cast Q to the codomain? For example, 2/2 in ZZ but it is not an integer.

__contains__ implementation of EllipticCurve checks isinstance(Q, EllipticCurveModel) and Q.curve() == self if I recalled correctly, so I think this does what it should.

Actually you're right, the current behavior is like this

sage: f.inverse_image((0, 2)) --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) ... AttributeError: 'tuple' object has no attribute 'is_zero'

on the other hand,

sage: f.codomain().coerce((0, 2)) --------------------------------------------------------------------------- TypeError Traceback (most recent call last) ... TypeError: no canonical coercion from <class 'tuple'> to Elliptic Curve defined by ...

it's not ideal to directly convert the point, since the zero point in any elliptic curve can be converted into the zero point in any other elliptic curve. I decide to cast it after checking Q in self.codomain().

New behavior:

sage: f.inverse_image((0, 2)) (2 : 3*z2 + 1 : 1)

Or maybe it's a good idea to make conversion not work for the wrong curve, or __contains__ not work for tuple? After all the documentation says

def __contains__(self, P): """ Return ``True`` if and only if P is a point on the elliptic curve. P just has to be something that can be coerced to a point.

see "coerced", not "converted". Yet the implementation converts.

There isn't necessarily anything wrong with it using conversion to check (yes, the doc should be changed). Well, I'm not sure what the best course of action is here as I don't use this code. John is a very good person to ask about this.

I think that using contains as a test is fine. If E1 and E2 are different curves then "E1(0) in E2" is False.

src/sage/schemes/elliptic_curves/hom.py

JohnCremona · 2025-07-01T08:36:55Z

I noticed this PR just when I was myself computing some inverse images under isogenies, so thanks!

For what I was doing I would need an option extend=True. Perhaps we can mae that a new issue, I would not want to delay this one. It's not an obvious extension since even for the x-coordinates, the roots will in general lie in different fields.

JohnCremona

Nothing to add beyond what @tscrim has already said. Good!

user202729 · 2025-07-01T23:51:40Z

I realize there's a bug that if you just call any_root(), you get some x-coordinate that lies in the field but there's no guarantee that the y-coordinate is also in the field (in fact there isn't and previously sometimes the assertion fails). I fallback to roots() instead.

JohnCremona · 2025-07-02T08:29:55Z

I realize there's a bug that if you just call any_root(), you get some x-coordinate that lies in the field but there's no guarantee that the y-coordinate is also in the field (in fact there isn't and previously sometimes the assertion fails). I fallback to roots() instead.

That is a good catch, which I should have noticed before yesterday's comment.

You might find it helpful to look at the code (which I wrote) for Q.division_points(n) which returns a list of P satisfying nP=Q. That's a specical case of what this function is doing. That code does look at every root x and tries to lift to (x,y). Now if 2Q=0 then both y's are valid solutions, while otherwise at most one is, and you may need to check both to see which one works.

user202729 · 2025-07-02T11:27:23Z

I took a look. The only difference with the current implementation is the check of is 2 torsion, but I think that check is not particularly useful, at best it saves 1-2 evaluation of the morphism at the cost of computing _neg_ to check for 2-torsion. Finding root is likely more expensive anyway.

sagemathgh-40251: Implement kernel_points and inverse_image for elliptic curve hom Ideally I want to implement `.kernel_gens()` (and eventually `.kernel()`) but that requires a lot of framework (subgroup of `E.abelian_group()`, etc.) Also it may be possible to use a more efficient algorithm for `EllipticCurveHom_composite`, but I haven't worked out the math yet. (if you're lucky then taking the inverse image over each successtive `φ` works, but otherwise…) Currently it takes successive image, but might have bad worst case behavior. ### 📝 Checklist  - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [ ] I have linked a relevant issue or discussion. - [x] I have created tests covering the changes. - [ ] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies    URL: sagemath#40251 Reported by: user202729 Reviewer(s): John Cremona, Travis Scrimshaw, user202729

yyyyx4 · 2025-07-23T16:07:43Z

By the way, implementing a .kernel_gens() method on top of this is very easy: There is an AdditiveAbelianGroupWrapper.from_generators() method, and from there you can just extract a basis of the group. It's not the most efficient implementation, but it gets the job done, and optimizations can always come later.

user202729 · 2025-07-23T16:14:50Z

Cool. (I haven't looked into what algoithm it uses internally yet, but i the group order is highly composite then it should be polynomial time. Possibly with high exponent.)

If the group object exists, it would be more consistent to implement it as .kernel() of the hom object.

(then .kernel_points() as is would be bad API, since it should be accessible by iter(f.kernel()). still, I think if the latter is sufficiently efficiently implemented, then having .kernel_points() implemented as return iter(self.kernel()) isn't too bad.)

yyyyx4 · 2025-07-23T16:25:19Z

The .from_generators() method is definitely polynomial-time in the prime divisors of the order (here: isogeny degree). What I meant with "not the most efficient" is that it is a bit wasteful to enumerate the entire kernel, only to extract just one or two points from the list. In the most common case (cyclic isogenies), it would be more favorable to look for a single root of the kernel polynomial right away whose associated point generates the kernel, and the generalization to non-cyclic isogenies should be easy enough as well.

Implement kernel_points and inverse_image for elliptic curve hom

563596f

user202729 requested a review from JohnCremona June 13, 2025 11:30

user202729 added 2 commits June 27, 2025 20:14

Merge remote-tracking branch 'upstream/develop' into elliptic-curve-h…

88deab1

…om-inverse

Improve inverse_image for hom_composite

6ea2a8c

github-actions bot added the s: needs review label Jun 27, 2025

tscrim requested changes Jul 1, 2025

View reviewed changes

JohnCremona approved these changes Jul 1, 2025

View reviewed changes

user202729 added 5 commits July 1, 2025 18:30

Apply suggested changes

0e34ccb

Make inverse_image(tuple) behave correctly

18f79fb

Add coverage test

7a14182

Fix failing test

d28e303

Fix a bug, add a stress test

5397a01

Add some links

b6176fe

JohnCremona approved these changes Jul 2, 2025

View reviewed changes

user202729 added s: positive review and removed s: needs review labels Jul 4, 2025

user202729 mentioned this pull request Jul 14, 2025

detect unsolvable systems when solving integer linear systems #40211

Merged

vbraun merged commit fa1479e into sagemath:develop Jul 25, 2025
23 of 25 checks passed

github-actions bot removed the s: positive review label Jul 25, 2025

user202729 mentioned this pull request Aug 16, 2025

Compute kernel of sum morphism of elliptic curve intelligently #40601

Open

1 task

		if Q not in self.codomain():
		raise TypeError('input must be a point in the codomain')

Uh oh!

Implement kernel_points and inverse_image for elliptic curve hom #40251

Implement kernel_points and inverse_image for elliptic curve hom #40251

Uh oh!

Conversation

user202729 commented Jun 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

📝 Checklist

⌛ Dependencies

Uh oh!

github-actions bot commented Jun 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tscrim left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

tscrim Jul 1, 2025

Choose a reason for hiding this comment

Uh oh!

user202729 Jul 1, 2025

Choose a reason for hiding this comment

Uh oh!

user202729 Jul 1, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tscrim Jul 2, 2025

Choose a reason for hiding this comment

Uh oh!

JohnCremona Jul 2, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

JohnCremona commented Jul 1, 2025

Uh oh!

JohnCremona left a comment

Choose a reason for hiding this comment

Uh oh!

user202729 commented Jul 1, 2025

Uh oh!

JohnCremona commented Jul 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

user202729 commented Jul 2, 2025

Uh oh!

yyyyx4 commented Jul 23, 2025

Uh oh!

user202729 commented Jul 23, 2025

Uh oh!

yyyyx4 commented Jul 23, 2025

Uh oh!

Uh oh!

Uh oh!

user202729 commented Jun 13, 2025 •

edited

Loading

github-actions bot commented Jun 13, 2025 •

edited

Loading

user202729 Jul 1, 2025 •

edited

Loading

JohnCremona commented Jul 2, 2025 •

edited

Loading