Solution: Day 5, problem 1


The solutions of the fifth day problems problems are somewhat longer and we only give highlights.

The sequence ( tn ) starts 1, 1, 1, 1, 1, 2, 3, 5, 11, 37, 83, ... It is required to show that all of the tn are integral. The proof comes from the theory of elliptic curves, and can be expressed either in terms of the denominators of the coordinates of the multiples of a particular point on a particular elliptic curves, or in terms of special values of certain Jacobi theta functions. In the first version, one computes the point nP + T on the elliptic curve E : y(x + y) = x(x - 1)(x + 2), where T is the 2 - torsion point (0,0) and P is the point of infinite order (2,2); this has the form (xn, yn) where the exact denominators of xn and yn are tn2 and tn3, respectively, for some integer tn, and the rules of computation on elliptic curves lead to the given recursion for the t's. I'll omit the analysis, indicating instead two ways that one could be led to find this solution.

The first is algebraic.
Dividing the recursion tntn+5 = tn+1tn+4 + tn+2tn+3 by tn+1tn+4 gives the simpler recursion wnwn+2 = 1 + 1/wn+1 for the numbers wn = tn+3tn/tn+1tn+2. This says that the seqence of pairs (X, Y) = (wn,wn+1) is generated from the initial value (X, Y) = (1, 1) by (X, Y) ↦ (Y, (1 + Y-1)/X). A picture shows that these points (wn, wn+1) all lie on a curve, which is then easily found to be given by the equation (XY - 1)(5 - X - Y) = 6. This is a curve of genus 1 which is isomorphic to the above E via (x,y) = ( 2(X + Y - 2)/(Y + X - 5), 2(Y - 2X + 1)/(X + Y - 5) ).

The other method is more analytic: one computes the first few (in my case, 300) terms tn numerically, studies their numerical growth, and tries to fit this data by a nice analytic expression. One quickly finds that the growth is roughly exponential in n2, but with some slow fluctuations around this and also with a dependency on the parity of n. This suggests trying the Ansatz tn = C± BnAn2, where (- 1)n = ± 1. This is easily seen to give a solution to our recursion if A is the root of A12 = A4 + 1, and the numerical value A = 1.07283 (approx) does indeed give a reasonably good fit to the data, but eventually fails more and more thoroughly. Looking more carefully, we try the same Ansatz but with C± replaced by a function C±(n) which lies between fixed limits but is almost periodic in n, and this works, but with a new value A = 1.07425 (approx). (The coefficient C±(n) in fact depends on the position of the point (wn, wn+1) on the above-mentioned curve (XY - 1)(5 - X - Y) = 6.) Expanding the function C±(n) numerically into a Fourier series, we discover that it is a Jacobi theta function, and since theta functions (or quotients of them) are elliptic functions, this leads quickly to elliptic curves and to the above curve E.

By the way, by varying the coefficients in the recursion for the tn one can replace the above (E, P) by essentially any elliptic curve over Q and any rational point on it, so that in an elementary course in number theory one could develop (or at least introduce) the entire theory of elliptic curves just by starting with these simple recursions!