In reading "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES" by Rostovtsev and Stolbunov, they claim on page 8 that the set $U=\{E_i(\mathbb{F}_p)\}$ of elliptic curves with a specific prime $l$ form a "branchless cycle".
For some context,
- $U$ is a set of elliptic curves, each one being a uniquely determined by a $j$-invariant.
- $l$ is a prime such that the Kronecker symbol $\left(\frac{D_\pi}{l}\right)=1$, and $D_\pi$ is the Frobenius discriminant (which is common among all the elliptic curves in $U$ because they are all isogenous by Tate's theorem).
Kohel (Theorem 2 in paper) showed that if an elliptic curve has $D_\pi$ and $l$ satisfying $\left(\frac{D_\pi}{l}\right)=1$, then there are exactly two $l$-degree isogenies from $E$.
Now this implies $U$ is $2$-regular, but why does the following statement hold:
It is practically determined that, when $\#U$ is prime, all the elements of $U$ form a single isogeny cycle.
If $\#U=7$ can't we have two disjoint cycles of size $3$ and $4$? And why must $\#U$ be prime?
Cross-post: https://mathoverflow.net/questions/467175/why-do-we-get-a-connected-2-regular-graph
Answered on MO (MathOverflow) https://mathoverflow.net/questions/467175/why-do-we-get-a-connected-2-regular-graph/467743#467743.
The construction makes $U$ the Cayley graph associated to an abelian group $G$ and a pair $\pm g$ of elements of $G$. In such a graph all the components are cycles of the same length, namely the order of $g$, call it $|g|$. Thus $|g|$ is a factor of $|G|$ (this is also part of Lagrange's theorem). In particular if $|G|$ is prime and $g$ is not the identity element then $|g| = |G|$ and the graph is a single $|G|$-cycle.
See the MO answer for further information.