The upper density of an automatic set is rational

Bell, Jason P.

Journal de théorie des nombres de Bordeaux, Tome 32 (2020) no. 2, pp. 585-604.

Soient $k\ge 2$ un nombre naturel et $S$ un ensemble $k$-reconnaissable de nombres naturels. On montre que la densité inférieure et la densité supérieure de $S$ sont des nombres rationnels qui sont récursivement calculables, et on donne un algorithme pour les calculer. En outre, on montre que, pour $k\ge 2$ et $(\alpha ,\beta )\in {\mathbb{Q}}^2$ tels que $0<\alpha <\beta <1$ ou $(\alpha ,\beta )\in \left\{\right(0,0),(1,1\left)\right\}$, il existe un sous-ensemble $k$-reconnaissable de $\mathbb{N}$ tel que la densité inférieure et la densité supérieure sont respectivement égales à $\alpha$ et $\beta$. De plus, on montre que ces valeurs sont précisément celles qui peuvent apparaître comme densités inférieure et supérieure d’un ensemble reconnaissable.

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 $(\alpha ,\beta )$ with $0<\alpha <\beta <1$ or with $(\alpha ,\beta )\in \left\{\right(0,0),(1,1\left)\right\}$ there is a $k$-automatic subset of the natural numbers whose lower density and upper density are $\alpha$ and $\beta$ respectively, and we show that these are precisely the values that can occur as the lower and upper densities of an automatic set.

Classification : 11B85, 68Q45
Mots clés : upper density, automatic sets, Cobham’s theorem, formal languages

[1] Allouche, Jean-Paul; Shallit, Jeffrey Automatic sequences. Theory, applications, generalizations, Cambridge University Press, 2003 | Zbl

[2] Bell, Jason P. Logarithmic frequency in morphic sequences, J. Théor. Nombres Bordeaux, Volume 20 (2008) no. 2, pp. 227-241 | DOI | Numdam | MR | Zbl

[3] Chomsky, Noam; Schützenberger, Marcel-Paul The algebraic theory of context-free languages, Computer programming and formal systems (Studies in Logic and the Foundations of Mathematics), North-Holland, 1963, pp. 118-161 | DOI | Zbl

[4] Cobham, Alan Uniform tag sequences, Math. Syst. Theory, Volume 6 (1972), pp. 164-192 | DOI | MR | Zbl

[5] Higham, Nicholas J.; Lin, Lijing On $p$th roots of stochastic matrices, Linear Algebra Appl., Volume 435 (2011) no. 3, pp. 448-463 | DOI | Zbl

[6] Karpelevich, Friedrich I. On the characteristic roots of matrices with nonnegative elements, Izv. Akad. Nauk SSSR, Ser. Mat., Volume 15 (1951), pp. 361-383 | MR | Zbl

[7] Kemp, Rainer A note on the density of inherently ambiguous context-free languages, Acta Inf., Volume 14 (1980) no. 3, pp. 295-298 | DOI | MR | Zbl

[8] Lenstra, Arjen K.; Lenstra, Hendrik W. jun.; Lovász, László Factoring polynomials with rational coefficients, Math. Ann., Volume 261 (1982) no. 4, pp. 515-534 | DOI | MR | Zbl

[9] Lothaire, M. Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, 90, Cambridge University Press, 2002 | MR | Zbl

[10] Schaeffer, Luke; Shallit, Jeffrey The critical exponent is computable for automatic sequences, Int. J. Found. Comput. Sci., Volume 23 (2012) no. 8, pp. 1611-1626 | DOI | MR | Zbl