The upper density of an automatic set is rational

Jason P. Bell

doi:10.5802/jtnb.1135

Jason P. Bell ¹

¹ Department of Pure Mathematics University of Waterloo Waterloo, ON N2L 3G1, Canada

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

Résumé
Abstract

Soient $k \geq 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 \geq 2$ et $(α, β) \in ℚ^{2}$ tels que $0 < α < β < 1$ ou $(α, β) \in {(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 $k \geq 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 \geq 2$ and every pair of rational numbers $(α, β)$ with $0 < α < β < 1$ or with $(α, β) \in {(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 : 2020-02-18
Révisé le : 2020-07-08
Accepté le : 2020-07-28
Publié le : 2020-10-29

DOI : 10.5802/jtnb.1135

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

Affiliations des auteurs :

Jason P. Bell ¹

¹ Department of Pure Mathematics University of Waterloo Waterloo, ON N2L 3G1, Canada

Licence :

CC-BY-ND 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@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
AU  - Jason P. Bell
TI  - The upper density of an automatic set is rational
JO  - Journal de théorie des nombres de Bordeaux
PY  - 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/
DO  - 10.5802/jtnb.1135
LA  - en
ID  - JTNB_2020__32_2_585_0
ER  -

%0 Journal Article
%A Jason P. Bell
%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://jtnb.centre-mersenne.org/articles/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, Tome 32 (2020) no. 2, pp. 585-604. doi : 10.5802/jtnb.1135. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1135/

Bibliographie
Cité par

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

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

[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 | DOI | Zbl

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

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

[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 | Zbl

[7] Rainer Kemp 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] 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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

Cité par Sources :