7
$\begingroup$

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 [1] 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 [2] 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.

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

[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?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Mar 6, 2015 at 2:16
  • $\begingroup$ 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. $\endgroup$
    – Vesselin Dimitrov
    Mar 6, 2015 at 2:28
  • $\begingroup$ @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. $\endgroup$
    – Richard Stanley
    Mar 6, 2015 at 2:59
  • $\begingroup$ @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.) $\endgroup$
    – Vesselin Dimitrov
    Mar 6, 2015 at 4:16
  • $\begingroup$ @GerryMyerson Of course. I added a P.S. $\endgroup$
    – user40023
    Mar 6, 2015 at 11:31

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.