# [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 16:52:07 CET 2011

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.

**By request:** Here it is  from $a_{-9}$ to $a_{33}:$
$${\small \cdots 1,2,1,6,1,2,1,2,1,}\mathbf{0}\small{,\overline{1,2,1,2,1,6,1,2,1,2,1,6,1,2,1,2,1,6,1,2,1,2,1,24},1,2,1,2,1,6,1,\cdots}$$
$a_0=\mathbf{0}$ and all other terms are positive. The length 24 sequence with the overline keeps repeating except the $4!=24$ is $5!=120$ in positions 120,240,360,480,600 (but not 720) 840,960

Three notes:

- One could use the least common multiple of $\lbrace1,2,3\cdots m\rbrace$ in place of $m!$
- Since the question asked only about primes one could make it have period #$p$ (p primorial) $\mod p$
- If $a_k$ satisfies a recurrence of order $n$ mod $m$ then it is periodic $\mod m$ with a period $P=P_m$ which is no greater than $m^n$. Hence it is enough to ask: " If $<a_k>$ is an integer sequence which is periodic mod $m$ (with a period $P_m$ depending on $m$) for every $m$, must it satisfy a finite recurrence?