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?


1 Answer 1


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

If you said


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.

  • $\begingroup$ I edited "$U$ is a sequence". In your alternate definition of $U(\bar{c},r)$, I assume you mean "$n\in\mathbb{N}$" instead of "$\bar{n}\in\mathbb{N}^k$". For the Fibonacci sequence, I do know that the sets $U(\bar{c},r)$ (as I defined them) are very well structured in a certain model theoretic sense, which has something to do with your alternate definition. But I need to check some details before providing more information. $\endgroup$ Jul 7, 2018 at 16:42
  • $\begingroup$ Of course you are right. I fixed it. Cut and paste is great but needs some caution. $\endgroup$ Jul 7, 2018 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.