Elliptic Divisibility Sequences

Suppose u[n] denotes the nth term of an integer divisibility sequence. This means all the terms are integers and

u[n] divides u[m] whenever n divides m.

The sequence is said to be an Elliptic Divisibility Sequence (hereafter EDS) if it satisfies the recurrence relation

u[m-n]u[m+n] = u[m+1]u[m-1]u[n]² - u[n+1]u[n-1]u[m]²

for all m > n > 0. In Morgan Ward's terminology, the sequence is proper if u[0]=0, u[1]=1 and u[2]u[3]u[4] is non-zero. We will always assume our EDSs are proper in that sense.

There are some trivial examples such as the integers 0,1,2,3,4.. but non-trivial examples abound. An EDS which occurs a lot starts 0,1,1,-1,1, then continues

2,-1,-3,-5,7,-4,-28,29,59,129,-314,-65,1529,-3689,-8209,-16264,833313,113689,-620297,

2382785,7869898,7001471,-126742987,-398035821,168705471,-7911171597,...

This is sequence A006769 in the On-Line Encyclopedia of Integer Sequences maintained by Neil Sloane.

It might not be obvious but the sequence does have a growth rate: The term log|u[n]| is approximately cn² where c=.02555.. This growth rate is intimately related to the global height of a rational point on an elliptic curve. A recent paper gives more details.

How do you actually calculate values of an EDS? The relation above can be broken down into two simpler relations

u[2n+1] = u[n+2]u[n]³ - u[n-1]u[n+1]³ and

u[2n]u[2] = u[n](u[n+2]u[n-1]² - u[n-2]u[n+1]²).

Once the terms u[0]=0, u[1]=1, u[2], u[3] and u[4] are specified, these formulae can be used to compute all the other terms in the sequence. For example, the formulae above give

u[5]=u[4]u[2]³-u[1]u[3]³ and

u[6]u[2]=u[3](u[5]u[2]²-u[1]u[4]²).

In our earlier example, we get u[5]=1.1³-1.(-1)³=2 and u[6].1=(-1).(2.1²-1.1²)=-1 and so on. One of the amazing things about EDSs is that if you specify the first five terms (and make sure u[2]|u[4]) then your sequence will always be a divisibility sequence if you use these two rules to calculate the rest of the terms.

Rachel Shipsey has recently written a very interesting thesis about EDSs which includes some applications to cryptography. EDSs are connected to heights of rational points on elliptic curves and the elliptic Lehmer problem . This was considered in the paper. The Chudnovskys considered prime values of EDSs in the 80's and a recent paper discusses their conjecture. For a more down to earth treatment of this material, consult this article.

Somos Sequences

EDSs are special cases of a class of sequences which satisfy bilinear recurrences. They are called Somos Sequences after Michael Somos. Jim Propp is creating a web page which gathers together details on these sequences.