Can an integer or rational sequence satisfy some bounded order recurrence $\mod \$ almost all primes but doesn't satisfy such in $\mathbb{Q}$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T18:35:41Z http://mathoverflow.net/feeds/question/54315 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54315/can-an-integer-or-rational-sequence-satisfy-some-bounded-order-recurrence-mod Can an integer or rational sequence satisfy some bounded order recurrence $\mod \$ almost all primes but doesn't satisfy such in $\mathbb{Q}$? joro 2011-02-04T14:24:32Z 2011-02-06T18:59:43Z <p>Can an integer or rational sequence satisfy some bounded order recurrence $\mod \$ almost all primes but doesn't satisfy such in $\mathbb{Q}$?</p> <p>The recurrences $\mod p$ can be different, possibly depending on $p$ and the recurrence need not be linear, any recurrence will do.</p> http://mathoverflow.net/questions/54315/can-an-integer-or-rational-sequence-satisfy-some-bounded-order-recurrence-mod/54322#54322 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}$? Charles Matthews 2011-02-04T15:44:54Z 2011-02-04T15:44:54Z <p>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.</p> http://mathoverflow.net/questions/54315/can-an-integer-or-rational-sequence-satisfy-some-bounded-order-recurrence-mod/54323#54323 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}$? Ewan Delanoy 2011-02-04T15:46:02Z 2011-02-04T15:56:12Z <p>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 <code>$p\in {\cal P}$</code> there is a function <code>$f_p$</code> from <code>${\mathbb Z}_p^r$</code> to <code>${\mathbb Z}_p$</code> such that the sequence <code>$(a_n)_{n\geq 1}$</code> satisfies <code>$$a_{n+r+1} \equiv f_p(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r}) \ ({\rm mod} \ p)$$</code> for all <code>$n\geq 0$</code> and <code>$p\in {\cal P}$</code>.</p> <p>Now consider the function $A$ defined by <code>$A(n)=(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r})$</code> for all <code>$n \geq 0$</code>. If <code>$A$</code> is injective, the sequence <code>$(a_n)_{n\geq 1}$</code> satisfies a recurrence of degree <code>$r$</code> in <code>$\mathbb Q$</code>. If <code>$A$</code> is not injective, then there are integers <code>$i \lt j$</code> such that <code>$A(i)=A(j)$</code>. Then the values <code>$a_{i+r+1}$</code> and <code>$a_{j+r+1}$</code> agree modulo all primes in $\cal P$, and are therefore equal in $\mathbb Q$. By induction, we see that the sequence <code>$(a_n)_{n\geq 1}$</code> is eventually <code>$(j-i)$</code>-periodic. Then a (more delicate) construction shows that <code>$(a_n)_{n\geq 1}$</code> still satisfies a recurrence of degree <code>$r$</code> in <code>$\mathbb Q$</code></p> http://mathoverflow.net/questions/54315/can-an-integer-or-rational-sequence-satisfy-some-bounded-order-recurrence-mod/54337#54337 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}$? Ewan Delanoy 2011-02-04T17:41:16Z 2011-02-04T17:41:16Z <p>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 <code>$\cal P$</code> of primes such that the sequence <code>$(a_n)_{n\geq 1}$</code> satisifies some linear recurrence modulo <code>$p$</code> for every <code>$p\in {\cal P}$</code>.</p> <p>Now consider the function $A$ defined by <code>$A(n)=(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r})$</code> for all <code>$n \geq 0$</code>. Let <code>$\Omega$</code> be the set of all integers $t\geq 1$ such that the vectors <code>$A(i+1),A(i+2), \ldots ,A(i+t)$</code> are linearly dependent over <code>$\mathbb Q$</code> for some $i$. Then <code>$r+1\in \Omega$</code> so <code>$\Omega$</code> is nonempty. Let $t$ be the smallest element in <code>$\Omega$</code> , and pick up $i$ such that <code>$A(i+1),A(i+2), \ldots ,A(i+t)$</code> are linearly dependent over $\mathbb Q$. By the choice of $t$, we have <code>$t \leq r+1$</code> and <code>$A(i+1),A(i+2), \ldots ,A(i+t-1)$</code> are linearly independent over $\mathbb Q$, so the last vector <code>$A(i+t)$</code> is a linear combination of <code>$A(i+1),A(i+2), \ldots ,A(i+t-1)$</code>:</p> <p><code>$$(*) : A(i+t)=\sum_{k=1}^{t-1} \beta_k A(i+k)$$</code></p> <p>for some coefficients <code>$\beta_1,\beta_2, \ldots ,\beta_k \in {\mathbb Q}$</code>. Now define a new sequence <code>$(b_n)_{n \geq i}$</code> by</p> <p><code>$$b_n=a_{n+t}-\sum_{k=1}^{t-1} \beta_k a_{n+k}$$</code></p> <p>By (*) above, the first $r$ values of <code>$(b_n)_{n \geq 1}$</code> are $0$ (in $\mathbb Q$). Now for <code>$p\in {\cal P}$</code>, the sequence <code>$(b_n \ ({\rm mod} \ p))_{n \geq i}$</code> satisifies a linear recurrence of order $r$, ans starts with $r$ zeroes. So that sequence is identically zero. We deduce that $p$ divides <code>$b_n$</code> for any <code>$p\in {\cal P}$</code> and <code>$n \geq i$</code>, so that <code>$(b_n)_{n \geq i}$</code> is identically $0$ in $\mathbb Q$. </p> <p>So we see that $(*)$ still holds when $i$ is replaced by any <code>$n\geq i$</code>, and that the initial sequence <code>$(a_n)_{n\geq 1}$</code> eventually satisfies a linear recurrence of degree <code>$\leq r$</code>.</p> http://mathoverflow.net/questions/54315/can-an-integer-or-rational-sequence-satisfy-some-bounded-order-recurrence-mod/54349#54349 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}$? ARupinski 2011-02-04T19:34:55Z 2011-02-04T19:34:55Z <p>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:</p> <p>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:</p> <p>$a_n = 0$ if $n&lt;0$</p> <p>$a_0$ = 1</p> <p>$a_n$ = $\sum_{i=1}^\infty (p_i$#$)\cdot a_{n-i}$ if $n>0$</p> <p>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}$.</p> http://mathoverflow.net/questions/54315/can-an-integer-or-rational-sequence-satisfy-some-bounded-order-recurrence-mod/54382#54382 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}$? Aaron Meyerowitz 2011-02-05T02:24:50Z 2011-02-06T18:59:43Z <p>YES, define $a_k$ by $a_0=0$, $a_k=a_{-k}$ for <code>$k&lt;0$</code> and for <code>$k&gt;0$</code> $a_k=m!$ where <code>$m\ge 1$</code> 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 <code>$1 \le j\le m!-1$</code> but not for $j=m!$ when $a_{m!} \ne a_{(m+1)!}$ so the sequence can't satisfy a recurrence of finite order.</p> <p><strong>By request:</strong> 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</p> <p>Three notes: </p> <ul> <li>One could use the least common multiple of $\lbrace1,2,3\cdots m\rbrace$ in place of $m!$ </li> <li>Since the question asked only about primes one could make it have period #$p$ (p primorial) $\mod p$</li> <li>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 <code>$&lt;a_k&gt;$</code> 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?</li> </ul>