# Solutions to linear equations from recurrence sequences with no repeated roots

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?

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.

• 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. Jul 7 '18 at 16:42
• Of course you are right. I fixed it. Cut and paste is great but needs some caution. Jul 7 '18 at 18:05
{"ft_lang_label":"__label__en","ft_lang_prob":0.85436004,"math_prob":0.99964094,"size":1375,"snap":"2021-43-2021-49","text_gpt3_token_len":470,"char_repetition_ratio":0.09700948,"word_repetition_ratio":0.0,"special_character_ratio":0.32072726,"punctuation_ratio":0.12903225,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999666,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-11-28T15:53:09Z\",\"WARC-Record-ID\":\"<urn:uuid:056a0dea-48bd-4750-ae03-a33a464b9daa>\",\"Content-Length\":\"106442\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:99ebe808-25e0-413a-a07e-7e748e355814>\",\"WARC-Concurrent-To\":\"<urn:uuid:bc8e7c62-6d75-4d76-b45b-3b38d7dfdbe6>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/304441/solutions-to-linear-equations-from-recurrence-sequences-with-no-repeated-roots\",\"WARC-Payload-Digest\":\"sha1:K2D26LTH2RX42QXJKJF4V2UPHJVXD2DQ\",\"WARC-Block-Digest\":\"sha1:DR7ZQ46LFXWESFAZLPLJOBJJXT75TA5K\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-49/CC-MAIN-2021-49_segments_1637964358560.75_warc_CC-MAIN-20211128134516-20211128164516-00212.warc.gz\"}"}