The upper density of an automatic set is rational (Q2211032)

Let \(\pi_S(x)\) denote the number of elements of the set \(S\subseteq\mathbb{N}\) that are less than \(x\). The upper and lower densities of \(S\) are respectively \(\limsup_{x\to\infty} \pi_S(x)/x\) and \(\liminf_{x\to\infty} \pi_S(x)/x\). Let \(k\ge 2\) be an integer. When \(S\) is \(k\)-automatic, i.e., the base-\(k\) expansions of the elements in \(S\) are accepted by a finite automaton, then it is shown that these upper and lower densities are recursively computable rational numbers. The author also proves the following. Let \((\alpha,\beta)\) be a pair of rational numbers satisfying either \(0<\alpha\le\beta<1\) or \((\alpha,\beta)\in\{(0,0),(1,1)\}\). Then there is a \(k\)-automatic set \(S\) whose lower density and upper density are \(\alpha\) and \(\beta\) respectively. Conversely, if \(S\) is a \(k\)-automatic set whose lower density is \(\alpha\) and whose upper density is \(\beta\) then either \((\alpha,\beta)\in\{(0,0),(1,1)\}\) or \(\alpha,\beta\) are rational numbers with \(0<\alpha\le\beta<1\).