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