# Degenerate linear recurrence sequences

Let $(u_n)_{n \geq 0}$ be a linear recurrence given by $$u_n = a_1 u_{n-1} + \cdots + a_k u_{n-k} \quad \forall n \geq k ,$$ where $u_0, \ldots, u_{k-1}, a_1, \ldots, a_k \in \mathbb{Z}$. We recall that $(u_n)_{n \geq 0}$ is said to be degenerate if its characteristic polynomial $f(x) = X^k - a_1 X^{k-1} - \cdots - a_k$ has two roots $\alpha$ and $\beta$ such that their ratio $\alpha/\beta$ is a root of unity, otherwise $(u_n)_{n \geq 0}$ is said to be non-degenerate.

The following theorem tell us that the study of linear recurrence sequences over an algebraic field can effectively be reduced to that of non-degenerate linear recurrence sequences.

Theorem  Let $(u_n)_{n \geq 0}$ be a linear recurrence of order $k$ over an algebraic number field of degree $d$ over $\mathbb{Q}$. Then there exists an effectively computable constant $M(k,d)$ such that for some $M \leq M(k,d)$ each subsequence $(u_{Mn+\ell})_{n \geq 0}$, with $\ell=0,\ldots,M-1$, is either identically zero or is non-degenerate.

In the light of the previous theorem, usually when dealing with linear recurrence one assumes that these are non-degenerate.

Instead, my question is about degenerate linear recurrence with integer coefficient (from now on). In  all the second order degenerate linear recurrences are listed. What about higher order? Is some general classification known?

Thank you in advance for any reference.

 G. Everest, A. van der Poorten, and I. Shparlinski, Recurrence sequences, Theorem 1.2

 P. Ribenboim, My number, my friends, pp. 5--6

P.S. For who is not practical of linear recurrence sequences, the answer can be equivalently formulated as purely algebraic: Are there some classification of the monic polynomials with integer coefficients $f(X)$ such that there exists two non-zero roots $\alpha$ and $\beta$ of $f(X)$ with $\alpha / \beta$ a root of unity?

• This is the same, isn't it, as asking for all monic cubics with integer coefficients, with one pair or all pairs of roots having ratio a root of unity. – Gerry Myerson Mar 6 '15 at 2:16
• If the characteristic polynomial is irreducible, every degenerate sequence is a splice $a_1,b_1,\ldots ; a_2,b_2, \ldots; \cdots$ of two or more linear recurrent sequences $(a_n), (b_n), \ldots$ (and conversely, a splice is degenerate). Then, excluding the sequences whose characteristic polynomial has a multiple root (those are clearly degenerate, and are characterized as having at least one non-constant polynomial coefficient), the general answer is: arbitrary sums of sequences with irreducible characteristic polynomials, one at least of which has this splice form. – Vesselin Dimitrov Mar 6 '15 at 2:28
• @VessilinDimitrov: I do not seem to understand what you mean by a splice. If $\alpha=(a_1,a_2,\dots)$ is a linear recurrent sequence, then $a_1, a_3, a_5,\dots$ and $a_2,a_4,a_6,\dots$ are also linear recurrent sequences, and $\alpha$ is a splice of these two. – Richard Stanley Mar 6 '15 at 2:59
• @RichardStanley: You are right... I was careless. I had in mind non-trivial splices, where the characteristic polynomial $f$ of each $(a_n), (b_n), \ldots$ has $f(x^d)$ irreducible over $\mathbb{Z}$ for all $d$. (The example you give is special in that the characteristic polynomial $f$ of $a_1,a_3,\ldots$ has $f(x^2)$ reducible.) – Vesselin Dimitrov Mar 6 '15 at 4:16
• @GerryMyerson Of course. I added a P.S. – user40023 Mar 6 '15 at 11:31