If $(x_n)$ is a linear recurrence, is the same true for the subsequence $(x_{pn+q})$?

Question

Let $R$ be a ring and let $M$ be a left $R$-module. Then a linear recurrence in $M$ is a sequence $(x_n)_{n\geq 0}$ in $M$ for which there exist scalars $r_0,\ldots,r_d\in R$ such that $$x_{n+d+1} = r_0x_0 + \cdots r_{n+d}x_{n+d}$$ for all $n\geq 0$.

A lacunary subsequence of a sequence $(x_n)$ is a subsequence along an arithmetic progression: i.e. $(x_{pn+q})_{n\geq 0}$ where $p\geq 1,q\geq 0$.

Question: If $(x_n)$ is a linear recurrence, is the same true for every lacunary subsequence?

Specifically, I'm trying to prove this in the case where $R=\mathbf{Z}$. It seems to be "well-known" in the case where $R$ is $\mathbf{Z}$ or $\mathbf{Q}$ or $\mathbf{C}$ and $M=R$, but I can't find a proof. It's very possible that the proof in those special cases is essentially the same as for what I'm asking.

---

One reduction is to work in the submodule generated by $x_0,\ldots,x_d$, so WLOG $M$ is finitely-generated. So if $R$ is a PID then we know it is a sum of cyclic modules. So if we can prove it in the cyclic case, then we know the lacunary subsequences in each component are all linear recurrences, and then hopefully that means it's true for $(x_n)$.

So basically there are two lemmas if you want to prove this over a PID.

1. Let $(x_n)$ be a sequence in $A\oplus B$ and write $x_n=(a_n,b_n)$. Then if $(a_n)$ and $(b_n)$ are linear recurrences in $A$ and $B$ (resp.), then $(x_n)$ is also a linear recurrence. Use induction to get an arbitrary number of summands.

2. Prove the main question in the case where $M$ is cyclic and use Step 1 to get any finitely-generated module.

Answer 1

I thought it over and found a different solution (my comment did not actually address the monicity problem).

Here $R$ is an integral domain with characteristic zero, $K$ is its fraction field, $M$ is any $R$-module.

For any polynomial $P(X)=\sum_{k= 0}^d{a_kX^k} \in R[X]$, and $(u_n)_{n \geq 0}$ is a sequence in $M$, I denote $P(u)=\left(\sum_{k=0}^d{a_ku_{n+k}}\right)_{n \geq 0}$.

It can be easily seen that $(P,u) \longmapsto P(u)$ is $R$-bilinear, and $P(Q(u))=(PQ)(u)$ where $PQ$ is the usual product.

It is also easy to see that $u$ is a linear recurrence iff there is some monic polynomial $P$ (with degree $d$) such that $P(u)=0$. Besides, any multiple $Q$ of said $P$ satisfies $Q(u)=0$.

Now, let $u$ be any sequence that is a linear recurrence (with $P$), and $v_n=u_{qn+p}$ where $p \geq 0$, $q \geq 1$.

Then, for any polynomial $Q$, if $R(X)=X^pQ(X^q)$, $Q(v)_n=R(u)_{qn+p}$.

So, if we can find a monic $Q \in R[X]$ such that the associated $R$ is divisible by $P$ (it is sufficient that $Q(X^q)$ be divisible by $P$), we are done.

This is going to use some “heavy” theory.

Let $\omega$ be a primitive $q$-th root of unity in a field extension $K’$ of $K$.

Let $Q(X)=-(-1)^n\prod_{k=0}^{q-1}{P(\omega^kX)}$.

$Q$ has coefficients that are symmetric polynomials in $1,\omega,\omega^2,\ldots,\omega^{d-1}$ with coefficients in $R$.

So, using the theorem of symmetric polynomials, and the Vieta relations in $X^q-1=\prod_{i=0}^{q-1}{(X-\omega^i)}$, it turns out that $Q$ has coefficients in $R$ and is monic.

Furthermore, $Q(X)=Q(\omega X)$, so $Q$ is a polynomial in $X^q$.

This should be enough.

Answer 2

Here's one almost-answer that I worked out with my friend. It actually uses this paper by PT Young which is where I got the term "lacunary sequence" to begin with.

The basic problem with my strategy in OP is that combining two linear recurrences in a direct sum doesn't work. Let's say $(x_n)$ is a sequence in $A\oplus B$ and write $x_n=(a_n,b_n)$. If we can solve the problem for $A$, then since $(a_n)$ is a linear recurrence in $A$, the subsequence $(a_{qn})$ is also a linear recurrence. Same for $(b_{qn})$. But their recurrences may have different lengths and various coefficients: so smashing them together to get a recurrence $x_n=(a_n,b_n)$ may not work as planned.

PT Young to the rescue! If I understand his notation correctly, the following is a consequence of his work.

Theorem. Let $d,q\geq 1$. There are polynomials $f_1,\ldots,f_d \in \mathbf{Z}[x_1,\ldots,x_d]$, called Dickson polynomials, with the following property. If $(a_n)$ is a sequence in $\mathbf{Z}$ satisfying the $d$th order recurrence $$a_n = k_1a_{n-1}+\cdots+k_da_{n-d}$$ where $\bar{k}:=(k_1,\ldots,k_d)\in \mathbf{Z}^d$, then the $q$-spaced subsequence $(a_{qn})$ satisfies the recurrence $$a_{qn} = f_1(\bar{k}) a_{q(n - 1)} + \cdots + f_d(\bar{k}) a_{q(n-d)}.$$

It is possible that I have misinterpreted his result, so I'm double-checking. But let's proceed assuming that this interpretation is correct.

The point is: the coefficients and length of $(a_{qn})$ depend only on the coefficients/length of $(a_n)$, and not on the actual initial terms of $(a_n)$. So the recurrence is "universal" in that sense. This will solve the direct sum problem, because now each of the summands satisfies a recurrence of the same length and with the same coefficients. The problem thus reduces to proving PT Young's Theorem for $\mathbf{Z}$ and $\mathbf{Z}/m\mathbf{Z}$, the former of which is already literally his theorem, and the latter being easily solved by lifting to $\mathbf{Z}$.

I am also open to precisely quantifying the amount of overkill contained in this argument :P

---

One simpler strategy for proving PT Young's theorem is to show the following less-quantified statement: that if $(a_n)$ is a linear recurrence in a UFD $R$, then the $q$-spaced subsequence $(a_{qn})$ is also a linear recurrence of the same order. Now apply this to the case $R=\mathbf{Z}[x_1,\ldots,x_d]$ and the linear recurrence $(a_n)$ given as follows: $$a_n=x_1a_{n-1}+\cdots+x_da_{n-d}$$ where the initial terms $a_0,\ldots,a_d$ are arbitrary: the subsequence $a_{qn}$ is a recurrence whose coefficients are polynomials. Now specialize the coordinates $x_i$ with any integers you want, and that should prove the quantified theorem for $\mathbf{Z}$.