Solutions to linear equations from recurrence sequences with no repeated roots

Question

Let $U=(u_n)_{n=0}^{\infty}\subseteq\mathbb{C}$ be a sequence enumerated by a linear homogeneous recurrence relation with constant coefficients, i.e., there is some $d\geq 1$ and $a_1,\ldots,a_d\in\mathbb{C}$ such that, for $n\geq d$, $$ u_n=a_1u_{n-1}+\ldots+a_du_{n-d}. $$

Now, given some $k\geq 1$, a tuple $\bar{c}=(c_1,\ldots,c_k)\in\mathbb{Z}^k$, and some $r\in\mathbb{C}$, define $$ U(\bar{c},r)=\{\bar{n}\in\mathbb{N}^k:c_1u_{n_1}+\ldots+c_ku_{n_k}=r\}. $$ The question I want to ask has to do with the structure of sets of the above form. There has been some well-known work on this type of problem. For example:

Skolem-Mahler-Lech Theorem: Set $k=1$, $c_1=1$, and $r=0$. Then $$ U(1,0)=F\cup P_1\cup\ldots\cup P_t, $$ where $F$ is finite and each $P_i$ is an infinite arithmetic progression.

On the other hand, results in this area for larger $k$ seem to be less developed. Most things I have found are restricted to $k\leq 3$ (e.g. this paper by Schlickewei and Schmidt). I get the impression that this type of question can be quite difficult for arbitrary recurrence relations and large $k$.

So, I want to know if more can be done in the case that the characteristic polynomial $x^d-a_1x^{d-1}-\ldots-a_{d-1}x-a_d$ of $U$ has no repeated roots. Are there results showing that, for arbitrary $k$, sets of the form $U(\bar{c},r)$ have "nice" structure in this case?

Answer 1

I think you mean that $U$ is a sequence satisfying a recurrence.

If you said

$U(\bar{c},r)=\{\bar{n}\in\mathbb{N}:c_1u_{n-1}+\ldots+c_ku_{n-k}=r\}.$

things would be easy because the sequence $V$ defined by $v_n=c_1u_{n-1}+\ldots+c_ku_{n-k}$ satisfies the same recurrence as $U$ so the theorem you quoted applies.

What would you say for this example? That might clarify what kind of answer you could expect.

Consider the sequence of fibonacci numbers $0,1,1,2,3,5,\cdots$ and the equation $u_{n_1}+u_{n_2}+u_{n_3}-u_{n_4}-u_{n_5}-u_{n_6}=0$

First of all one could combine any two zero sums such as $u_9-u_8-u_7=0$ and $u_{37}+u_{36}-u_{38}=0$ to get $36$ solutions if order matters. Actually you could get $72$ by negating. So one could pick $n_1$ and $n_4$ freely.

One could also pick $n_4,n_5,n_6$ arbitrarily and then have $n_1,n_2,n_3$ be any of the $6$ possible orders of the same numbers.

For more complexity consider the sequence which alternates between the Fibonacci numbers , $0$, and the Lucas numbers.

$0,0,2,\ 1,0,1,\ 1,0,3,\ 2,0,4,\ 3,0,7\ ,5,0,11,\ 8,0,18\cdots.$ It satisfies $u_{n+6}=u_{n+3}+u_m $ with $6$ initial conditions. First I'll remark that there might be jazzier ways to get arithmetic progressions of $0$ then to take a recurrence with characteristic equation $f(x)$ and replace it by $f(x^k)$ to allow the interlacing of any $k$ solutions, but I don't know any. Other than that I'll just say that there are many relations.