Opened 17 months ago
Closed 11 months ago
#30199 closed enhancement (fixed)
Prime degree isogeny (di)graphs of elliptic curves
Reported by:  ghmarcbn  Owned by:  

Priority:  major  Milestone:  sage9.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: 
Description (last modified by )
Given an elliptic curve E and a prime l, this code outputs the graph or digraph object representing the ldegree isogeny (di)graph containing E with vertices isomorphism classes of curves labelled by either an equation of a representative curve or the associated jinvariant.
This is functionality similar to the ticket #16942
Change History (23)
comment:1 Changed 17 months ago by
 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
 Branch set to u/ghmarcbn/prime_degree_isogeny__di_graphs_of_elliptic_curves
comment:3 Changed 17 months ago by
 Cc defeo added
 Commit set to 72d8cf3136c47305b466a0a8b620ec10811044af
comment:4 Changed 15 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:5 Changed 14 months ago by
 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
 Description modified (diff)
comment:7 Changed 14 months ago by
 Commit changed from 72d8cf3136c47305b466a0a8b620ec10811044af to b8e086208a0ea7a6333096a7711075ecf8df1fce
Branch pushed to git repo; I updated commit sha1. New commits:
b8e0862  Fix doctest formatting

comment:8 Changed 14 months ago by
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 offor exampleduplicating 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
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 evendata_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 2graph with ~1000 vertices, ~60s for the 3graph, ~300s for the 5graph. Maybe you could adjust
curve_max
depending onl
(e.g., 34 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
orisogeny_ell_graph
is more easily discoverable thanprime_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
 Commit changed from b8e086208a0ea7a6333096a7711075ecf8df1fce to fec79b9f9fa7d940e1665aacc67485d9ba51f16a
comment:11 Changed 12 months ago by
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 toisogeny_ell_graph
.  For the multiple
curve_max
values: on my laptop, the warning is generally output after ~20 seconds. However, whenl
is large, the warning will only fire afterE.isogenies_prime_degree(l)
returns which can take a while for bigl
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 jinvariant) 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 toisogenies_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
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 ldivision polynomial, which has degree (l^{21)/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
 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 nondeterministic, 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
 Status changed from needs_review to positive_review
comment:15 followups: ↓ 16 ↓ 19 Changed 12 months ago by
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 indegrees and outdegrees of the vertices must be balanced and therefore the number of outedges from the vertices corresponding to jinvariants 0 and 1728 (if they are part of the graph) are reduced to match the number of inedges.
In particular, always use ``True``
, ``False``
, ```None``
 at least 2 spaces before
#
and one after, for instance m = len(E.automorphisms()) / 2 #multiplicity of outedges + m = len(E.automorphisms()) / 2 # multiplicity of outedges
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
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 jinvariant 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
Right. I confused myself. Sorry.
comment:18 Changed 12 months ago by
 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:
4b59634  Cleaned up comments and documentation

comment:19 in reply to: ↑ 15 Changed 12 months ago by
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
another minor one.
 while s in labels: s += "*" + while s in labels: + s += "*"
comment:21 Changed 12 months ago by
 Commit changed from 4b59634af076914604064774b8ed1fdc1497df00 to 89274a683e6bd63ec922762f5a6e6cc9c1bbe921
Branch pushed to git repo; I updated commit sha1. New commits:
89274a6  Added line break to while loop

comment:22 Changed 12 months ago by
 Status changed from needs_review to positive_review
comment:23 Changed 11 months ago by
 Branch changed from u/ghmarcbn/prime_degree_isogeny__di_graphs_of_elliptic_curves to 89274a683e6bd63ec922762f5a6e6cc9c1bbe921
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Separate equation string construction from _repr_ method
Add prime_isogeny_graph method