Bill Gosper wrote:
If a sequence of integers is periodic modulo every positive integer, then it obeys a linear or bilinear recurrence with constant coefficients. E.g., if s(n):= somos4(n)^2, then
- 4 s(n - 6) s(n - 1) + 29 s(n - 5) s(n - 2) + 116 s(n - 4) s(n - 3) s(n) = -------------------------------------------------------------------- s(n - 7)
So I posted the following question to the Robbins forum (see the text-file jamespropp.org/about-robbins for a description of the forum, and send me an email if you want to join): ------------------------------------------------------------------------- Bill Gosper asks whether the following extremely general proposition is true or false: If a sequence of integers is periodic modulo every positive integer, then it obeys a linear or bilinear recurrence with constant >coefficients. He follows this by a very specific example: E.g., if s(n):= somos4(n)^2, then - 4 s(n - 6) s(n - 1) + 29 s(n - 5) s(n - 2) + 116 s(n - 4) s(n - 3) s(n) = -------------------------------------------------------------------- s(n - 7) Can we answer Gosper's question in the affirmative for arbitrary powers of somos4? Jim Propp ------------------------------------------------------------------------- Here are the replies I got:
From Ira Gessel:
------------------------------------------------------------------------- [re the general assertion] It's very unlikely to be true in general. For example, the Bell numbers are periodic modulo every positive integer. I'm not sure how to prove that they (or any sequence) don't satisfy a bilinear recurrence with constant coefficients but I'd be very surprised if they do. -------------------------------------------------------------------------
From Noam Elkies:
------------------------------------------------------------------------- [re the general assertion] I don't think this can be true, because the hypothesis holds if the sequence satisfies *any* reversible polynomial recurrence, including some that grow much too fast to hope for (bi)linearity, e.g. a(n) = a(n-2) + a(n-1)^2009 ... [re the case of powers of somos4] Yes, or even generalized somos-n for n=4,5,6,7. More generally yet, the termwise product of two theta sequences (and thus by induction of any number of theta sequences) is a theta sequence. -------------------------------------------------------------------------
From Michael Larsen:
------------------------------------------------------------------------- [following up on Noam's first remark] Besides, the set of integer sequences which is periodic modulo every positive integer has the cardinality of the continuum. ------------------------------------------------------------------------- (Note that this is exactly the point that Rich Schroeppel made in math-fun on May 14.)
From Fred Lunnon:
------------------------------------------------------------------------- [following up on Ira's posting] Nice example! And deBruijn's formula gives an asymptotic expression for Bell numbers (essentially just an approximaion to the largest term of the Dobinski sum). So they might do the trick, if we knew a general asymptotic form for the solution of a bilinear recurrence, analogous to polynomial(n)*exponential(n) for a linear recurrence. Something involving exp(n^2), perhaps ... -------------------------------------------------------------------------
From Richard Stanley:
------------------------------------------------------------------------- It is easy to find a nonrecursive sequence that is periodic modulo every n. Simply define f(0), f(1), f(-1), f(2), f(-2), etc., in turn, using the Chinese remainder theorem to keep the sequence periodic modulo every prime power. There are infinitely many choices at each step, so most of the time we will obtain a nonrecursive sequence. ------------------------------------------------------------------------- Jim Propp