Elliptic divisibility sequence

A (nondegenerate) elliptic divisibility sequence (EDS) is a sequence of integers defined recursively by four initial values , , , , with ≠ 0 and with subsequent values determined by the formulas : \begin{align} W_{2n+1}W_1^3 &= W_{n+2}W_n^3 - W_{n+1}^3W_{n-1},\qquad n \ge 2, \\ W_{2n}W_2W_1^2 &= W_{n+2}W_n W_{n-1}^2 - W_n W_{n-2}W_{n+1}^2,\qquad n\ge 3,\\ \end{align} It can be shown that if divides each of , , and if further divides , then every term in the sequence is an integer. == Divisibility property ==

An EDS is a divisibility sequence in the sense that : m \mid n \Longrightarrow W_m \mid W_n. In particular, every term in an EDS is divisible by , so EDS are frequently normalized to have = 1 by dividing every term by the initial term. Any three integers , , with divisible by lead to a normalized EDS on setting : W_1 = 1,\quad W_2 = b,\quad W_3 = c,\quad W_4 = d. It is not obvious, but can be proven, that the condition | suffices to ensure that every term in the sequence is an integer. == General recursion ==

A fundamental property of elliptic divisibility sequences is that they satisfy the general recursion relation : W_{n+m}W_{n-m}W_r^2 = W_{n+r}W_{n-r}W_m^2 - W_{m+r}W_{m-r}W_n^2 \quad\text{for all}\quad n > m > r. (This formula is often applied with = 1 and = 1.) == Nonsingular EDS ==

The discriminant of a normalized EDS is the quantity : \Delta = W_4W_2^{15} - W_3^3W_2^{12} + 3W_4^2W_2^{10} - 20W_4W_3^3W_2^7 + 3W_4^3W_2^5 + 16W_3^6W_2^4 + 8W_4^2W_3^3W_2^2 + W_4^4. An EDS is nonsingular if its discriminant is nonzero. == Examples ==

A simple example of an EDS is the sequence of natural numbers 1, 2, 3,... . Another interesting example is 1, 3, 8, 21, 55, 144, 377, 987,... consisting of every other term in the Fibonacci sequence, starting with the second term. However, both of these sequences satisfy a linear recurrence and both are singular EDS. An example of a nonsingular EDS is : \begin{align} &1,\, 1,\, -1,\, 1,\, 2,\, -1,\, -3,\, -5,\, 7,\, -4,\, -23,\, 29,\, 59,\, 129,\\ &-314,\, -65,\, 1529,\, -3689,\, -8209,\, -16264,\dots.\\ \end{align} == Periodicity of EDS ==

A sequence is said to be periodic if there is a number so that = for every ≥ 1. If a nondegenerate EDS is periodic, then one of its terms vanishes. The smallest ≥ 1 with = 0 is called the rank of apparition of the EDS. A deep theorem of Mazur implies that if the rank of apparition of an EDS is finite, then it satisfies ≤ 10 or = 12. == Elliptic curves and points associated to EDS ==

Ward proves that associated to any nonsingular EDS () is an elliptic curve /Q and a point ε (Q) such that : W_n = \psi_n(P)\qquad\text{for all}~n \ge 1. Here ψ is the division polynomial of ; the roots of ψ are the nonzero points of order on . There is a complicated formula for and in terms of , , , and . There is an alternative definition of EDS that directly uses elliptic curves and yields a sequence which, up to sign, almost satisfies the EDS recursion. This definition starts with an elliptic curve /Q given by a Weierstrass equation and a nontorsion point ε (Q). One writes the -coordinates of the multiples of as : x(nP) = \frac{A_n}{D_n^2} \quad \text{with}~\gcd(A_n,D_n)=1~\text{and}~D_n \ge 1. Then the sequence () is also called an elliptic divisibility sequence. It is a divisibility sequence, and there exists an integer so that the subsequence ( ± ) ≥ 1 (with an appropriate choice of signs) is an EDS in the earlier sense. == Growth of EDS ==

Let be a nonsingular EDS that is not periodic. Then the sequence grows quadratic exponentially in the sense that there is a positive constant such that : \lim_{n\to\infty} \frac{\log |W_n|}{n^2} = h > 0. The number is the canonical height of the point on the elliptic curve associated to the EDS. == Primes and primitive divisors in EDS ==

It is conjectured that a nonsingular EDS contains only finitely many primes However, all but finitely many terms in a nonsingular EDS admit a primitive prime divisor. Thus for all but finitely many , there is a prime such that divides , but does not divide for all < . This statement is an analogue of Zsigmondy's theorem. == EDS over finite fields ==

An EDS over a finite field F, or more generally over any field, is a sequence of elements of that field satisfying the EDS recursion. An EDS over a finite field is always periodic, and thus has a rank of apparition . The period of an EDS over F then has the form , where and satisfy : r \le \left(\sqrt q+1\right)^2 \quad\text{and}\quad t \mid q-1. More precisely, there are elements and in F* such that : W_{ri+j} = W_j\cdot A^{ij} \cdot B^{j^2} \quad\text{for all}~i \ge 0~\text{and all}~j \ge 1. The values of and are related to the Tate pairing of the point on the associated elliptic curve. == Applications of EDS ==

Bjorn Poonen has applied EDS to logic. He uses the existence of primitive divisors in EDS on elliptic curves of rank one to prove the undecidability of Hilbert's tenth problem over certain rings of integers. Katherine E. Stange has applied EDS and their higher rank generalizations called elliptic nets to cryptography. She shows how EDS can be used to compute the value of the Weil and Tate pairings on elliptic curves over finite fields. These pairings have numerous applications in pairing-based cryptography. ==References==

• G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward. Recurrence sequences, volume 104 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2003. . (Chapter 10 is on EDS.) • R. Shipsey. Elliptic divisibility sequences . PhD thesis, Goldsmiths College (University of London), 2000. • K. Stange. Elliptic nets. PhD thesis, Brown University, 2008. • C. Swart. Sequences related to elliptic curves. PhD thesis, Royal Holloway (University of London), 2003. == External links ==