[seqfan] Re: Can a sequence that is not a linear recurrence with constant coefficients be such mod every prime p (possibly with different coefficients)?

[Robert Israel]

On Mon, 7 Feb 2011, Georgi Guninski wrote:

> On Fri, Feb 04, 2011 at 02:31:35PM +0200, Georgi Guninski wrote:
>> On Thu, Feb 03, 2011 at 04:56:35PM +0100, allouche at math.jussieu.fr wrote:
>>>
>>>
>>> Am I mistaken if I give n! as an example?
>>> jp
>>>
>>>
>>
>> thank you. your example recurrence seems of unbounded order mod p.
>>
>> is it possible the order of the recurrence mod p to be bounded?
>>
>
> FYI Aaron Meyerowitz seems to claim bounded order is possible:
>
> http://mathoverflow.net/questions/54315/can-an-integer-or-rational-sequence-satisfy-some-bounded-order-recurrence-mod/54382#54382
>
> YES, define $a_k$ by $a_0=0$, $a_k=a_{-k}$ for `$k<0$` and for `$k>0$` $a_k=m!$ where `$m\ge 1$` is as large as possible subject to $k$
  being a multiple of $m!$. Then $$a_{k+m!} \equiv a_k \mod m.$$ However we have $a_j=a_{m\cdot m!+j}$ for `$1 \le j\le m!-1$` but not for
  $j=m!$ when $a_{m!} \ne a_{(m+1)!}$ so the sequence can't satisfy a recurrence of finite order.

What is the recurrence of bounded order mod p?  a_{k+p!} = a_k mod p is a 
recurrence of order p!.

Robert Israel                                israel at math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            Vancouver, BC, Canada