[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 Mon, Feb 07, 2011 at 08:14:36AM -0800, Robert Israel wrote:
>>> 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!.
>>
>
> i admit i don't know. but the author seems to suggest the answer is
> "yes".

In fact, it can't be of bounded order mod p, because the same argument
the author uses to show that a_n can't satisfy a recurrence of finite
order shows that the order of any recurrence it satisfies mod p must be
at least m! if p > m.

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