# Can an integer or rational sequence satisfy some bounded order recurrence $\mod \$ almost all primes but doesn't satisfy such in $\mathbb{Q}$?

Can an integer or rational sequence satisfy some bounded order recurrence $\mod \$ almost all primes but doesn't satisfy such in $\mathbb{Q}$?

The recurrences $\mod p$ can be different, possibly depending on $p$ and the recurrence need not be linear, any recurrence will do.

-
@joro: I was mistaken. I think Ewan is right. – Qiaochu Yuan Feb 4 '11 at 16:27
"Satisfies any recursion at all" is a very weak notion. The only way for $a_n$ NOT to satisfy some recursion of length $r$ is if there is some $m < n$ for which $a_m=a_n$, $a_{m+1} = a_{n+1}$ ... $a_{m+r-1} = a_{n+r-1}$ but $a_{m+r} \neq a_{n+r}$. Is this really all you want to require? – David Speyer Feb 4 '11 at 16:31
@ Qiaochu : I think Ewan is right too :-). BTW, I think if the sequence satisfies some linear recurrence of degree r for infinitely many p (with r independent of p of course), then it satisfies a fixed linear recurrence of degree r in $\mathbb Z$. – Ewan Delanoy Feb 4 '11 at 16:35

The answer to your question is NO. In fact, your hypothesis says that there is an infinite set $\cal P$ of primes such that for each $p\in {\cal P}$ there is a function $f_p$ from ${\mathbb Z}_p^r$ to ${\mathbb Z}_p$ such that the sequence $(a_n)_{n\geq 1}$ satisfies $$a_{n+r+1} \equiv f_p(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r}) \ ({\rm mod} \ p)$$ for all $n\geq 0$ and $p\in {\cal P}$.

Now consider the function $A$ defined by $A(n)=(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r})$ for all $n \geq 0$. If $A$ is injective, the sequence $(a_n)_{n\geq 1}$ satisfies a recurrence of degree $r$ in $\mathbb Q$. If $A$ is not injective, then there are integers $i \lt j$ such that $A(i)=A(j)$. Then the values $a_{i+r+1}$ and $a_{j+r+1}$ agree modulo all primes in $\cal P$, and are therefore equal in $\mathbb Q$. By induction, we see that the sequence $(a_n)_{n\geq 1}$ is eventually $(j-i)$-periodic. Then a (more delicate) construction shows that $(a_n)_{n\geq 1}$ still satisfies a recurrence of degree $r$ in $\mathbb Q$

-
Injectivity merely says that once you know $r$ subsequent terms, you can determine their position and, therefore, $a_{n+r+1}$ uniquely, so you can design a formal function that maps $r$-tuples of integers to integers and agrees with the sequence. – fedja Feb 4 '11 at 16:27

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?
-
Hm, If you claim such a sequence is possible can you please give more detailed construction? I fail to see how you define $a_k$ for all $k$. – joro Feb 6 '11 at 7:54
ok I extended the answer – Aaron Meyerowitz Feb 6 '11 at 17:45
Aaron, thanks. Due to stupidity I fail to see the bounded order recurrence $\mod p$, can you please explain the order $\mod p$? – joro Feb 7 '11 at 16:31
If there is a recurrence at all then there is a recurrence of the simple form $a_{k+P} \equiv a_{k} \mod m$. In this case we can take $P=P_m=m!$. Unless $m$ is a prime or prime power there is a smaller period which will do. For example the Fibonacci numbers where we have $a_{k+2}=a_{k+1}+a_k$ (of course) also satisfy that same recurrence to any modulus. However $\mod 6$ they are $$\tiny 0, 1, 1, 2, 3, 5, 2, 1, 3, 4, 1, 5, 0, 5, 5, 4, 3, 1, 4, 5, 3, 2, 5, 1, 0, 1, 1, 2, 3, 5$$ so they also satisfy $a_{k+24}=a_k$. – Aaron Meyerowitz Feb 7 '11 at 17:40
Thank you. So do you claim the answer of the question is "yes" (i.e. there is bounded order recurrence mod p)? – joro Feb 8 '11 at 9:52

This is not a new answer but a comment too long to fit in the usual comment format. It answers the "linear" variant of the problem suggested by Qiaochu. So let us suppose that there is an infinite set $\cal P$ of primes such that the sequence $(a_n)_{n\geq 1}$ satisifies some linear recurrence modulo $p$ for every $p\in {\cal P}$.

Now consider the function $A$ defined by $A(n)=(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r})$ for all $n \geq 0$. Let $\Omega$ be the set of all integers $t\geq 1$ such that the vectors $A(i+1),A(i+2), \ldots ,A(i+t)$ are linearly dependent over $\mathbb Q$ for some $i$. Then $r+1\in \Omega$ so $\Omega$ is nonempty. Let $t$ be the smallest element in $\Omega$ , and pick up $i$ such that $A(i+1),A(i+2), \ldots ,A(i+t)$ are linearly dependent over $\mathbb Q$. By the choice of $t$, we have $t \leq r+1$ and $A(i+1),A(i+2), \ldots ,A(i+t-1)$ are linearly independent over $\mathbb Q$, so the last vector $A(i+t)$ is a linear combination of $A(i+1),A(i+2), \ldots ,A(i+t-1)$:

$$(*) : A(i+t)=\sum_{k=1}^{t-1} \beta_k A(i+k)$$

for some coefficients $\beta_1,\beta_2, \ldots ,\beta_k \in {\mathbb Q}$. Now define a new sequence $(b_n)_{n \geq i}$ by

$$b_n=a_{n+t}-\sum_{k=1}^{t-1} \beta_k a_{n+k}$$

By (*) above, the first $r$ values of $(b_n)_{n \geq 1}$ are $0$ (in $\mathbb Q$). Now for $p\in {\cal P}$, the sequence $(b_n \ ({\rm mod} \ p))_{n \geq i}$ satisifies a linear recurrence of order $r$, ans starts with $r$ zeroes. So that sequence is identically zero. We deduce that $p$ divides $b_n$ for any $p\in {\cal P}$ and $n \geq i$, so that $(b_n)_{n \geq i}$ is identically $0$ in $\mathbb Q$.

So we see that $(*)$ still holds when $i$ is replaced by any $n\geq i$, and that the initial sequence $(a_n)_{n\geq 1}$ eventually satisfies a linear recurrence of degree $\leq r$.

-
Can this be generalised to polynomial recursions? – Dror Speiser Feb 4 '11 at 22:46

Ewan's answer works if you are assuming that the recurrence mod $p$ is of size at most $r$ for every $p$ in your set. It may be a different interpretation of the question than what you meant, but if you merely assume that the recurrences are finite mod $p$ (but no bound on how large the recurrence may be) but not finite over $\mathbb{Q}$, then the answer is yes, such a sequence does exist:

Let $p_n$ denote the $n^{th}$ prime and $p$# denote the product of all primes $\leq p$ and let $a_n$ be the following sequence:

$a_n = 0$ if $n<0$

$a_0$ = 1

$a_n$ = $\sum_{i=1}^\infty (p_i$#$)\cdot a_{n-i}$ if $n>0$

This sequence satisfies a $n^{th}$ order linear recurrence mod $p_n$ for every $n$ (since all but finitely many of the coefficients of the $\mathbb{Q}$-recurrence are 0 mod $p$), but does not satisfy any finite order recurrence over $\mathbb{Q}$.

-
@ARupinski You are answering a different question, right? This one is about bounded order and your n-th order is unbounded? – joro Feb 5 '11 at 6:26
@joro: I wasn't clear on how to interpret "satisfies some bounded order recursion mod almost all primes"; either there is a recursion for each prime of size at most r (Ewan's answer) or there is some finite recursion for each of these primes (which is my answer) . From this comment, I take it you meant the former. – ARupinski Feb 5 '11 at 18:14

I would guess that the answer is "yes", despite the apparent ill-posed nature of the query, simply because you can take a very rapidly growing sequence satisfying congruences modulo primes. In other words I'd expect some sort of growth condition to be required for any result at all here.

-
Can you please give an example? Another answer claims it is impossible. – joro Feb 4 '11 at 16:07
No, if you try to do this you can't get the sequences mod p to have bounded period. – Qiaochu Yuan Feb 4 '11 at 16:55
@joro: I think the problem there is the bad English: "Can an integer sequence ... but doesn't satisfy such in Q ?" to which the answer is "yes, there can be such a sequence". – Charles Matthews Feb 4 '11 at 17:07
@Qiaochu: The hypothesis isn't "bounded period". – Charles Matthews Feb 4 '11 at 17:10
@Charles : So in fact my answers don't contradict yours. I deal with the "bounded period" case. – Ewan Delanoy Feb 4 '11 at 17:47