In mathematics, an elliptic divisibility sequence (EDS) is a sequence of integers satisfying a nonlinear recursion relation arising from division polynomials on elliptic curves. EDS were first defined, and their arithmetic properties studied, by Morgan Ward[1] in the 1940s. They attracted only sporadic attention until around 2000, when EDS were taken up as a class of nonlinear recurrences that are more amenable to analysis than most such sequences. This tractability is due primarily to the close connection between EDS and elliptic curves. In addition to the intrinsic interest that EDS have within number theory, EDS have applications to other areas of mathematics including logic and cryptography.
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} W2n+1
3 | |
W | |
1 |
&=Wn+2
3 | |
W | |
n |
-
3W | |
W | |
n-1 |
, n\ge2,\\ W2nW2W
2 | |
1 |
&=Wn+2Wn
2 | |
W | |
n-1 |
-WnWn-2
2, | |
W | |
n+1 |
n\ge3,\\ \end{align}
It can be shown that if divides each of,, and if further divides, then every term in the sequence is an integer.
An EDS is a divisibility sequence in the sense that
m\midn\LongrightarrowWm\midWn.
Any three integers,, with divisible by lead to a normalized EDS on setting
W1=1, W2=b, W3=c, W4=d.
A fundamental property of elliptic divisibility sequencesis that they satisfy the general recursion relation
Wn+mWn-m
2 | |
W | |
r |
=Wn+rWn-r
2 | |
W | |
m |
-Wm+rWm-r
2 | |
W | |
n |
forall n>m>r.
The discriminant of a normalized EDS is the quantity
\Delta=W4W
15 | |
2 |
-
12 | |
W | |
2 |
+
10 | |
3W | |
2 |
-20W4W
7 | |
2 |
+
5 | |
3W | |
2 |
+
4 | |
16W | |
2 |
+
2 | |
8W | |
2 |
+
4. | |
W | |
4 |
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,....\\ \end{align}
A sequence is said to be periodicif there is a number sothat = 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[2] implies that if the rank of apparition of an EDS is finite, then it satisfies ≤ 10 or = 12.
Ward proves that associated to any nonsingular EDS is an elliptic curve /Q and a point ε (Q) such that
Wn=\psin(P) forall~n\ge1.
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)=
An | ||||||
|
with~\gcd(An,Dn)=1~and~Dn\ge1.
Let be a nonsingular EDSthat is not periodic. Then the sequence grows quadratic exponentially in the sense that there isa positive constant such that
\limn\toinfty
log|Wn| | |
n2 |
=h>0.
It is conjectured that a nonsingular EDS contains only finitely many primes[4] However, all but finitely many terms in a nonsingular EDS admit a primitive prime divisor.[5] 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.
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(\sqrtq+1\right)2 and t\midq-1.
Wri+j=Wj ⋅ Aij ⋅
j2 | |
B |
forall~i\ge0~andall~j\ge1.
Bjorn Poonen[6] 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[7] has applied EDS and their higher rank generalizations called elliptic netsto cryptography. She shows how EDS can be used to compute the valueof the Weil and Tate pairings on elliptic curves over finitefields. These pairings have numerous applications in pairing-based cryptography.