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