On Thu, Feb 2, 2012 at 12:57 PM, Bill Gosper <billgosper@gmail.com> wrote:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Trilinear Recursion Michael Somos somos@cis.csuohio.edu
It has been known for some time that the recursion
A(n) = (A(n-1) + C1) / A(n-2)
(of which C1=1 is the Lyness 5-cycle) has a solution in terms of a general Somos-5 sequence a(n) as follows
A(n) = (a(n+2) * a(n-3)) / (a(n) * a(n-1) * C2) 1 + A(n) = (a(n+1) * a(n-2) * C3) / (a(n) * a(n-1) * C2)
for some constansts C2, C3. There are similar kinds of examples. One of the simplest is the following. If
A(n) = (A(n-1) + A(n-2)) / A(n-3), A(1) = A(2) = A(3) = 1,
then
A(n) = (a(n) * a(n+7)) / (a(n+3) * a(n+4))
where
a(n)=(a(n-1)*a(n-6)*a(n-8) + a(n-2)*a(n-4)*a(n-9)) / (a(n=5)*a(n-10)), a(1) = a(2) = ... = a(10) = 1.
which is now sequence A205303 in the OEIS at oeis.org. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
While the idea of an integer trilinear recurrence seems startling, you can make one simply by shifting n in Somos 4, Out[7]= a[-4 + n] a[n] == a[-2 + n]^2 + a[-3 + n] a[-1 + n]
In[8]:= % /. n -> n - 1
Out[8]= a[-5 + n] a[-1 + n] == a[-3 + n]^2 + a[-4 + n] a[-2 + n]
and eliminating a[n-1]
In[9]:= Eliminate[{%, %%}, a[n - 1]]
Out[9]= a[-5 + n] a[-4 + n] a[n] ==
a[-3 + n]^3 + a[-4 + n] a[-3 + n] a[-2 + n] + a[-5 + n] a[-2 + n]^2
In[10]:= Solve[%, a[n]]
Out[10]= {{a[n] -> ( a[-3 + n]^3 + a[-4 + n] a[-3 + n] a[-2 + n] + a[-5 + n] a[-2 + n]^2)/(a[-5 + n] a[-4 + n])}}
I tend to harp on the mysterious polynomial sequence from initializing Somos 4 to 0,1,1,-1,x,... . (See Somos Sequence Near-Addition Formulas and Modular Theta Functions ~p10.) Besides the mystery of why they're (an elliptic divisibility sequence of) polynomials, we have the following. (Strong) EDS => gcd(p[a](x),p[a*b](x)) = p[a](x). But is
p[prime](x) always irreducible? Seems so. The converse, p[n](x) irreducible => n prime is false, despite EDS! Because factors of 2 and 3 only guarantee multiples of p[2](x) = -p[3](x) = 1. But
p[n](x) irreducible <=> n prime
holds for 9<n<146. And then starts failing like crazy, at almost every n=2*prime and n=3*prime, e.g. 201 and 202.
Possibly, p[3*59] is the last reducible exemplar, but checked only thru 249 due to cumbrousness. (According to the formula on p. 11, degree(p[n](x)) goes up like (n^2-Mod[n,8]^2)/16 +e, where |e|<=3. We should at least be able to prove *this*. Unfortunately, the *logs* of the coefficients grow similarly.) This is slightly weird, since bigger *integers* are more likely to factor. So the (slightly strengthened) conjecture could be: p[n:=2^a 3^b prime](x) is irreducible if a+b<2 and n>177.
Uh oh, NJAS, what makes you think I said anything about 1,4,6,9,146,158,166,178,183,194,201,202,... ?
206, 213, 214, 218, 219, 226, 237,249,... Or 10, 14, 15, 21, 22, 26, 33, 34, 38, 39, 46, 51, 57, 58, 62, 69, 74, 82, 86, 87, 93, 94, 106, 111, 118, 122, 123, 129, 134, 141, 142, 159, 177?
--rwg
All this supposing Mma is bearing up under these memory-busting polynomials. It seems that the "Somos" 5 EDS[0] = 0; EDS[1] = 1; EDS[2] = a; EDS[3] = 1; EDS[4] = -a; EDS[5] = x; EDS[n_] := EDS[n] = Factor[ PolynomialQuotient[EDS[n - 1]*EDS[n - 4] + EDS[n - 2]*EDS[n - 3], EDS[n - 5], x]] also makes magic polynomials, which can be irreducible for index 4*prime as well as prime (always), 2*prime, and 3*prime. --rwg