Edon Kelmendi - Computing the Density of the Positivity Set for Linear Recurrence Sequences

lmcs:10538 - Logical Methods in Computer Science, November 28, 2023, Volume 19, Issue 4 - https://doi.org/10.46298/lmcs-19(4:16)2023
Computing the Density of the Positivity Set for Linear Recurrence SequencesArticle

Authors: Edon Kelmendi

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 the density of the positivity set of a given linear recurrence sequence, that is the question of how much more frequent are the positive entries compared to the non-positive ones. 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. Further, 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. Finally, we generalise all these results to symbolic orbits of linear dynamical systems, thereby showing that one can decide various properties of such systems, up to a set of density zero.


Volume: Volume 19, Issue 4
Secondary volumes: Selected Papers of the 37th ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
Published on: November 28, 2023
Accepted on: September 1, 2023
Submitted on: December 23, 2022
Keywords: Mathematics - Number Theory

Consultation statistics

This page has been seen 2611 times.
This article's PDF has been downloaded 677 times.