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

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.

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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/jtnb.1135
Classification: 11B85,  68Q45
Keywords: upper density, automatic sets, Cobham’s theorem, formal languages
Jason P. Bell 1

1 Department of Pure Mathematics University of Waterloo Waterloo, ON N2L 3G1, Canada
@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/}
}
TY  - JOUR
TI  - The upper density of an automatic set is rational
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2020
DA  - 2020///
SP  - 585
EP  - 604
VL  - 32
IS  - 2
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1135/
UR  - https://doi.org/10.5802/jtnb.1135
DO  - 10.5802/jtnb.1135
LA  - en
ID  - JTNB_2020__32_2_585_0
ER  - 
%0 Journal Article
%T The upper density of an automatic set is rational
%J Journal de Théorie des Nombres de Bordeaux
%D 2020
%P 585-604
%V 32
%N 2
%I Société Arithmétique de Bordeaux
%U https://doi.org/10.5802/jtnb.1135
%R 10.5802/jtnb.1135
%G en
%F JTNB_2020__32_2_585_0
Jason P. Bell. The upper density of an automatic set is rational. Journal de Théorie des Nombres de Bordeaux, Volume 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

Cited by Sources: