correct documentation of is_kernel_polynomial

[yyyyx4]

The documentation of is_kernel_polynomial in src/sage/schemes/elliptic_curves/isogeny_small_degree.py states that the function checks if the polynomial defines a cyclic subgroup, but cyclicity is not really tested:

sage: from sage.schemes.elliptic_curves.isogeny_small_degree import is_kernel_polynomial
sage: E = EllipticCurve([1,0])
sage: is_kernel_polynomial(E, 25, E.division_polynomial(5))
True

Also, we fix a typo (m→a) and slightly rephrase the docstring for clarity.

CC: @JohnCremona

Component: elliptic curves

Author: Lorenz Panny

Branch/Commit: public/32484 @ 8d8bd72

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

[yyyyx4]

Branch: public/32484

[yyyyx4]

Author: Lorenz Panny

[yyyyx4]

Commit: 8d8bd72

[fchapoton]

comment:3

looks good to me, but I am no expert. John, do you approve ?

[JohnCremona]

comment:4

The new text is not correct for non-cyclic isogenies: for example, the 2-division polynomial has degree 3 and is a valid kernel polynomial for the multiplication-by-2 map which has degree m=4, though [m/2]=2 not 3.

I wrote this function (at least, the original version) and its docstring, only needing it for cyclic isogenies of prime degree, though he algorithm does not require m to be prime. If you want to check for more general kernel polynomials, you will need to implement something new. For the kernel to have structure [mn,n] I think that f would have to factor as the n-division polynomial times a cyclic m-polynomial (as tested here) but you need to be very careful in case either m or n is even.

As it stands, the second part of the test (closure under multiplication maps) does check that the zeros of the polynomial form a union of subgroups (minus the identity point at infinity); the degree check was to ensure that they form a single subgroup of the correct order.

Unless you really need the more general version, I suggest changing this back (apart from the typos changing m to a in two places -- those are my fault).

[yyyyx4]

comment:5

Thanks for your comment! I agree that the new version is wrong (my bad). But just keeping the old version is wrong too:

• is_kernel_polynomial(E, 25, E.division_polynomial(5)) (not cyclic)
• is_kernel_polynomial(E, 6, E.division_polynomial(2)) (not cyclic & wrong degree!)

...both return True. The current documentation states:

Test whether E has a cyclic isogeny of degree m with kernel polynomial f.

...which means these examples should return False.

According to your comment, the fix for is_kernel_polynomial in isolation would be to simply add a restriction that m must be prime, as that has always been an assumption of the code anyway. However, the EllipticCurveIsogeny constructor calls is_kernel_polynomial with composite degrees (this was apparently introduced in #23222), which is incorrect at the moment and would obviously break if we started enforcing m.is_prime() now. So, it seems the only real way out is to generalize is_kernel_polynomial to arbitrary subgroups? (I don't mind writing some code, if this is what we want.)

Here's an example where the current situation can actually lead to a wrong isogeny:

sage: E = EllipticCurve(GF(71^2), [0,1])
sage: R.<x> = E.base_field()[]
sage: h = x^4 + 26*x^3 + 61*x^2 + 4*x + 19
sage: psi = E.isogeny(h)
sage: psi.domain().is_isogenous(psi.codomain())
False

(The subset defined by this h can be identified with {(0,0), (3,0),(6,0), (0,1),(0,2),(0,4),(0,5),(0,7),(0,8)} under an isomorphism E[9] ≅ ℤ/9 × ℤ/9. Notice in particular that this is not a union of subgroups.)

[JohnCremona]

comment:6

You are right, and I agree that the best fix is to make this work for all possible subgroups. If you write the code I will be happy to review it. Perhaps we could have a function which does not take m as a paramter, just f, which returns a positive integer m if the argument defines a subgroup of order m and 0 if it does not define a subgroup, and/or have a special case for cyclic kernels is_cyclic_kernel_polynomial?