ELKIES' 1995 POST TO SCI.MATH.RESEARCH: Date: Wed, 26 Apr 1995 17:59:25 GMT Newsgroups: sci.math,sci.math.research Subject: 1,2,3,5,11,37,...: Non-recursive solution found Summary: Closed form in terms of elliptic theta functions References: <9504231715591.kevin2003.DLITE@delphi.com> Organization: Harvard Math Department Keywords: Somos recurrence, elliptic theta functions Randall Rathbun: > T(i-1)*T(i-4)+T(i-2)*T(i-3) > T(i) = --------------------------- > T(i-5) > > T(0) = 1 T(1) = 1 T(2) = 2 T(3) = 3 T(4) = 5 Two versions of a closed form are given below, together with consequences for the asymptotics of the T(i). First, some preliminary observations: We can extend the functional equation to negative i, finding the sequence ..., 11, 5, 3, 2, 1, 1, 1, 1, 1, 2, 3, 5, 11, ... the symmetry suggests renumbering the T's so that the central 1 is the zeroth. Numerical experiments show that the functional equation has analogs expressing T(i+k+1)T(i-k) as a linear combination of T(i)T(i+1) and T(i-1)T(i+2) for all k. We might hope for a similar equation expressing T(i+k)T(i-k) in terms of T(i)^2 and T(i+1)T(i-1). We don't quite find that; for instance if k=2 then T(i)^2 + T(i-2)T(i+2) is either twice or three times T(i-1)T(i+1) depending on the parity of i. But we can fix this, without losing either the symmetry or the T(i+k+1)T(i-k) identity, by replacing every other T(i) by r*T(i) for a suitable constant r. Indeed let r be the 4th root of 2/3, and define c(-i) = c(i) = T(i-1) if i is even, r*T(i-1) if i is odd, so for i=0,1,2,3,... c(i) is 1,r,1,2r,3,2r,5,11r,... [The second occurrence of "2" appears to be a typo; I assume that 1,r,1,2r,3,5r,11,... was intended, or perhaps 1,r,2,3r,5,11r,... --JGP] These satisfy the recurrence c(i-2) c(i+2) = sqrt(6) * c(i)^2 - c(i-1) c(i+1). [Ralph Buchholz points out that the correct formula is c(i-2) c(i+2) = sqrt(6) * c(i-1) c(i+1) - c(i)^2 --NDE] This looks like a Somos recurrence on sequences of elliptic theta functions (presumably Michael Somos hasn't seen this thread yet, or he would have remarked on this some time back). Indeed let q = 0.02208942811097933557356088... z = 0.1141942041600238048921321... b = 0.9576898995913810138013844... u = 0.7889128685374661530379575... then c(i) = b * u^(n^2) * [sum from n=-infty to + infty of (q^(n^2)*z^(i*n)]. [David DesJardins notes: This should presumably read: c(i) = b * u^(i^2) * ... ] (These values of q,z,b,u were obtained numerically from the condition that the formula for c(i) hold for the initial values i=0,1,2,3.) It follows that c(i) = f(i)*C^(i^2) where C = u * exp(log^2(z) / 4 log(q)) = 1.074254514864672463110626... [wrong: log(q) should be log(1/q) --NDE] and f(i) is a quasiperiodic function with the single irrational period 2 log(q) / log(z) = 3.51420405240870236831... which is bounded away from zero; this gives the asymptotic behavior of c(i), and thus also of T(i) though the T's also have a period of 2 due to the factors of r. The continued fraction of the period starts 3, 1, 1, 17, 9, 1, 15, 2, 7, 2, 7, 1, 1, ... and yields the good rational approximations 7/2 (whence the apparent period-7 behavior noted by Kevin Brown ), 123/35 (explaining the oscillation "with period near 124" observed by Kevin), and 1237/352. The numbers T(i-1) can also be obtained "arithmetically" from the elliptic curve C/q^(2Z) associated to our theta functions. Wasting some more time on gp, I found that we're dealing with the elliptic curve E: y^2 + xy + y = x^3 - 2x (#102-A1(E) in Cremona's table) [subsequently corrected to y^2 + xy = x^3 + x^2 - 2x thanks to D.Rusin's e-mail --NDE] which has [a rational 2-torsion point at (0,0) and] a rational point P: (x,y) = (2,2) of infinite order. For i=0,1,2,3,... the x-coordinate of the i-th multiple of P on E in lowest terms is 1/0 [sic], 2/1, 1/1, 8/1, 9/1, 50/49, 121/64, 2738, 6889/3249, ... , with numerators 1, 2, 1, 2*2^2, 3^2, 2*5^2, 11^2, 2*37^2, 83^2, ... ! Indeed the numerator of i*P is always T(i-1)^2 or 2*T(i-1)^2 according as i is even or odd, and the canonical height of P on E is log(C) = 0.0716269464704400357381372... Note that 7P is an integral point with large (x,y), so very close to the origin (inf,inf) of E(R); this reflects the fact that z^7 is close to a power of q^2 (namely q^4), which is also what was responsible for the nearly 7-periodic behavior of T(i). --Noam D. Elkies (elkies@ramanujan.harvard.edu) Dept. of Mathematics, Harvard University ELKIES' 2000 POST TO THE BILINEAR FORUM (LATER RENAMED THE ROBBINS FORUM): Date: Mon, 27 Nov 2000 14:31:04 -0500 (EST) From: Noam Elkies Subject: Re: Theta functions >> >The little practical problem is to determine (f(0),f(1),f(2),f(3),p,q) >> >from (a,b,c,d,e,k) and vice versa. >> Surely it's only the "vice versa" that's a problem... But that problem >> can probably be reduced to standard computations on elliptic curves. >In this particular case, it is true that going one way is much easier >than the reverse. This is based on the assumption that there exist >effective ways to evaluate the theta function involved. I was thinking >of other cases where it is not clear how to how to go one way or the other >for various reasons including ineffective definitions of functions. The theta function is defined by a rapidly converging sum, so there's no problem. There's also a version of this that's stated directly in terms of arithmetic on the elliptic curve, without any explicit theta functions: Let x(n) = a(n+1) a(n-1) / a(n)^2. Notice that knowing all x(n) together with a(0), a(1) suffices to determine all a(n); that without a(0), a(1) we at least know a(n) up to multiplication by exp(A+Bn); and that multiplying a(n) by exp(C*n^2) is equivalent to multiplying x(n) by exp(2*C). Then for a theta sequence there exists an elliptic curve E: y^2 = c_0 x^3 + c_1 x^2 + c_2 x + c_3 and two points P,Q on E, with Q having x-coordinate zero, such that x(n) is the x-coordinate of the point P+nQ on the curve, for all n. How to find it? Start from x(0),x(1),x(2),x(3) -- which must be distinct for the following recipe to work. Without loss of generality, assume Q has coordinates (0,1). Let y(n) be the y-coordinate of P+nQ. If we know y(0) then we can determine y(1),y(2),y(3) by the usual chords-and-tangents construction: y(1) = (x1/x0) (1-y(0)) - 1 y(2) = (x2/x1) (1-y(1)) - 1 y(3) = (x3/x2) (1-y(2)) - 1 so each y(n) is an affine linear function of y(0). We then have five points (x,y) = (0,1), (x(0),y(0)), ..., (x(3),y(3)) that must lie on a curve y^2 = cubic(x). That is, the determinant | 1 0 0 0 1 | | 1 x(0) x(0)^2 x(0)^3 y(0)^2 | | 1 x(1) x(1)^2 x(1)^3 y(1)^2 | | 1 x(2) x(2)^2 x(2)^3 y(2)^2 | | 1 x(3) x(3)^2 x(3)^3 y(3)^2 | must vanish. All but the last column of this matrix is known, and the last column consists of quadratic polynomials in y whose leading term is proportional to x(n)^2. Therefore the determinant is a linear polynomial which can be solved for y. I haven't worked out the exact conditions under which it really is a linear polynomials, as opposed to a constant or identically zero; however, to show that this works generically it's enough to produce one example, which I do with your challenge problem below. Note that multiplying all the a(n) by exp(C*n^2), and thus each x(n) by exp(2*C), would scale all the x-coordinates by this factor but would still produce an isomorphic curve. > However, it is not a simple process to identify the theta function which > is associated to a bilinear sequence. For those who like challenges, how > about the sequence ...,2,10,-4,2,3,1,-2,2,1,5,2,12,-26,34,... given by > a(n) = (-a(n-1)a(n-3)/2 + a(n-2)^2)/a(n-4) ? The terms seem to be all > integers but I think the j invariant is 186688297520577/225574912. Yes, that's the right j. That's not so bad; only the denominator matters, and the denominator factors as 2^17 1721. The curve turns out to have "multiplicative reduction" at each of the two bad primes 2 and 1721, so it's "semistable" -- which is down-to-earth terms means that it's congruent mod each prime to a curve with only a node, the mildest singularity possible. It also means that the conductor is 2*1721 (in general each of the primes might occur to a higher power in the conductor -- semistable is equivalent to squarefree conductor), which is small enough that the curve can be found in the extended Cremona tables, as 3442-C: Y^2 + XY + Y = X^3 - X^2 - 1191 X + 16095 [note added by JP, 7/29/06: the original post gave the constant term as 10695, but Elkies sent a correction a few hours later] (with the terms XY+Y introduced to remove spurious singularities mod 2). This is not quite the form of the curve described above -- it's related by a linear transformation. The curve has rank 2. We may take P = (-29,174) and Q = (19,-18) and then x(n) is not quite x(P+nQ) but [x(P+nQ)-19]/8. Q is a point of rather small canonical height, .046932... according to gp (which is also what I used to find the equations); but the sequence ...,2,10,-4,2,3,1,-2,2,1,5,2,12,-26,34,... grows more rapidly than this suggest due to the influence of that 2^17 factor the 2-valuation of the terms grows as n^2/34, with details governed by a cycle of length 34=2*17. NDE [For the full conversation of which the preceding message is a part, see the Robbins forum archive. jamespropp.org/about-robbins gives information on how to access the Robbins forum archive.] EMAIL FOLLOWUP, MARCH 2002: Propp to Elkies: Starting from the recurrence c(i-2) c(i+2) = sqrt(6) * c(i-1) c(i+1) - c(i)^2 and from the assumption that c(i) is roughly r^(i^2) for some r, we find that r must satisfy r^8 = sqrt(6) * r^2 - 1, so that r = 1.08072833... But you claim that c(i) = f(i)*C^(i^2) where f(i) is quasiperiodic and C = 1.074254514864672463110626... . Any idea what explains this discrepancy? Thanks, Jim Elkies to Propp: Yes: the quasiperiodic oscillation of c(i)/r^(i^2). The same recursion with different initial conditions can yield different values of r. The computation you report indicates that R = 1.08072833... arises for the solution c(i) = R^(i^2), a degenerate theta sequence. But other initial conditions need not yield the same limit of c(i)^(1/i^2). ************************************************************************** DAVID SPEYER'S 2003 POST TO THE BILINEAR / ROBBINS FORUM: Date: Fri, 28 Feb 2003 01:41:19 -0600 (CST) Subject: Elliptic Curve Formulae While I hesitate to start this debate up again, I thought people might like to know that I have the general form for the elliptic curve associated to a Somos-4 sequence. The results below were computed by essentially the method from Elkies' posts. More specifically, define a[n] by a[0]=a, a[1]=b, a[2]=c, a[3]=d, a[n+2]a[n-2]=p*a[n-1]a[n+1]+q*a[n]^2 Set x[n]=a[n+1]a[n-1]/a[n]^2. Let E be the elliptic curve y^2=(-4/p)x^3+A*x^2-2*B*x+1 where A=b^4/(a^2 c^2)+c^4/(b^2 d^2)+(2 b c)/(a d)+(a^2 d^2)/(b^2 c^2 p^2) +(2 a c)/(b^2 p)+(2 b d)/(c^2 p)-(2 q)/p^2+(2 c^3 q)/(a d^2 p) +(2 b^3 q)/(a^2 d p)+(b^2 c^2 q^2)/(a^2 d^2 p^2) and B=b^2/(a c)+c^2/(b d)+(a d)/(b c p)+(b c q)/(a d p) Let P=(0,1) and Q=((a c)/b^2, -(a c^3)/(b^3 d)+(a^2 d)/(b^3 p)-(c^2 q)/(b d p)). Then x[n] is the x-coordinate of the point P+nQ (where the addition is in the group law of the elliptic curve. In particular, if we set a=b=c=d=p=q=1, our curve is y^2=1-8x+12x^2-4x^3 with P=(0,1) and Q=(1,-1). The first six points P+nQ have coordinates {1, -1}, {1, 1}, {2, -1}, {3/4, -1/4}, {14/9, 43/27}, {69/49, -527/343} The discriminant of the curve is -64(a^13 b^7 c^7 d^13 p^5 + 3 a^12 b^7 c^10 d^11 p^6 + 3 a^11 b^10 c^7 d^12 p^6 + 3 a^11 b^7 c^13 d^9 p^7 - 21 a^10 b^10 c^10 d^10 p^7 + 3 a^9 b^13 c^7 d^11 p^7 + a^10 b^7 c^16 d^7 p^8 + 3 a^9 b^10 c^13 d^8 p^8 + 3 a^8 b^13 c^10 d^9 p^8 + a^7 b^16 c^7 d^10 p^8 + a^14 b^6 c^6 d^14 p^3 q + 4 a^13 b^6 c^9 d^12 p^4 q + 4 a^12 b^9 c^6 d^13 p^4 q + 6 a^12 b^6 c^12 d^10 p^5 q - 21 a^11 b^9 c^9 d^11 p^5 q + 6 a^10 b^12 c^6 d^12 p^5 q + 4 a^11 b^6 c^15 d^8 p^6 q - 18 a^10 b^9 c^12 d^9 p^6 q - 18 a^9 b^12 c^9 d^10 p^6 q + 4 a^8 b^15 c^6 d^11 p^6 q + a^10 b^6 c^18 d^6 p^7 q + 7 a^9 b^9 c^15 d^7 p^7 q + 12 a^8 b^12 c^12 d^8 p^7 q + 7 a^7 b^15 c^9 d^9 p^7 q + a^6 b^18 c^6 d^10 p^7 q - 4 a^12 b^8 c^8 d^12 p^3 q^2 - 4 a^11 b^8 c^11 d^10 p^4 q^2 - 4 a^10 b^11 c^8 d^11 p^4 q^2 + 4 a^10 b^8 c^14 d^8 p^5 q^2 - 25 a^9 b^11 c^11 d^9 p^5 q^2 + 4 a^8 b^14 c^8 d^10 p^5 q^2 + 4 a^9 b^8 c^17 d^6 p^6 q^2 + 15 a^8 b^11 c^14 d^7 p^6 q^2 + 15 a^7 b^14 c^11 d^8 p^6 q^2 + 4 a^6 b^17 c^8 d^9 p^6 q^2 + 6 a^10 b^10 c^10 d^10 p^3 q^3 - 4 a^9 b^10 c^13 d^8 p^4 q^3 - 4 a^8 b^13 c^10 d^9 p^4 q^3 + 6 a^8 b^10 c^16 d^6 p^5 q^3 + 13 a^7 b^13 c^13 d^7 p^5 q^3 + 6 a^6 b^16 c^10 d^8 p^5 q^3 - 4 a^8 b^12 c^12 d^8 p^3 q^4 + 4 a^7 b^12 c^15 d^6 p^4 q^4 + 4 a^6 b^15 c^12 d^7 p^4 q^4 + a^6 b^14 c^14 d^6 p^3 q^5)/(a^10 b^10 c^10 d^10 p^10) There might be some interesting behavior when this is zero, although the length of the expression is forbidding. David Speyer