Английская Википедия:Elliptic divisibility sequence
Шаблон:Short description 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.
Definition
A (nondegenerate) elliptic divisibility sequence (EDS) is a sequence of integers Шаблон:Math defined recursively by four initial values Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math, with Шаблон:Math ≠ 0 and with subsequent values determined by the formulas
- <math>
\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}
</math>
It can be shown that if Шаблон:Math divides each of Шаблон:Math, Шаблон:Math, Шаблон:Math and if further Шаблон:Math divides Шаблон:Math, then every term Шаблон:Math in the sequence is an integer.
Divisibility property
An EDS is a divisibility sequence in the sense that
- <math>
m \mid n \Longrightarrow W_m \mid W_n.
</math> In particular, every term in an EDS is divisible by Шаблон:Math, so EDS are frequently normalized to have Шаблон:Math = 1 by dividing every term by the initial term.
Any three integers Шаблон:Math, Шаблон:Math, Шаблон:Math with Шаблон:Math divisible by Шаблон:Math lead to a normalized EDS on setting
- <math>
W_1 = 1,\quad W_2 = b,\quad W_3 = c,\quad W_4 = d.
</math> It is not obvious, but can be proven, that the condition Шаблон:Math | Шаблон:Math 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
- <math>
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.
</math> (This formula is often applied with Шаблон:Math = 1 and Шаблон:Math = 1.)
Nonsingular EDS
The discriminant of a normalized EDS is the quantity
- <math>
\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.
</math> 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 Шаблон: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 Шаблон:OEIS
- <math>
\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}
</math>
Periodicity of EDS
A sequence Шаблон:Math is said to be periodic if there is a number Шаблон:Math so that Шаблон:Math = Шаблон:Math for every Шаблон:Math ≥ 1. If a nondegenerate EDS Шаблон:Math is periodic, then one of its terms vanishes. The smallest Шаблон:Math ≥ 1 with Шаблон:Math = 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 Шаблон:Math ≤ 10 or Шаблон:Math = 12.
Elliptic curves and points associated to EDS
Ward proves that associated to any nonsingular EDS (Шаблон:Math) is an elliptic curve Шаблон:Math/Q and a point Шаблон:Math ε Шаблон:Math(Q) such that
- <math>
W_n = \psi_n(P)\qquad\text{for all}~n \ge 1.
</math> Here ψШаблон:Math is the [[division polynomial|Шаблон:Math division polynomial]] of Шаблон:Math; the roots of ψШаблон:Math are the nonzero points of order Шаблон:Math on Шаблон:Math. There is a complicated formula[3] for Шаблон:Math and Шаблон:Math in terms of Шаблон:Math, Шаблон:Math, Шаблон:Math, and Шаблон:Math.
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 Шаблон:Math/Q given by a Weierstrass equation and a nontorsion point Шаблон:Math ε Шаблон:Math(Q). One writes the Шаблон:Math-coordinates of the multiples of Шаблон:Math as
- <math>
x(nP) = \frac{A_n}{D_n^2} \quad \text{with}~\gcd(A_n,D_n)=1~\text{and}~D_n \ge 1.
</math> Then the sequence (Шаблон:Math) is also called an elliptic divisibility sequence. It is a divisibility sequence, and there exists an integer Шаблон:Math so that the subsequence ( ±Шаблон:Math )Шаблон:Math ≥ 1 (with an appropriate choice of signs) is an EDS in the earlier sense.
Growth of EDS
Let Шаблон:Math be a nonsingular EDS that is not periodic. Then the sequence grows quadratic exponentially in the sense that there is a positive constant Шаблон:Math such that
- <math>
\lim_{n\to\infty} \frac{\log |W_n|}{n^2} = h > 0.
</math> The number Шаблон:Math 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[4] However, all but finitely many terms in a nonsingular EDS admit a primitive prime divisor.[5] Thus for all but finitely many Шаблон:Math, there is a prime Шаблон:Math such that Шаблон:Math divides Шаблон:Math, but Шаблон:Math does not divide Шаблон:Math for all Шаблон:Math < Шаблон:Math. This statement is an analogue of Zsigmondy's theorem.
EDS over finite fields
An EDS over a finite field FШаблон:Math, 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 Шаблон:Math. The period of an EDS over FШаблон:Math then has the form Шаблон:Math, where Шаблон:Math and Шаблон:Math satisfy
- <math>
r \le \left(\sqrt q+1\right)^2 \quad\text{and}\quad t \mid q-1.
</math> More precisely, there are elements Шаблон:Math and Шаблон:Math in FШаблон:Math* such that
- <math>
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.
</math> The values of Шаблон:Math and Шаблон:Math are related to the Tate pairing of the point on the associated elliptic curve.
Applications of EDS
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 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. (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
- Graham Everest's EDS web page.
- Prime Values of Elliptic Divisibility Sequences.
- Lecture on p-adic Properites of Elliptic Divisibility Sequences.
- ↑ Morgan Ward, Memoir on elliptic divisibility sequences, Amer. J. Math. 70 (1948), 31–74.
- ↑ B. Mazur. Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. 47:33–186, 1977.
- ↑ This formula is due to Ward. See the appendix to J. H. Silverman and N. Stephens. The sign of an elliptic divisibility sequence. J. Ramanujan Math. Soc., 21(1):1–17, 2006.
- ↑ M. Einsiedler, G. Everest, and T. Ward. Primes in elliptic divisibility sequences. LMS J. Comput. Math., 4:1–13 (electronic), 2001.
- ↑ J. H. Silverman. Wieferich's criterion and the abc-conjecture. J. Number Theory, 30(2):226–237, 1988.
- ↑ B. Poonen. Using elliptic curves of rank one towards the undecidability of Hilbert's tenth problem over rings of algebraic integers. In Algorithmic number theory (Sydney, 2002), volume 2369 of Lecture Notes in Comput. Sci., pages 33–42. Springer, Berlin, 2002.
- ↑ K. Stange. The Tate pairing via elliptic nets. In Pairing-Based Cryptography (Tokyo, 2007), volume 4575 of Lecture Notes in Comput. Sci. Springer, Berlin, 2007.
