#30199 closed enhancement (fixed)

Prime degree isogeny (di)graphs of elliptic curves

Reported by: gh-marcbn Owned by:
Priority: major Milestone: sage-9.3
Component: elliptic curves Keywords:
Cc: defeo, cremona Merged in:
Authors: Marc Newman Reviewers: Luca De Feo
Report Upstream: N/A Work issues:
Branch: 89274a6 (Commits, GitHub, GitLab) Commit: 89274a683e6bd63ec922762f5a6e6cc9c1bbe921
Dependencies: Stopgaps:

Status badges

Description (last modified by chapoton)

Given an elliptic curve E and a prime l, this code outputs the graph or digraph object representing the l-degree isogeny (di)graph containing E with vertices isomorphism classes of curves labelled by either an equation of a representative curve or the associated j-invariant.

This is functionality similar to the ticket #16942

Change History (23)

comment:1 Changed 17 months ago by gh-marcbn

  • Authors set to Marc Newman
  • Component changed from PLEASE CHANGE to elliptic curves
  • Description modified (diff)
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 17 months ago by gh-marcbn

  • Branch set to u/gh-marcbn/prime_degree_isogeny__di_graphs_of_elliptic_curves

comment:3 Changed 17 months ago by defeo

  • Cc defeo added
  • Commit set to 72d8cf3136c47305b466a0a8b620ec10811044af

New commits:

abc9c6fSeparate equation string construction from _repr_ method
72d8cf3Add prime_isogeny_graph method

comment:4 Changed 15 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:5 Changed 14 months ago by chapoton

  • Cc cremona added
  • the doctest is not correctly formatted, missing :: at the end of lines preceding doctests blocks
  • the changes about _repr_ of elliptic curves are not useful and could be undone

comment:6 Changed 14 months ago by chapoton

  • Description modified (diff)

comment:7 Changed 14 months ago by git

  • Commit changed from 72d8cf3136c47305b466a0a8b620ec10811044af to b8e086208a0ea7a6333096a7711075ecf8df1fce

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

b8e0862Fix doctest formatting

comment:8 Changed 14 months ago by gh-marcbn

I fixed the doctest formatting. However, with regards to the _repr_ changes, the curve equation is needed as a string to label the vertices and it seemed like the best way to get that was to separate that part out from the _repr_ method instead of--for example--duplicating the code for assembling that equation string or extracting it from the full _repr_ output.

So instead of pulling the _equation_string method out of the _repr_ method, what would your recommendation for getting that curve equation string be?

Thanks!

comment:9 Changed 12 months ago by defeo

Hi Marc,

Apologies for the dealy. This is excellent quality code, thanks! I'm not sure what chapoton was suggesting to do about _repr_, yours looks like the best choice to me (one may take the chance to simplify the printing code, btw, but that's not a necessity).

Some minor remarks:

  • You could use sparse=True, or even data_strcture=static_sparse as parameter for the graph constructor, since users are likely to want to construct large graphs with small degree.
  • The two lines
    b = self.ainvs()
    a = [z._coeff_repr() for z in b]
    

in _repr_ seem unncessary now.

  • On my server it takes ~30s to construct a supersingular 2-graph with ~1000 vertices, ~60s for the 3-graph, ~300s for the 5-graph. Maybe you could adjust curve_max depending on l (e.g., 3-4 increments). Also, the warning message could be more explicit, e.g.: Isogeny graph contains more than x curves.
  • Maybe the name isogeny_graph_prime_degree or isogeny_ell_graph is more easily discoverable than prime_isogeny_graph.

Finally, a question: have you thought about the ordering of the outputs in the doctests? I assume Graph prints the vertices in the order they appear in the adjacency matrix, but what about edges? Is the ordering explicitly defined, or is there a risk that the doctests break at some future Sage release?

If you can solve these points, I'm happy to give positive review.

comment:10 Changed 12 months ago by git

  • Commit changed from b8e086208a0ea7a6333096a7711075ecf8df1fce to fec79b9f9fa7d940e1665aacc67485d9ba51f16a

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

9b24903Removed old lines from _repr_ function
aa3accbAdded different curve_max values given l; changed user warning message
fec79b9Changed method name

comment:11 Changed 12 months ago by gh-marcbn

Hi Luca,

I updated the code as you requested. A few things:

  • I cleaned up those two lines, used static_sparse for the graph, and changed the method name to isogeny_ell_graph.
  • For the multiple curve_max values: on my laptop, the warning is generally output after ~20 seconds. However, when l is large, the warning will only fire after E.isogenies_prime_degree(l) returns which can take a while for big l values.
  • It seems like as long as the vertex labels are all comparable (which they are in this case), the edge order will be consistent.
  • However, when labelling the vertices with the curve equation (as opposed to the j-invariant) the ordering of the vertices when generating the graph could matter (since multiple isomorphic curve equations exist). The vertex and edge order depends on the order of the isogenies returned by isogenies_prime_degree, the documentation for which does not explicitly specify an ordering. So, if that method/algorithm is changed in such a way that the order of the returned isogenies changes, there is the chance that the tests for this will fail if walking the graph in one way results in different (but isomorphic) curve equations than walking it in another way. Similarly, there is also a risk where some change to isogenies_prime_degree causes the method to return isogenies to curves isomorphic to what is currently being returned. I'm not sure if it is appropriate to complicate the code here in order to prevent possible future test failures caused by changes which may or may not ever occur. I can think about how to best do this if you think it's worthwhile though. Let me know.

Thanks!

comment:12 Changed 12 months ago by cremona

I am only following this ticket from a distance, but am probably responsible for having written isogenies_prime_degree. This was done for my own needs, for elliptic curves over number fields, where the prime degrees are never large, and the code is absolutely not intended to be used for large prime degrees -- it will then involve computing and factoring the l-division polynomial, which has degree (l2-1)/2. If you need to run it for larger primes then you will want to implement something better.

I see no problem in making a change to the order of the output of this function, other than the usual one -- some doctests will fail.

Also, it is the case that automorphisms of prime degree, when they exist, will cause some of the isogenies computed by this function to have codomain isomorphic to the domain. This is entirely correct. If you don't want them then filter the output of the function, please do not change the function.

comment:13 Changed 12 months ago by defeo

  • Reviewers set to Luca De Feo
  • Status changed from new to needs_review

Hi Marc, thanks for the changes. Regarding the doctesting framework, I don't think you need to account for isogenies_prime_degree returning random results:

  • The doctesting code of isogenies_prime_degree itself would break if it was non-deterministic, so there is an implicit assumption of determinism there.
  • If someone changes the code of isogenies_prime_degree, then they will have to update the doctests for that function and this one. I don't think that's asking too much.

What would have been unreasonable, is asking someone who changes the code in sage.graphs to touch up the doctests here. But if sage.graphs respects some ordering, then we have a deal with sage.graphs.

@John, Marc's code takes properly into account the multiple edges for j=0,1728. And, yes, we shouldn't worry about large l, this code is meant to be called with small l. If someone wants large degree isogeny graphs, that's their problem.

Thanks Marc, and thanks John for writing the original isogenies_prime_degree. I'm giving positive review (Marc, I just noticed you should have checked "needs review" a long time ago).

comment:14 Changed 12 months ago by defeo

  • Status changed from needs_review to positive_review

comment:15 follow-ups: Changed 12 months ago by dcoudert

Hello,

to avoid some future work to clean the code, I suggest to fix some minor points in the coding style (pep8):

  • no dot at the end of the short sentence
    -        - ``l`` -- prime degree of isogenies.
    +        - ``l`` -- prime degree of isogenies
    
  • the convention for parameters is like:
    -        - ``directed`` (default True) -- return a directed graph if ``True``;
    -          otherwise return an undirected graph.  In the undirected case, the
    +        - ``directed`` -- boolean (default: ``True``); whether to return
    +           a directed or an undirected graph. In the undirected case, the
              in-degrees and out-degrees of the vertices must be balanced and
              therefore the number of out-edges from the vertices corresponding to
              j-invariants 0 and 1728 (if they are part of the graph) are reduced
              to match the number of in-edges.
    

In particular, always use ``True``, ``False``, ```None``

  • at least 2 spaces before # and one after, for instance
    -                m = len(E.automorphisms()) / 2 #multiplicity of out-edges
    +                m = len(E.automorphisms()) / 2  # multiplicity of out-edges
    

And finally, there is no need for a loop here

-                while s in labels: s += "*"
+                s += "*" * len(labels)

comment:16 in reply to: ↑ 15 Changed 12 months ago by defeo

Replying to dcoudert:

And finally, there is no need for a loop here

-                while s in labels: s += "*"
+                s += "*" * len(labels)

Uh? No, that's not equivalent. That's only adding as many * as necssary to make a unique label.

Arguably, I don't think it's possible to have a j-invariant appear more than twice in any isogeny graph (as usual, one should check for j=0,1728), so

    if s in labels: s += "*"

would likely suffice, however I see no harm in the while loop.

comment:17 Changed 12 months ago by dcoudert

Right. I confused myself. Sorry.

comment:18 Changed 12 months ago by git

  • Commit changed from fec79b9f9fa7d940e1665aacc67485d9ba51f16a to 4b59634af076914604064774b8ed1fdc1497df00
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

4b59634Cleaned up comments and documentation

comment:19 in reply to: ↑ 15 Changed 12 months ago by gh-marcbn

Replying to dcoudert:

to avoid some future work to clean the code, I suggest to fix some minor points in the coding style (pep8):

I got this cleaned up as suggested (but left the while loop as is). Let me know if there is any other cleanup necessary.

comment:20 Changed 12 months ago by dcoudert

another minor one.

-                while s in labels: s += "*"
+                while s in labels:
+                    s += "*"

comment:21 Changed 12 months ago by git

  • Commit changed from 4b59634af076914604064774b8ed1fdc1497df00 to 89274a683e6bd63ec922762f5a6e6cc9c1bbe921

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

89274a6Added line break to while loop

comment:22 Changed 12 months ago by gh-marcbn

  • Status changed from needs_review to positive_review

comment:23 Changed 11 months ago by vbraun

  • Branch changed from u/gh-marcbn/prime_degree_isogeny__di_graphs_of_elliptic_curves to 89274a683e6bd63ec922762f5a6e6cc9c1bbe921
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.