The upper density of an automatic set is rational
Journal de Théorie des Nombres de Bordeaux, Tome 32 (2020) no. 2, pp. 585-604.

Soient k2 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 k2 et (α,β) 2 tels que 0<α<β<1 ou (α,β){(0,0),(1,1)}, il existe un sous-ensemble k-reconnaissable de tel que la densité inférieure et la densité supérieure sont respectivement égales à α et β. 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 k2 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 k2 and every pair of rational numbers (α,β) with 0<α<β<1 or with (α,β){(0,0),(1,1)} there is a k-automatic subset of the natural numbers whose lower density and upper density are α and β respectively, and we show that these are precisely the values that can occur as the lower and upper densities of an automatic set.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.1135
Classification : 11B85,  68Q45
Mots clés : upper density, automatic sets, Cobham’s theorem, formal languages
@article{JTNB_2020__32_2_585_0,
     author = {Jason P. Bell},
     title = {The upper density of an automatic set is rational},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {585--604},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {32},
     number = {2},
     year = {2020},
     doi = {10.5802/jtnb.1135},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1135/}
}
Jason P. Bell. The upper density of an automatic set is rational. Journal de Théorie des Nombres de Bordeaux, Tome 32 (2020) no. 2, pp. 585-604. doi : 10.5802/jtnb.1135. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1135/

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

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

[3] Noam Chomsky; Marcel-Paul Schützenberger 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 | Article | Zbl 0148.00804

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

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

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

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

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

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

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