The upper density of an automatic set is rational

Abstract

Given a natural number $k\ge 2$ and a $k$-automatic set $S$ of natural numbers, we show that the lower density and upper density of $S$ are recursively computable rational numbers and we provide an algorithm for computing these quantities. In addition, we show that for every natural number $k\ge 2$ and every pair of rational numbers $(\hat{I}\pm ,{\hat{I}}^2)$ with $0<\hat{I}\pm <{\hat{I}}^2<1$ or with $(\hat{I}\pm ,{\hat{I}}^2)\in \{(0,0),(1,1)\}$ there is a $k$-automatic subset of the natural numbers whose lower density and upper density are $\hat{I}\pm$ and ${\hat{I}}^2$ respectively, and we show that these are precisely the values that can occur as the lower and upper densities of an automatic set.

16 pages. This version corrects the proof of Lemma 3.1 in addition to making other changes