The upper density of an automatic set is rational

DOI10.5802/JTNB.1135MaRDI QIDQ2211032zbMATH OpenOpenAlexFDO

Authors Jason P. Bell

Publication date 10 November 2020

Published in Journal de Théorie des Nombres de Bordeaux (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

Full work available at URL https://arxiv.org/abs/2002.07256

zbMATH Keywords

automatic setCobham's theoremformal languagesupper density

Mathematics Subject Classification ID

Automata sequences (11B85) Formal languages and automata (68Q45)

Abstract: Given a natural number $kge2$ 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 $kge2$ and every pair of rational numbers $$ with $$ or with $$ there is a $k$-automatic subset of the natural numbers whose lower density and upper density are $alpha$ and $$ respectively, and we show that these are precisely the values that can occur as the lower and upper densities of an automatic set.

Review text

Let \(\pi_S(x)\) denote the number of elements of the set \(S\subseteq\mathbb{N}\) that are less than \(x\). The upper and lower densities of \(S\) are respectively \(\limsup_{x\to\infty} \pi_S(x)/x\) and \(\liminf_{x\to\infty} \pi_S(x)/x\). Let \(k\ge 2\) be an integer. When \(S\) is \(k\)-automatic, i.e., the base-\(k\) expansions of the elements in \(S\) are accepted by a finite automaton, then it is shown that these upper and lower densities are recursively computable rational numbers. The author also proves the following. Let \((\alpha,\beta)\) be a pair of rational numbers satisfying either \(0<\alpha\le\beta<1\) or \((\alpha,\beta)\in\{(0,0),(1,1)\}\). Then there is a \(k\)-automatic set \(S\) whose lower density and upper density are \(\alpha\) and \(\beta\) respectively. Conversely, if \(S\) is a \(k\)-automatic set whose lower density is \(\alpha\) and whose upper density is \(\beta\) then either \((\alpha,\beta)\in\{(0,0),(1,1)\}\) or \(\alpha,\beta\) are rational numbers with \(0<\alpha\le\beta<1\).

Recommendations

• Automatic sets of rational numbers
• k-automatic sets of rational numbers
• The asymptotic distribution of elements in automatic sequences
• (Logarithmic) densities for automatic sequences along primes and squares
• When is an automatic set an additive basis?

Cites work

• A note on the density of inherently ambiguous context-free languages
• Automatic Sequences
• Computer programming and formal systems
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3065861 (Why is no real title available?)
• Logarithmic frequency in morphic sequences
• On \(p\)th roots of stochastic matrices
• Uniform tag sequences

Cited in

(8)

• The asymptotic distribution of elements in automatic sequences
• How to prove that a sequence is not automatic
• Squarefree words with interior disposable factors
• k-automatic sets of rational numbers
• Automatic sets of rational numbers
• (Logarithmic) densities for automatic sequences along primes and squares
• Quantitative estimates for the size of an intersection of sparse automatic sets
• On the finite factorial numbers

This page was built for publication: The upper density of an automatic set is rational

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2211032)