Computing the Density of the Positivity Set for Linear Recurrence Sequences

The set of indices that correspond to the positive entries of a sequence ofnumbers is called its positivity set. In this paper, we study the density ofthe positivity set of a given linear recurrence sequence, that is the questionof how much more frequent are the positive entries compared to the non-positiveones. We show that one can compute this density to arbitrary precision, as wellas decide whether it is equal to zero (or one). If the sequence isdiagonalisable, we prove that its positivity set is finite if and only if itsdensity is zero. Further, arithmetic properties of densities are treated, inparticular we prove that it is decidable whether the density is a rationalnumber, given that the recurrence sequence has at most one pair of dominantcomplex roots. Finally, we generalise all these results to symbolic orbits oflinear dynamical systems, thereby showing that one can decide variousproperties of such systems, up to a set of density zero