Elliptic divisibility sequence

Last updated February 24, 2024

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 $(W n) n \geq 1$ defined recursively by four initial values $W 1$ , $W 2$ , $W 3$ , $W 4$ , with $W 1 W 2 W 3$ ≠ 0 and with subsequent values determined by the formulas

{\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 $W 1$ divides each of $W 2$ , $W 3$ , $W 4$ and if further $W 2$ divides $W 4$ , then every term $W n$ 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 $W 1$ , so EDS are frequently normalized to have $W 1$ = 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,\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}\quad {\text{for all}}\quad n>m>r.

(This formula is often applied with $r$ = 1 and $W 1$ = 1.)

Nonsingular EDS

The discriminant of a normalized EDS is the quantity

\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 )

{\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 $(A n) n \geq 1$ is said to be periodic if there is a number $N \geq 1$ so that $A n+N$ = $A n$ for every $n$ ≥ 1. If a nondegenerate EDS $(W n) n \geq 1$ is periodic, then one of its terms vanishes. The smallest $r$ ≥ 1 with $W r$ = 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 $r$ ≤ 10 or $r$ = 12.

Elliptic curves and points associated to EDS

Ward proves that associated to any nonsingular EDS ( $W n$ ) is an elliptic curve $E$ /Q and a point $P$ ε $E$ (Q) such that

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^[3] for $E$ and $P$ in terms of $W 1$ , $W 2$ , $W 3$ , and $W 4$ .

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(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 ( $D n$ ) is also called an elliptic divisibility sequence. It is a divisibility sequence, and there exists an integer $k$ so that the subsequence ( ± $D nk$ )_{$n$ ≥ 1} (with an appropriate choice of signs) is an EDS in the earlier sense.

Growth of EDS

Let $(W n) n \geq 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\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^[4] However, all but finitely many terms in a nonsingular EDS admit a primitive prime divisor.^[5] Thus for all but finitely many $n$ , there is a prime $p$ such that $p$ divides $W n$ , but $p$ does not divide $W m$ for all $m$ < $n$ . This statement is an analogue of Zsigmondy's theorem.

EDS over finite fields

An EDS over a finite field F_$q$, 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 F_$q$ then has the form $rt$ , where $r$ and $t$ satisfy

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 F_$q$^* such that

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 ^[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.

Related Research Articles

<span class="mw-page-title-main">Elliptic curve</span> Algebraic curve

In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point $O$ . An elliptic curve is defined over a field $K$ and describes points in $K 2$ , the Cartesian product of $K$ with itself. If the field's characteristic is different from 2 and 3, then the curve can be described as a plane algebraic curve which consists of solutions $(x, y)$ for:

In complex analysis, an entire function, also called an integral function, is a complex-valued function that is holomorphic on the whole complex plane. Typical examples of entire functions are polynomials and the exponential function, and any finite sums, products and compositions of these, such as the trigonometric functions sine and cosine and their hyperbolic counterparts sinh and cosh, as well as derivatives and integrals of entire functions such as the error function. If an entire function $has a root at, then, taking the limit value at, is an entire function. On the other hand, the natural logarithm, the reciprocal function, and the square root are all not entire functions, nor can they be continued analytically to an entire function.$

A Pythagorean triple consists of three positive integers $a$ , $b$ , and $c$ , such that $a 2 + b 2 = c 2$ . Such a triple is commonly written $(a, b, c)$ , and a well-known example is $(3, 4, 5)$ . If $(a, b, c)$ is a Pythagorean triple, then so is $(ka, kb, kc)$ for any positive integer $k$ . A primitive Pythagorean triple is one in which $a$ , $b$ and $c$ are coprime (that is, they have no common divisor larger than 1). For example, $(3, 4, 5)$ is a primitive Pythagorean triple whereas $(6, 8, 10)$ is not. A triangle whose sides form a Pythagorean triple is called a Pythagorean triangle and is a right triangle.

In abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily unique up to the order of the factors. There are at least three other characterizations of Dedekind domains that are sometimes taken as the definition: see below.

The abc conjecture is a conjecture in number theory that arose out of a discussion of Joseph Oesterlé and David Masser in 1985. It is stated in terms of three positive integers and that are relatively prime and satisfy . The conjecture essentially states that the product of the distinct prime factors of is usually not much smaller than . A number of famous conjectures and theorems in number theory would follow immediately from the abc conjecture or its versions. Mathematician Dorian Goldfeld described the abc conjecture as "The most important unsolved problem in Diophantine analysis".

In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for "repeated unit" and was coined in 1966 by Albert H. Beiler in his book Recreations in the Theory of Numbers.

In mathematics, the rank, Prüfer rank, or torsion-free rank of an abelian group A is the cardinality of a maximal linearly independent subset. The rank of A determines the size of the largest free abelian group contained in A. If A is torsion-free then it embeds into a vector space over the rational numbers of dimension rank A. For finitely generated abelian groups, rank is a strong invariant and every such group is determined up to isomorphism by its rank and torsion subgroup. Torsion-free abelian groups of rank 1 have been completely classified. However, the theory of abelian groups of higher rank is more involved.

In mathematics, an affine algebraic plane curve is the zero set of a polynomial in two variables. A projective algebraic plane curve is the zero set in a projective plane of a homogeneous polynomial in three variables. An affine algebraic plane curve can be completed in a projective algebraic plane curve by homogenizing its defining polynomial. Conversely, a projective algebraic plane curve of homogeneous equation $h (x, y, t) = 0$ can be restricted to the affine algebraic plane curve of equation $h (x, y, 1) = 0$ . These two operations are each inverse to the other; therefore, the phrase algebraic plane curve is often used without specifying explicitly whether it is the affine or the projective case that is considered.

In number theory, a Woodall number (W_n) is any natural number of the form

In mathematics, the Nagell–Lutz theorem is a result in the diophantine geometry of elliptic curves, which describes rational torsion points on elliptic curves over the integers. It is named for Trygve Nagell and Élisabeth Lutz.

In mathematics, a Weierstrass point $on a nonsingular algebraic curve defined over the complex numbers is a point such that there are more functions on, with their poles restricted to only, than would be predicted by the Riemann-Roch theorem.$

In mathematics, a Witt vector is an infinite sequence of elements of a commutative ring. Ernst Witt showed how to put a ring structure on the set of Witt vectors, in such a way that the ring of Witt vectors $over the finite field of order is isomorphic to, the ring of -adic integers . They have a highly non-intuitive structure upon first glance because their additive and multiplicative structure depends on an infinite set of recursive formulas which do not behave like addition and multiplication formulas for standard p-adic integers.$

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if $are coprime integers, then for any integer, there is a prime number p that divides and does not divide for any positive integer, with the following exceptions:$

In mathematics and theoretical computer science, an automatic sequence (also called a k-automatic sequence or a k-recognizable sequence when one wants to indicate that the base of the numerals used is k) is an infinite sequence of terms characterized by a finite automaton. The n-th term of an automatic sequence a(n) is a mapping of the final state reached in a finite automaton accepting the digits of the number n in some fixed base k.

In number theory, the Néron–Tate height is a quadratic form on the Mordell–Weil group of rational points of an abelian variety defined over a global field. It is named after André Néron and John Tate.

In mathematics, a Hodge structure, named after W. V. D. Hodge, is an algebraic structure at the level of linear algebra, similar to the one that Hodge theory gives to the cohomology groups of a smooth and compact Kähler manifold. Hodge structures have been generalized for all complex varieties in the form of mixed Hodge structures, defined by Pierre Deligne (1970). A variation of Hodge structure is a family of Hodge structures parameterized by a manifold, first studied by Phillip Griffiths (1968). All these concepts were further generalized to mixed Hodge modules over complex varieties by Morihiko Saito (1989).

Lehmer's conjecture, also known as the Lehmer's Mahler measure problem, is a problem in number theory raised by Derrick Henry Lehmer. The conjecture asserts that there is an absolute constant $such that every polynomial with integer coefficients satisfies one of the following properties:$

In mathematics the division polynomials provide a way to calculate multiples of points on elliptic curves and to study the fields generated by torsion points. They play a central role in the study of counting points on elliptic curves in Schoof's algorithm.

In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.

In mathematics, and in particular in mathematical analysis, the Gagliardo–Nirenberg interpolation inequality is a result in the theory of Sobolev spaces that relates the $-norms of different weak derivatives of a function through an interpolation inequality. The theorem is of particular importance in the framework of elliptic partial differential equations and was originally formulated by Emilio Gagliardo and Louis Nirenberg in 1958. The Gagliardo-Nirenberg inequality has found numerous applications in the investigation of nonlinear partial differential equations, and has been generalized to fractional Sobolev spaces by Haim Brezis and Petru Mironescu in the late 2010s.$

References

↑ 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.

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. 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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Ward-1] Morgan Ward, Memoir on elliptic divisibility sequences, Amer. J. Math.70 (1948), 31–74.

[Mazur-2] B. Mazur. Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. 47:33–186, 1977.

[SilvermanStephens-3] 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.

[Einsiedler-4] M. Einsiedler, G. Everest, and T. Ward. Primes in elliptic divisibility sequences. LMS J. Comput. Math., 4:1–13 (electronic), 2001.

[Silverman-5] J. H. Silverman. Wieferich's criterion and the abc-conjecture. J. Number Theory, 30(2):226–237, 1988.

[6] 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.

[Stange-7] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]