Is regular selection from recurrence also recurrence?

Question

Let $R$ be a ring, and $u=(u(0),u(1),u(2),...)$ be a sequence over $R$ ($u(i)\in R$). Let $m\ge1$, $c_0,...,c_{m-1}\in R$ be fixed elements, and the following law of recursion holds $$u(i+m)=c_0u(i)+c_1u(i+1)+...+c_{m-1}u(i+m-1).$$ Now, we consider some regular selection from the sequence $u$, i.e. the sequence $$v(i)=u(l+d\cdot i),\ \ i\ge0,$$ for some fixed $l\ge0$, $d\ge1$.

Is there exists some law of recursion (similar to above) for the sequence $v$. If $R$ is a finite ring, then $u$ is periodic and $v$ is periodic, so it is obviously true. Also it's true for $m=1$. But if $R$ is infinite and $m\ge2$?

Answer 1

If $R$ is commutative, then yes there is one with the same length.

The space of sequences $R^\Bbb N$ is naturally a $R$-module ($(u+v)(n) = u(n)+v(n)$ and $(r.u)(n) = r.u(n)$)

Let $T : R^\Bbb N \to R^\Bbb N$ be the translation-by-$1$ operation, defined by $(T(u))(n) = u(n+1)$.
This is an $R$-linear map, so there is a natural action of the polynomial ring $R[T]$ on $R^\Bbb N$, that is induced by $T.u = T(u)$.

Now in this context, for a sequence $u$, you have

$\forall i, u(i+m)=c_0u(i)+c_1u(i+1)+...+c_{m-1}u(i+m-1) \\ \iff \forall i, T^m(u)(i) = c_0 u(i) + c_1 T(u)(i) + \ldots + c_{m-1}T^{m-1}(u)(i) \\ \iff \forall i, (T^m(u) - c_{m-1} T^{m-1} - \ldots - c_1 T - c_0)(u)(i) = 0 \\ \iff (T^m(u) - c_{m-1} T^{m-1} - \ldots - c_1 T - c_0).u = 0$

That is, linear recurrent sequences are sequences that are annihilated by the action of a given polynomial in $T$.

So you are given that a sequence $u$ and a polynomial $P(T)$ such that $P(T).u = 0$, integers $d \ge 1,l \ge 0$, and you are asking if there is another polynomial $Q$ such that $(T^lQ(T^d)).u = 0$.
If you find such a $Q$ when $l=0$, the same polynomial will work for $l \ge 1$ so $l$ really doesn't matter here.

Given a sequence $u$, $\{P \in R[T] \mid P.u = 0 \}$ is an ideal of $R[T]$, so your question now becomes "if $P(T) \in R[T]$, is there a multiple of $P$ of the form $Q(T^d)$ ?"

Now, if $K$ is the algebraic closure of the field of fractions of $R$ and $d$ is coprime with the characteristic, $K(T)$ is a Galois extension of $K(T^d)$ of degree $d$, there is a norm map $N_d : K(T) \to K(T^d)$ so you can simply look at the norm of $N_d(P(T)) = \prod_{\zeta^d=1}P(\zeta T) \in K(T^d)$.
If $d$ is a power of the characteristic, then you can simply take $P(T)^d = P(T^d) \in K(T^d)$.
And you have to do both in succession in the general case.

Anyway, this also works over $\Bbb Z$, so for every $m$ and $d$, there is a big formula that gives the coefficients of $Q$ as polynomial expressions with integer coefficients in the coefficients of $P$. Also, it is enough to have the formulas when $d$ is prime, where you can do the computation of $N_d(P(T))$ over $\Bbb Z[\zeta_d] = \Bbb Z[Z]/(1+Z+\dots+Z^{d-1})$. And we have (from the characteristic $d$ case) $N_d(P(T)) \equiv P(T)^d \pmod d$

Answer 2

This is for the case $m=2,d=2.$ if $x,y$ are two adjacent terms in the "original" sequence, let the next term be $ax+by.$ Then the term after that is $ay+b(ax+by)$, and the next is $a(ax+by)+b(ay+b(ax+by)).$ Selecting the first, third, and fifth term, to get a subsequence with spacing $d=2,$ and naming these terms $T_1,T_2,T_3$ for convenience, we have $$T_1=x,\\ T_2=ax+by,\\ T_3=a(ax+by)+b(ay+b(ax+by)).$$ So $T_3$ is $aT_2+bay+b^2T_2,$ and we wish to express $bay$ in terms of $T_2$ and $T_1.$ This can be done by noting that $bay=a(by)=a(T_2-aT_1).$ We get for the two step recurrence (with the above notation for the $T_k$) that

$$T_3=(2a+b^2)T_2-a^2T_1.$$ A quite modest beginning, but the coefficients are in the ring, and the recurrence (which can start at an even or an odd index of the original sequence) is similar to the original recurrence.

Previously I had an erroneous matrix approach, but it may be there is some algebraic operation which would apply to $m=2$ and larger $d,$ or even to arbitrary $m,d.$ If anyone sees such an operation it would of course completely answer the posted question in the affirmative, and I'd be curious to see it.

Note I had to use commutativity of $R$ at a crucial point, and don't know even for the $m=d=2$ case whether for a noncommutative ring the OP's desired recursion can be done.

Answer 3

Here is somewhat simpler answer, with the downside that it's less explicit.

Let's consider again the shifting operator $T$ on the space of sequences, and let $k$ be the field of fractions of $R$.

Consider the $k$-vector space of sequences.

$u$ is a recurrent linear sequence if and only if $Span(u,T(u),T^2(u),\dots)$ is finite dimensional. (if you have a recurrence of order $m$, then that space is obviously of dimension at most $m$. For the converse, if the space has dimension $m$ then there is a relationship between $u,T(u),\ldots,T^m(u)$ so there is a recurrence of order $m$)

So if this space has dimension $m$, then $Span(u,T^d(u),T^{2d}(u),\ldots)$ also has dimension at most $m$ (since it's a subspace).
Let $f_d : R^\Bbb N \to R^\Bbb N$ be the map $f_d(u)(n) = u(dn)$, it only keeps entries with index a multiple of $d$ and erases everything else.
Then $f_d$ is linear, so that $Span(\{f_d(T^{kd}(u)\}) = f_d(Span(\{T^{kd}(u)\}))$ also has dimension at most $m$, which is exactly what we needed to show that the sequence $(u(0),u(d),u(2d),\ldots$) satisfies a linear recurrence of order at most $m$