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

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

2011-02-04T14:24:32Z

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.

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

2011-02-04T15:44:54Z

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.

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

2011-02-04T15:46:02Z

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$

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

2011-02-04T17:41:16Z

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

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

2011-02-04T19:34:55Z

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}$.

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

2011-02-05T02:24:50Z

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?