Graphs of endomorphisms of elliptic curves over finite fields

Abstract

There is a growing body of research on dynamics of maps over finite sets; such a map f : X → X is described by a finite directed graph with vertex set X and edges from x ∈ X to f(x) ∈ X. In general one finds that maps with algebraic properties give more symmetrical graphs than random graphs. In this context, we study endomorphisms of ordinary elliptic curves over finite fields with endomorphism ring equal to the maximal order of a quadratic number field. We translate the graph theory problem into an algebraic number-theoretic one. We use the theory of rational maps by x-coordinate projection of endomorphisms by Ugolini, and on dynamics of Dedekind domains by Qureshi and Reis, to derive precisely the cycles and trees that the graphs consist of. Next, we look at the curve E : y^2 = x^3 − x over Fp to apply this theory. We run some computer experiments for endomorphisms α = a ± bi with 1 ≤ a, b ≤ 9 for the first 1000 prime numbers where E is ordinary. We look at two invariants: the number of points in cycles and the maximal cycle length. We study the proportion of points in cycles, looking at the density of primes where this proportion is maximal. Using congruence relations, we find a lower bound for endomorphisms which do not contain split primes. We also find more general results concerning the proportion of points experimentally. Next, we look at the proportion of cyclic points that are contained in the maximal cycle. We study experimentally how the proportion behaves as p increases in size; and find a big difference in the case where the norm of the endomorphism is even or odd. Further, we look into when the proportion is maximal. In the even case, the maximum proportion is 1; in the odd case it is < 1. For the odd case, we give a conjecture describing the value of the maximum proportion as a function of the endomorphism, which we base on the experimental data and on the case where the graph has only a minimal number of points.