- Source: Elliptic divisibility sequence
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
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.
Definition
A (nondegenerate) elliptic divisibility sequence (EDS) is a sequence of integers (Wn)n ≥ 1
defined recursively by four initial values
W1, W2, W3, W4,
with W1W2W3 ≠ 0 and with subsequent values determined by the formulas
W
2
n
+
1
W
1
3
=
W
n
+
2
W
n
3
−
W
n
+
1
3
W
n
−
1
,
n
≥
2
,
W
2
n
W
2
W
1
2
=
W
n
+
2
W
n
W
n
−
1
2
−
W
n
W
n
−
2
W
n
+
1
2
,
n
≥
3
,
{\displaystyle {\begin{aligned}W_{2n+1}W_{1}^{3}&=W_{n+2}W_{n}^{3}-W_{n+1}^{3}W_{n-1},\qquad n\geq 2,\\W_{2n}W_{2}W_{1}^{2}&=W_{n+2}W_{n}W_{n-1}^{2}-W_{n}W_{n-2}W_{n+1}^{2},\qquad n\geq 3,\\\end{aligned}}}
It can be shown that if W1 divides each of W2, W3, W4 and if further W2 divides W4, then every term Wn in the sequence is an integer.
An EDS is a divisibility sequence in the sense that
m
∣
n
⟹
W
m
∣
W
n
.
{\displaystyle m\mid n\Longrightarrow W_{m}\mid W_{n}.}
In particular, every term in an EDS is divisible by W1, so
EDS are frequently normalized to have W1 = 1 by dividing every term by the initial term.
Any three integers b, c, d
with d divisible by b lead to a normalized EDS on setting
W
1
=
1
,
W
2
=
b
,
W
3
=
c
,
W
4
=
d
.
{\displaystyle 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 b | d 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
for all
n
>
m
>
r
.
{\displaystyle 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 r = 1 and W1 = 1.)
Nonsingular EDS
The discriminant of a normalized EDS is the quantity
Δ
=
W
4
W
2
15
−
W
3
3
W
2
12
+
3
W
4
2
W
2
10
−
20
W
4
W
3
3
W
2
7
+
3
W
4
3
W
2
5
+
16
W
3
6
W
2
4
+
8
W
4
2
W
3
3
W
2
2
+
W
4
4
.
{\displaystyle \Delta =W_{4}W_{2}^{15}-W_{3}^{3}W_{2}^{12}+3W_{4}^{2}W_{2}^{10}-20W_{4}W_{3}^{3}W_{2}^{7}+3W_{4}^{3}W_{2}^{5}+16W_{3}^{6}W_{2}^{4}+8W_{4}^{2}W_{3}^{3}W_{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 (sequence A006709 in the OEIS) 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 (sequence A006769 in the OEIS)
1
,
1
,
−
1
,
1
,
2
,
−
1
,
−
3
,
−
5
,
7
,
−
4
,
−
23
,
29
,
59
,
129
,
−
314
,
−
65
,
1529
,
−
3689
,
−
8209
,
−
16264
,
…
.
{\displaystyle {\begin{aligned}&1,\,1,\,-1,\,1,\,2,\,-1,\,-3,\,-5,\,7,\,-4,\,-23,\,29,\,59,\,129,\\&-314,\,-65,\,1529,\,-3689,\,-8209,\,-16264,\dots .\\\end{aligned}}}
Periodicity of EDS
A sequence (An)n ≥ 1 is said to be periodic
if there is a number N ≥ 1 so
that An+N = An for every n ≥ 1.
If a nondegenerate EDS (Wn)n ≥ 1
is periodic, then one of its terms vanishes. The smallest r ≥ 1 with Wr = 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 r ≤ 10 or r = 12.
Elliptic curves and points associated to EDS
Ward proves that associated to any nonsingular EDS (Wn)
is an elliptic curve E/Q and a point
P ε E(Q) such that
W
n
=
ψ
n
(
P
)
for all
n
≥
1.
{\displaystyle W_{n}=\psi _{n}(P)\qquad {\text{for all}}~n\geq 1.}
Here ψn is the
n division polynomial
of E; the roots of ψn are the
nonzero points of order n on E. There is
a complicated formula
for E and P in terms of W1, W2, W3, and W4.
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 E/Q given by a Weierstrass equation and a nontorsion point P ε E(Q). One writes the x-coordinates of the multiples of P as
x
(
n
P
)
=
A
n
D
n
2
with
gcd
(
A
n
,
D
n
)
=
1
and
D
n
≥
1.
{\displaystyle x(nP)={\frac {A_{n}}{D_{n}^{2}}}\quad {\text{with}}~\gcd(A_{n},D_{n})=1~{\text{and}}~D_{n}\geq 1.}
Then the sequence (Dn) is also called an elliptic divisibility sequence. It is a divisibility sequence, and there exists an integer k so that the subsequence ( ±Dnk )n ≥ 1 (with an appropriate choice of signs) is an EDS in the earlier sense.
Growth of EDS
Let (Wn)n ≥ 1 be a nonsingular EDS
that is not periodic. Then the sequence grows quadratic exponentially in the sense that there is
a positive constant h such that
lim
n
→
∞
log
|
W
n
|
n
2
=
h
>
0.
{\displaystyle \lim _{n\to \infty }{\frac {\log |W_{n}|}{n^{2}}}=h>0.}
The number h 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 n,
there is a prime p such that p divides Wn, but p does not divide Wm for all m < n. This statement is an analogue of Zsigmondy's theorem.
EDS over finite fields
An EDS over a finite field Fq, 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 r. The period of an EDS over Fq then has the form rt, where r and t satisfy
r
≤
(
q
+
1
)
2
and
t
∣
q
−
1.
{\displaystyle r\leq \left({\sqrt {q}}+1\right)^{2}\quad {\text{and}}\quad t\mid q-1.}
More precisely, there are elements A and B in Fq* such that
W
r
i
+
j
=
W
j
⋅
A
i
j
⋅
B
j
2
for all
i
≥
0
and all
j
≥
1.
{\displaystyle W_{ri+j}=W_{j}\cdot A^{ij}\cdot B^{j^{2}}\quad {\text{for all}}~i\geq 0~{\text{and all}}~j\geq 1.}
The values of A and B 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
Further material
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. ISBN 0-8218-3387-1. (Chapter 10 is on EDS.)
R. Shipsey. Elliptic divisibility sequences Archived 2011-06-09 at the Wayback Machine. 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
Graham Everest's EDS web page. Archived 2009-04-11 at the Wayback Machine
Prime Values of Elliptic Divisibility Sequences.
Lecture on p-adic Properites of Elliptic Divisibility Sequences.
Kata Kunci Pencarian:
6.838
7.433
No More Posts Available.
No more pages to load.
