# [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 guninski at guninski.com
Mon Feb 7 17:21:12 CET 2011

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".