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

[Georgi Guninski]

On Mon, Feb 07, 2011 at 10:47:27AM -0800, Robert Israel wrote:
> 
> 
> 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.
>

yes, you are right. i have misinterpreted the answer, sorry.