==========================================================================
BRIEF HISTORY OF THE SOMOS SEQUENCE PROBLEM
Michael Somos 07MAY90 (updated 30OCT94) 

The idea of defining recursive sequences of numbers goes back
at least to Fibonacci, although the Greeks already had some
ideas in this area.  The specific recurrence of Fibonacci is
a linear one.  Napier also used this idea to first calculate
his logarithms.  It can be used to calculate sine tables also.
The specific focus of these efforts is to calculate numbers
in a sequence of values of a function.

The equation that these sequences satisfy is of the form:

(1) a[n]=b1*a[n-1]+b2*a[n-2]+...+bk*a[n-k],  n=k,k+1,...

where b1,...,bk are idependent of n.  The case where there is
a dependency on n arises in continued fractions, but that is
another story.  It turns out that equation (1) is related to
the seemingly more general and powerful:

(2) a[n+m]=b1[m]*c1[n]+...+bk[m]*ck[n],  n,m=0,1,...

where b only depends on m and c only depends on n.  It turns
out that the two equations are equivalent in the sense that
(1) implies the existence of b,c (which is not unique) while
(2) implies (1) since there are only a finite number of terms
in the sum.

Equation (2) can be regarded as the diagonalization of the
matrix {a_ij} where a_ij=a[i+j] which is known as a Hankel
matrix [Ref Henrici, Appl. & Comp. Complex Anal.]

Note that this can be extended to the case of power series as

(3) a(x+y)=b1(x)*c1(y)+...+bk(x)*ck(y)+...,   x,y in R

[Ref L.J.Rogers, Proc. L.Math.Soc 1907] but this will not be
needed in this part of the study.

The equation (2) is an example of what is known as an 'Addition
Theorem' or 'Formula'.  The best known example is:

(4a) sin(x+y)=sin(x)cos(y)+cos(x)sin(y)
(4b) cos(x+y)=cos(x)cos(y)-sin(x)sin(y)

There is a trivial variation of this which is also well known:

(4c) sin(x-y)=sin(x)cos(y)-cos(x)sin(y)
(4d) cos(x-y)=cos(x)cos(y)+sin(x)sin(y)

But there is also the hyperbolic variation of the above:

(5a) sinh(x+y)=sinh(x)cosh(y)+cosh(x)sinh(y)
(5b) cosh(x+y)=cosh(x)cosh(y)+sinh(x)sinh(y)
(5c) sinh(x-y)=sinh(x)cosh(y)-cosh(x)sinh(y)
(5d) cosh(x-y)=cosh(x)cosh(y)-sinh(x)sinh(y)

It is tempting to try to find a common generalization of
the circular and hyperbolic cases of these formulas.

Around 1980 I did just that.  I noticed that if I added
equation (4b) to (4d) then this eliminates the sign
change difference in (5b) to (5d).  The common case is:

(6) c(x+y)+c(x-y)=2*c(x)*c(y)

and this is indeed satisfied by both variations of the
cos,cosh.  The problem is solved, but no new functions
emerge from the equation.  It is now a small step to try
to multiply the two equations together to get:

(7) c(x+y)*c(x-y)=c(x)^2*c(y)^2-s(x)^2*s(y)^2

together with the corresponding result for sine:

(8) s(x+y)*s(x-y)=s(x)^2*c(y)^2-c(x)^2*s(y)^2

The solution of these two functional equations includes
the circular and hyperbolic trig functions as a special
case of the elliptic versions.  These equations were
first studied by Gauss, Abel, and Jacobi [Refs to Werke]
in the explicit context of elliptic functions already
being defined through inversion of elliptic integrals.

Notice that there was no need to bring in these notions
in order to discover these equations.  They follow from
well known trig identities and the desire to find some
common generalization of circular and hyperbolic versions.

In this derivation, the problem is now to investigate
the functions that satisfy these equation given that
there already exist two solutions.

A good first step is to try an analogous step of passing
from equation (1) to (2) in this case.  Explicitly:

(9) a[n+2]*a[n-2]=b1*a[n+1]*a[n-1]+b2*a[n]*a[n]
(10) a[n+m]*a[n-m]=b1[n]*c1[m]+b2[n]*c2[m]

Again, the step from (10) to (9) is immediate since the
dimension of the space is 2.  Going from (9) to (10) is
not so easy.  In the published literature this step is
done by appealing to the existing theory of elliptic
functions which is assumed as known.  See for example
Demjanenko [Ref. Russ. Math. Surveys].  Morgan Ward and
Eric T. Bell both wrote papers regarding the relation of
these sequences to Fibonacci and Lucas sequences.  The
topic is known under 'elliptic divisibility sequences'
or 'elliptic division polynomials'  [Ref. Dan Gordon,
Math. of Comp. 1989].


It is now a small step to study the generalization to:

(11) a[n+m]*a[n-m]=b1[n]*c1[m]+...+bk[n]*ck[m],  or
(12) a1[n+m]*a2[n-m]=b1[n]*c1[m]+...+bk[n]*ck[m]

The surprise is that it is easy to find integer sequences
that satisfy equations of this kind.  I chose a particular
case of this to illustrate the existence of this class of
sequences and called it 'The Somos sequence' in 1989, even
though I had first discovered it in 1982.  Explicitly it is

(13) a[0]=a[1]=...=a[5]=1, and           
     a[n]=(a[n-1]*a[n-5]+a[n-2]*a[n-4]+a[n-3]^2)/a[n-6]

I performed computer calculations which strongly suggested
that this is an integer sequence, but have not yet proven
it to my satisfaction.  Recently [APR90] Dean Hickerson
reported to me that he used Macsyma to prove integrality.
I would prefer a more illuminating proof.

These investigations intersect related work in the work of
Gauss on AGM [Ref. to Werke and David Cox, L'Ens. Math.]
and a published problem by Ronald Graham [Ref. Math. Mag.
APR90] on recursive sequences.


Bibliography on Somos sequences

 1. Michael Somos, Problem 1470, Crux Mathematicorum 15, p. 208 (1989).

 2. David Gale, The Strange and Surprising Saga of the Somos Sequences,
    Mathematical Intelligencer 13, no. 1, pp. 40-42 (1991).

 3. David Gale, Somos Sequence Update, Mathematical Intelligencer 13,
    no. 4, pp. 49-50 (1991).

 4. Raphael M. Robinson, Pediodicity of Somos Sequences, Proceedings of
    the American Mathematical Society 116, no. 3, pp. 613-619 (1992).

 5. Janice L. Malouf, An Integer Sequence From a Rational Recursion,
    Discrete Mathematics 110, pp. 257-261 (1992).

Bibliography on Elliptic sequences by Morgan Ward

 1. Morgan Ward, "Note on Divisibility Sequences," Bull. AMS 42(1936):
    843-845.

 2. Morgan Ward, "Linear Divisibility Sequences," Transactions AMS 41
    (1937):276-286.

 3. Morgan Ward, "Arithmetical Properties of Sequences in Rings," Annals
    of Math. 39(1938):210-219.

 4. Morgan Ward, "A Note on Divisibility Sequences," Bull. AMS 45(1939):
    334-336.

 5. Morgan Ward, "The Law of Apparition of Primes in a Lucasion Sequence,"
    Transactions AMS 44(1948):68-86.

 6. Morgan Ward, "Memoir on Elliptic Divisibility Sequences," Amer. J.
    Math. 70(1948):31-74.

 7. Morgan Ward, "The Law of Repetition of Primes in an Elliptic
    Divisibility Sequence," Duke Math. J. 15(1948):941-946.

 8. Morgan Ward, "Arithmetical Properties of Polynomials Associated With
    The Lemniscate Elliptic Functions," Proc. Nat. Acad. Sci. 36(1950):
    359-362.

Bibliography on related areas

 1. Richard Rochberg & Lee A. Rubel, "A Functional Equation," Indiana
    University Mathematics Journal 41(1992):363-376.

 2. J.Zagrodzinski, M.Jaworski, K.Wyser, "From Periodic Process to
    Solitons and Vice-Versa," in Solitons and Chaos edited J.Antoniou
    and F.J.Lambert (1991):275-280, Springer-Verlag.

 3. Joseph H.Silverman, "The Arithmetic of Elliptic Curves," (1986)
    Springer-Verlag.

 4. "Integrable Mappings and Soliton Equations II," Physica D 34(1989)
    :183-192.
* - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - *

==========================================================================