The Shape of the Value Sets of Linear Recurrence Sequences

Stefan Gerhold^{1} Vienna University of Technology 1040 Vienna Austria and Microsoft Research-INRIA 91893 Orsay France

                   sgerhold@fam.tuwien.ac.at

Abstract We show that the closure of the value set of a real linear recurrence sequence is the union of a countable set and a finite collection of intervals. Conversely, any finite collection of closed intervals is the closure of the value set of some recurrence sequence.

1 Introduction

A real linear recurrence sequence (a_{n})_{n≥0} of order h satisfies a relation of the form

a_{n+h} = η_{1}a_{n+h−1} + ⋯ + η_{h−1}a_{n+1} + η_{h}a_{n}, n ≥ 0,

where the coefficients η_{i} and the initial values a_{0}, …, a_{h−1} are real numbers. It is well known that these are precisely the sequences that occur as Taylor coefficients of rational functions with real coefficients, which explains part of their importance in many areas of pure and applied mathematics. In the vast literature on recurrence sequences (the monograph by Everest et al. [3] is an excellent entry point), the possible shape of the value set

{a_{n} : n ≥ 0}

of such sequences seems not to have been worked out. Typical recurrence sequences are, e.g., constant sequences, 2^{n}, (−1)^{n}, and cos n. The first three of these have discrete value sets, whereas the latter, which satisfies the recurrence

a_{n+2} = 2 cos(1)a_{n+1} − a_{n},  n ≥ 0,  (1)

is dense in the interval [−1, 1], by a classical result in Diophantine approximation [2]. This is essentially the full picture, the precise statement being as follows.

2 Main Result

Theorem 1. The closure of the value set of a real linear recurrence sequence is the union of a countable set and a finite collection of intervals. Conversely, any finite non-empty collection of closed intervals is the closure of the value set of a recurrence sequence.

Proof. It is well known that any real recurrence sequence has a representation

a_{n} = |α|^{n}(n^{d}b_{n} + O(n^{d−1})), n → ∞,

where d is a non-negative integer, α ∈ ℂ is a dominating root of the characteristic polynomial

z^{h} − η_{1}z^{h−1} − ⋯ − η_{h−1}z − η_{h},

and the bounded real sequence (b_{n}) depends on the arguments of the dominating characteristic roots; see, e.g., Bell and Gerhold [1] for detailed formulas. Now if |α| ≠ 1, or |α| = 1 and d ≥ 1, then |a_{n}| tends to zero or infinity; in both cases, the closure of its value set is trivially at most countably infinite. The interesting case is |α| = 1 and d = 0, so that

a_{n} = b_{n} + o(1).  (2)

The sequence (b_{n}) can be written as [1]

b_{n} = u_{n} + v_{n},  (3)

where (u_{n}) is a periodic sequence (corresponding to characteristic roots with arguments that are commensurate to π), and (v_{n}) can be split into g sections

v_{gn+k} = ∑_{i=1}^{r} ξ_{i} cos(2πn ∑_{j=1}^{m} c_{ij}τ_{j} + ϕ_{i}),  0 ≤ k < g, n ≥ 0,  (4)

where g is a positive integer, ξ_{i}, τ_{i}, and ϕ_{i} are real numbers, c_{ij} are integers, and 1, τ_{1}, …, τ_{m} are linearly independent over ℚ. The numbers ξ_{i} and ϕ_{i} depend on k, but c_{ij} and τ_{j} do not. The representation (4) can be established by performing a unimodal coordinate change on the arguments of the characteristic roots [1].

If the function F : [0, 1]^{m} → ℝ, also depending on k, is defined by

F (t_{1}, …, t_{m}) := ∑_{i=1}^{r} ξ_{i} cos(2π ∑_{j=1}^{m} c_{ij}t_{j} + ϕ_{i}),

then the closure of the set of values of (v_{gn+k})_{n≥0} equals the image of F, since the sequence of vectors

(nτ_{1} mod 1, …, nτ_{m} mod 1), n ≥ 0,

is dense in [0, 1]^{m} by Kronecker’s approximation theorem [2]. This image is an interval, since F is continuous. Now consider a section (b_{gn+k})_{n≥0}, 0 ≤ k < g, of the sequence (b_{n}). We can split it into sections along which the periodic sequence (u_{n}) from (3) is constant, and the corresponding section-of-a-section of (v_{n}) will still densely fill the same interval as its “parent” (v_{gn+k})_{n≥0}. The closure of the value set of (b_{n}) therefore equals a collection of at most g closed intervals, where the left endpoints are values of the periodic sequence (u_{n}) in (3). Finally, adding the o(1) part in (2) can obviously contribute at most countably many values to the closure of the value set of (a_{n}), so that the first part of the theorem is proved.

To show the converse statement, let

[μ_{k}, ν_{k}],  0 ≤ k ≤ s,  (5)

be an arbitrary collection of real intervals. Suppose that ρ_{0} := ν_{0} − μ_{0} is minimal among the numbers ρ_{k} := ν_{k} − μ_{k}, and define m_{k} := ⌊ρ_{k}/ρ_{0}⌋ ≥ 1. Let (w_{n}) be a periodic recurrence sequence whose value set comprises exactly the ∑ m_{k} + s + 1 numbers

μ_{k} + iρ_{0}, 0 ≤ i < m_{k}, 0 ≤ k ≤ s,  (6)
ν_{k} − ρ_{0}, 0 ≤ k ≤ s.  (7)

The existence of such a (w_{n}) follows from the fact that periodic interlacements of recurrence sequences are themselves recurrence sequences [3]. Define furthermore

x_{n} := \frac{1}{2}ρ_{0}(cos n + 1), n ≥ 0,

which is dense in [0, ρ_{0}] by Kronecker’s Theorem, and

a_{n} := w_{n} + x_{n}, n ≥ 0.

To see that these are indeed recurrence sequences, recall (1) and the property that recurrence sequences form an ℝ-algebra [3]. Since any section of (x_{n}) is dense in [0, ρ_{0}], too, each section of (a_{n}) along which (w_{n}) equals one of the values in (6)–(7), let us call it λ, densely fills the interval [λ, λ + ρ_{0}]. By the definition of m_{k} and the minimality of ρ_{0}, we have

μ_{k} ≤ ν_{k} − ρ_{0} < μ_{k} + m_{k}ρ_{0} ≤ ν_{k}, 0 ≤ k ≤ s.

This shows that

[μ_{k}, ν_{k}] = [ν_{k} − ρ_{0}, ν_{k}] ∪ ⋃_{i=0}^{m_{k}−1}[μ_{k} + iρ_{0}, μ_{k} + (i + 1)ρ_{0}],

hence the closure of the value set of (a_{n}) is given by (5).

We remark that the following refined version of Kronecker’s approximation theorem [2] could also have been used: For real numbers θ_{1}, …, θ_{N}, without any independence assumption, the sequence

(nθ_{1} mod 1, …, nθ_{N} mod 1), n ≥ 0,

is dense in the intersection of the unit cube with finitely many translations of an affine set. Applying this directly to the arguments of the characteristic roots provides an alternative to the unimodal coordinate change employed in the proof above.

References

[1] J. P. Bell and S. Gerhold, On the positivity set of a linear recurrence sequence, Israel J. Math. 157 (2007), 333–345.

[2] J. W. S. Cassels, An Introduction to Diophantine Approximation, Cambridge University Press, 1957.

[3] G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, Recurrence Sequences, Vol. 104 of Mathematical Surveys and Monographs, American Mathematical Society, 2003.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11J71. Keywords: Linear recurrence sequence, value set, Kronecker’s approximation theorem.

Received March 25 2009; revised version received April 14 2009. Published in Journal of Integer Sequences, April 27 2009.

Return to Journal of Integer Sequences home page.