Recalling that the sequence 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 is the (twice-or-thrice-a-prime)s where the Somosoid4 EDS polynomial (starting 0,1,1,1,-1,x,... vs 1,1,1,1,1,2,...) factors "for no reason", it is tempting to suspect that the apparent termination at 177 is just an artifact of an insidious breakdown of Mma's Factor when the polynomials become too gigantic. But spot checks at 247 and 253 found the expected factors. (In honor of Neil :) I planned to give up after 2*157, where the (non)factorizations were taking half a day and most of memory. That was one case too late!: 309 {25176.9,False} 310 {492.747,False} 311 {503.344,True} 312 {515.421,False} 313 {529.497,True} 314 {78335.4,False} (Decimal = CPU secs, Boolean = Or[And[PrimeQ[n],irreducible pol],And[twiceorthrice,reducible pol]] In[19]:= ByteCount[eds[314]] Out[19]= 3132720 While the divisibility (EDS) property of Somosoid4 seems rather miraculous, the polynomial phenomenon itself, far from a rarity, seems intrinsic to Somos sequences and hints at what is really going on. Even Somos8, which "fails" with 420514/7 at n=18, seems to produce polynomials (over huge integers) when initialized 1,...,1,x (all positive, no 0/0 trick). --rwg On Sat, Feb 4, 2012 at 12:16 PM, Bill Gosper <billgosper@gmail.com> wrote:
The 0/0 -> x trick seems to make polynomials for the Somos 6 recursion, but lacking the divisibility property. And if there's a proof that any of these critters makes only polynomials, I'd like to see it. I think. Here's aneven more conjectural Somos6oid source of polynomials: Clear[summus2]; summus2[n_] := summus2[n] = Factor[PolynomialQuotient[ 2*summus2[n - 1] summus2[n - 5] + summus2[n - 2]*summus2[n - 4] - summus2[n - 3]^2, summus2[n - 6], x]]
summus2[0] = 1; summus2[1] = 1; summus2[2] = 1; summus2[3] = 1; summus2[4] = x; summus2[5] = d;
with d in {-2,-1,1,2}. For d=2 and n thru 105, deg(p[n+40])-2*deg(p[n+20])+deg(p[n]) = 40.
On Fri, Feb 3, 2012 at 4:18 PM, Bill Gosper <billgosper@gmail.com> wrote:
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
Now 274. I found a minor speedup. --rwg
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,... and all twice or thrice a prime hereafter. --rwg
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