Computing the Density of the Positivity Set for Linear Recurrence Sequences

Abstract

The set of indices that correspond to the positive entries of a sequence of numbers is called its positivity set. In this paper, we study how dense is the positivity set of a given linear recurrence sequence. We show that one can compute this density to arbitrary precision, as well as decide whether it is equal to zero (or one). If the sequence is diagonalisable, we prove that its positivity set is finite if and only if its density is zero. Lastly, arithmetic properties of densities are treated, in particular we prove that it is decidable whether the density is a rational number, given that the recurrence sequence has at most one pair of dominant complex roots.