++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Trilinear Recursion Michael Somos somos@cis.csuohio.edu <http://gosper.org/webmail/src/compose.php?send_to=somos%40cis.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 <http://richard.schroeppel.name:8015/somosadd-intro-070305a.pdf> ~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. Uh oh, NJAS, what makes you think I said anything about 1,4,6,9,146,158,166,178,183,194,201,202,... ? --rwg