|
8
|
|
edited Feb 6 2011 at 18:59 |
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?
|
|
|
|
|
7
|
|
edited Feb 6 2011 at 17:45 |
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 no greater than $m^n$.
|
|
|
|
|
6
|
|
edited Feb 5 2011 at 13:40 |
Define 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.
|
|
|
|
5
|
|
edited Feb 5 2011 at 4:23 |
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 $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.
|
|
|
|
|
4
|
|
edited Feb 5 2011 at 4:10 |
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 the sequence is periodic $\mod m$ for any $a_{k+m!} \equiv a_k \mod m.$$ However we have $m$ but it has arbitrarily long segments which are identical a_j=a_{m\cdot m!+j}$ for `$1 \le j\le m!-1$ but followed by different thingsnot for $j=m!$ when $a_{m!} \ne a_{(m+1)!}$ so the sequence can't satisfy a recurrence of finite order.
|
|
|
|
|
3
|
|
edited Feb 5 2011 at 3:02 |
As others have shown, the answer is no if the order is bounded by some number Define $r$. The construction a_k$ by ARupinski would satisfy me as probably correct but unduly complicated if we wanted sequences with first term $a_0$. I'll refine the question and then alter that construction. Let us stick to integer sequences a_0=0$, $<a_k>$ defined a_k=a_{-k}$ for $k\in \mathbb{Z}.$ Suppose such a sequence reduced $\mod m$ satisfies a recurrence of order n. So For <0$ and for $b_k=a_k \mod m$ k>0$ $$b_{k+n}=f(b_k\, b_{k+1} ,\cdots,b_{k+n-1} )$$ a_k=m!$ where $f$ m\ge 1$ is an arbitrary function which depends only on the previous terms (any one of the as large as possible subject to $m^q$ such for k$ being a multiple of $q=m^n$). m!$. Then the reduced sequence it is purely periodic with a period $P=P_m$ no larger than $m^n$ and satisfies the recurrence $a_{k+P}=a_k \mod \mod m$ . Hence I will take the question to be: Suppose $\mathbf{a}=<a_k>$ is a doubly infinite integer sequence and that for each $m>1$ there is a $P=P_m$ such that $a_{j+P}=a_j \mod m\ .$ Must the sequence any $\mathbf{a}$ itself satisfy some recurence? Put that way, it seems that the answer should be NO. Here is my construction, I think m$ but it will actually be clearer if I don't pin down all the details. I will have $P_m=m!$ So I require that for all $m$, $a_k \equiv a_r \mod m!$ when $k \mod m!=r$. Now I can go through the positive integers in order and specify the actual values $a_k$ for $-m! \le k \le m!$ subject to my previous choices and the constraints. This gives me an uncountable number of choices (even if I only choose between adding $(m-1)!$ or not according to some random or non-finite process) That should allow me to frustrate any possible recurrencehas arbitrarily long segments which are identical but followed by different things.
|
|
|
|
|
2
|
|
edited Feb 5 2011 at 2:34 |
As others have shown, the answer is no if the order is bounded by some number $r$. The construction by ARupinski would satisfy me as probably correct but unduly complicated if we wanted sequences with first term $a_0$. I'll refine the question and then alter that construction. Let us stick to integer sequences $<a_k>$ defined for $k \in \mathbb{Z}.$ Suppose such a sequence reduced $\mod m$ satisfies a recurrence of order n. So For $b_k=a_k \mod m$ $$b_{k+n}=f(b_k\, b_{k+1} ,\cdots,b_{k+n-1} )$$ where $f$ is an arbitrary function which depends only on the previous terms (any one of the $q^m$ m^q$ such for $q=m^n$). Then the reduced sequence it is purely periodic with a period $P=P_m$ no larger than $m^n$ and satisfies the recurrence $a_{k+P}=a_k \mod m$.
Hence I will take the question to be:
Suppose $\mathbf{a}=<a_k>$ is a doubly infinite integer sequence and that for each $m>1$ there is a $P=P_m$ such that $a_{j+P}=a_j \mod m\ .$ Must the sequence $\mathbf{a}$ itself satisfy some recurence?
Put that way, it seems that the answer should be NO. Here is my construction, I think it will actually be clearer if I don't pin down all the details. I will have $P_m=m!$ So I require that for all $m$, $a_k \equiv a_r \mod m!$ when $k \mod m!=r$. Now I can go through the positive integers in order and specify the actual values $a_k$ for $-m! \le k \le m!$ subject to my previous choices and the constraints. This gives me an uncountable number of choices (even if I only choose between adding $(m-1)!$ or not according to some random or non-finite process) That should allow me to frustrate any possible recurrence.
|
|
|
|
|
1
|
|
answered Feb 5 2011 at 2:24 |
As others have shown, the answer is no if the order is bounded by some number $r$. The construction by ARupinski would satisfy me as probably correct but unduly complicated if we wanted sequences with first term $a_0$. I'll refine the question and then alter that construction. Let us stick to integer sequences $<a_k>$ defined for $k \in \mathbb{Z}.$ Suppose such a sequence reduced $\mod m$ satisfies a recurrence of order n. So For $b_k=a_k \mod m$ $$b_{k+n}=f(b_k\, b_{k+1} ,\cdots,b_{k+n-1} )$$ where $f$ is an arbitrary function which depends only on the previous terms (any one of the $q^m$ such for $q=m^n$). Then the reduced sequence it is purely periodic with a period $P=P_m$ no larger than $m^n$ and satisfies the recurrence $a_{k+P}=a_k \mod m$.
Hence I will take the question to be:
Suppose $\mathbf{a}=<a_k>$ is a doubly infinite integer sequence and that for each $m>1$ there is a $P=P_m$ such that $a_{j+P}=a_j \mod m\ .$ Must the sequence $\mathbf{a}$ itself satisfy some recurence?
Put that way, it seems that the answer should be NO. Here is my construction, I think it will actually be clearer if I don't pin down all the details. I will have $P_m=m!$ So I require that for all $m$, $a_k \equiv a_r \mod m!$ when $k \mod m!=r$. Now I can go through the positive integers in order and specify the actual values $a_k$ for $-m! \le k \le m!$ subject to my previous choices and the constraints. This gives me an uncountable number of choices (even if I only choose between adding $(m-1)!$ or not according to some random or non-finite process) That should allow me to frustrate any possible recurrence.
|
|
|
