Skip to content

Elliptic Divisibility Sequence

An integer divisibility sequence generated by the nonlinear recurrence of elliptic-curve division polynomials, translating multiplication of a rational point into term divisibility, height growth, ranks of apparition, and primitive-divisor structure.

Version
v2 · 2026-08-30 · History
Domain-specific #
1757
Origin domain
mathematics
Subdomain
arithmetic of elliptic curves
Aliases
EDS, Elliptic divisibility recurrence

Core Idea

An Elliptic Divisibility Sequence (EDS) is an integer sequence governed by a nonlinear recurrence inherited from division polynomials on an elliptic curve. Its defining arithmetic feature is divisibility along index divisibility: under standard normalization and nondegeneracy conditions, m | n implies W_m | W_n. The sequence converts the group law of multiples nP on an elliptic curve into explicit integer arithmetic.[1][2]

Two closely connected definitions occur. Ward's recurrence approach begins with initial integer values satisfying integrality conditions and imposes a quartic bilinear recurrence, often expressed in the general form.

W_(n+m) W_(n-m) W_r² = W_(n+r) W_(n-r) W_m² - W_(m+r) W_(m-r) W_n²

for suitable indices. The geometric approach begins with an elliptic curve E over a number field and a rational point P. Denominators of the coordinates of nP, or values of division polynomials ψ_n(P) after normalization and sign choices, form an EDS. Nonsingular sequences correspond to genuine elliptic data; singular examples can collapse to linear recurrences such as ordinary integers or Fibonacci subsequences.

The locked identity is: elliptic curve and marked point (or equivalent nonsingular initial recurrence data) + division-polynomial recurrence -> integer sequence whose index multiplication becomes term divisibility and whose asymptotic arithmetic reflects elliptic height.

Structural Signature

  • the integer sequence W_n — normally normalized with W_0=0 and W_1=1, subject to convention;
  • finite initial data — early terms determine the sequence when required integrality and nondegeneracy conditions hold;
  • the nonlinear elliptic recurrence — bilinear products of separated terms replace the linear recurrence of Lucas or Fibonacci sequences;
  • strong divisibility behavior — index divisibility implies divisibility of corresponding terms;
  • the discriminant — a polynomial in initial terms separates nonsingular elliptic behavior from singular degeneration;
  • the elliptic curve E — a nonsingular cubic carrying an abelian group law;
  • the marked point P — its multiples nP supply the sequence's arithmetic trajectory;
  • division polynomials ψ_n — functions whose zeros detect nonzero n-torsion and whose values generate a recurrence sequence;
  • denominator interpretation — reduced coordinates x(nP)=A_n/D_n² yield a closely related divisibility sequence;
  • canonical-height growth — for nonperiodic nonsingular cases, log |W_n| grows quadratically in n with a constant related to the canonical height of P;
  • rank of apparition — the least index at which a divisor or zero appears;
  • primitive divisors — eventually terms acquire prime divisors absent from earlier terms under standard hypotheses.

The curve link and nonsingular nonlinear recurrence distinguish the class from an arbitrary integer divisibility sequence.

What It Is Not

  • Not every divisibility sequence. a_m | a_n when m | n is necessary but does not supply elliptic origin.
  • Not a linear recurrence sequence generally. Singular EDS may degenerate to linear examples, while nonsingular EDS obey elliptic nonlinear relations.
  • Not an elliptic curve itself. The sequence is an arithmetic encoding associated with a curve and point.
  • Not the Mordell–Weil rank. Rank describes the free abelian part of rational points; one marked point and its multiples generate an EDS regardless of the full rank value.
  • Not a division polynomial alone. The evaluated and normalized sequence, with integrality and divisibility behavior, is the object.
  • Not an arbitrary Somos sequence. Some Somos recurrences relate to elliptic curves, but identity requires the relevant EDS structure.
  • Not ordinary periodicity over the integers. Nonperiodic nonsingular sequences grow rapidly; reduction over finite fields can be periodic.
  • Not automatically a prime-generating sequence. Primitive prime divisors are different from terms that are themselves prime.
  • Not unique without conventions. Signs, scaling, integral model, and denominator normalization must be stated.

Scope of Application

EDS appear in arithmetic dynamics, elliptic curves, Diophantine equations, recurrence sequences, primitive-divisor theory, logic, and pairing-based cryptography. They are tractable nonlinear recurrences because elliptic geometry supplies heights, group structure, reduction modulo primes, and division polynomials.[2]

Over finite fields, EDS are periodic and their periods relate to the order of the point and multiplicative factors associated with pairings. Denominator sequences over number fields encode integrality properties of multiples. Primitive-divisor results play a role analogous to Zsigmondy's theorem for sequences such as a^n-b^n: after finitely many exceptional terms, new prime divisors appear.[3]

Logical applications use divisibility and primitive divisors to model multiplication or encode Diophantine sets in questions related to Hilbert's tenth problem. Cryptographic applications use elliptic nets and EDS-style recurrences to compute Weil or Tate pairings. These applications require exact hypotheses and should not be inferred from every sequence satisfying a visually similar recurrence.

Clarity

Always specify which definition is in use. A Ward recurrence sequence W_n, a division-polynomial value sequence ψ_n(P), and a denominator sequence D_n are closely related but can differ by predictable signs, powers, scaling, or subsequences. “Associated EDS” is safer than literal equality unless normalization is established.

The divisibility statement also needs domain conditions. Integer EDS use ordinary divisibility; ideal divisibility is natural over number fields; elements over finite fields have no informative integer divisibility order but retain recurrence and periodic structure. Degenerate initial data can yield zeros or singular curves and change theorems drastically.

The nearest catalog node, Mordell–Weil Rank of an Elliptic Curve, shares elliptic arithmetic but answers a different question. EDS follows one point through multiplication and records division-polynomial or denominator arithmetic. Rank measures the whole rational-point group's independent generators.

Manages Complexity

Repeated elliptic-curve addition produces rational functions with rapidly growing numerators and denominators. EDS packages those computations into a recurrence with strong divisibility laws. The sequence turns geometric questions—torsion, reduction of P, height, and point order—into patterns of zeros, divisors, valuations, and growth.

Conversely, elliptic geometry explains what would otherwise be an opaque nonlinear recurrence. Canonical height gives the quadratic-exponential growth scale; reduction modulo primes helps explain ranks of apparition and periodicity; division polynomials provide universal identities; primitive-divisor theorems constrain factorization. Each side makes the other more analyzable.

Abstract Reasoning

  1. If m | n, multiplication factors as nP=(n/m)(mP), and the division-polynomial structure yields corresponding term divisibility under normalization.
  2. A zero term indicates that the associated multiple reaches torsion or identity in the relevant setting; its least index is a rank of apparition.
  3. Nonzero discriminant is required before applying nonsingular elliptic-curve results.
  4. Canonical height zero versus positive height separates torsion/degenerate behavior from quadratic logarithmic growth for nontorsion points.
  5. A primitive divisor of W_n records new reduction behavior not present at earlier indices; it need not make W_n prime.
  6. Reduction modulo a finite field makes the point orbit finite and therefore makes the recurrence periodic up to its precise scaling law.
  7. Two sequences with the same initial few integers may belong to different normalizations unless recurrence, discriminant, and curve data agree.
  8. Singular examples warn that divisibility plus recurrence appearance does not guarantee genuinely elliptic complexity.

Knowledge Transfer

The abstraction transfers exactly among recurrence theory, elliptic arithmetic, finite fields, logic, and cryptography because the same division-polynomial identity persists. Elliptic nets generalize the construction from an integer index to higher-rank lattices, preserving much of the addition-law structure.

The broader residues belong to Recurrence, Divisibility, Periodicity, Growth, and Encoding. A biological or organizational “elliptic sequence” is not an instance absent an elliptic curve and the defining recurrence.

Examples

  • Natural numbers: 1,2,3,… can appear as a singular EDS, illustrating that an elementary sequence can sit at the degenerate boundary.
  • Fibonacci subsequence: 1,3,8,21,55,… is another singular example satisfying a linear recurrence.
  • Nonsingular Ward sequence: suitable initial terms generate rapidly growing positive and negative integers with genuine elliptic discriminant.
  • Denominator sequence: denominators of reduced x(nP) values for a nontorsion rational point exhibit divisibility and height growth.
  • Finite-field reduction: the recurrence becomes periodic because the associated point lies in a finite group.
  • Primitive divisor: a sufficiently late term contains a prime factor absent from every earlier nonzero term.
  • Pairing computation: elliptic-net recurrences evaluate bilinear pairings used in cryptography.

Structural Tensions

  • Recurrence data vs. geometric data. Each can define the object, but translation requires normalization.
  • Divisibility regularity vs. nonlinear growth. Strong arithmetic order coexists with rapid and complex terms.
  • Nonsingular theory vs. singular examples. Familiar sequences illustrate the boundary yet obey different theorems.
  • Integer sequence vs. field generalization. Recurrence transfers while ordinary divisibility changes meaning.
  • New prime factors vs. prime terms. Primitive-divisor abundance does not imply many prime-valued terms.
  • Canonical identity vs. sign and scale conventions. Equivalent elliptic information can produce superficially different sequences.

Structural–Framed Character

EDS is structural. Algebraic recurrence, divisibility, discriminant, and elliptic-curve correspondence supply exact membership and theorem conditions independent of interpretive convention, aside from transparent normalization choices.

Structural Core vs. Domain Accent

The core is recurrence translating repeated composition into divisibility and growth. The domain accent is elliptic curves, rational points, division polynomials, canonical heights, torsion, reductions, and primitive divisors. Removing those yields the prime Recurrence rather than an EDS.

  • Recurrence — finite data and a nonlinear identity generate all terms.
  • Divisibility — multiplication in the index induces arithmetic containment among terms.
  • Periodicity — finite-field sequences repeat under group finiteness.
  • Growth — canonical height controls asymptotic logarithmic size.
  • Encoding — elliptic point multiplication becomes integer arithmetic.
  • Invariant — discriminant and height classify qualitative regimes.

The prospective DAG uses composition under prime:recurrence.

Relationships to Other Abstractions

Local relationship map for Elliptic Divisibility SequenceParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.EllipticDivisibility SequenceDOMAINPrime abstraction: Recurrence — is part ofRecurrencePRIME

Current abstraction Elliptic Divisibility Sequence Domain-specific

Parents (1) — more general patterns this builds on

  • Elliptic Divisibility Sequence is part of Recurrence Prime

    finite data and a nonlinear identity generate all terms.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Elliptic Divisibility Sequence sits in a sparse region of the domain-specific corpus (84th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Elliptic Arithmetic & Group Finiteness (5 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

  • arbitrary divisibility sequence;
  • linear recurrence or Lucas sequence;
  • Somos sequence generally;
  • division polynomial by itself;
  • Mordell–Weil rank;
  • elliptic net as the higher-rank generalization;
  • periodic integer sequence;
  • a prime-generating formula.

References

[1] Morgan Ward, “Memoir on Elliptic Divisibility Sequences,” American Journal of Mathematics 70(1), 1948, 31–74, https://doi.org/10.2307/2371930. registry ↩

[2] Graham Everest, Alf van der Poorten, Igor Shparlinski, and Thomas Ward, Recurrence Sequences, Mathematical Surveys and Monographs 104, AMS, 2003, https://doi.org/10.1090/surv/104. registry ↩a ↩b

[3] Graham Everest, Gerard McLaren, and Thomas Ward, “Primitive Divisors of Elliptic Divisibility Sequences,” arXiv:math/0409540, https://arxiv.org/abs/math/0409540. registry ↩

[4] “Elliptic divisibility sequence,” Wikipedia, frozen revision 1364217482 (2026-07-15), https://en.wikipedia.org/wiki/Elliptic_divisibility_sequence. registry