The upper density of an automatic set is rational

DOI10.5802/JTNB.1135zbMATH Open1465.11079arXiv2002.07256OpenAlexW3095852456MaRDI QIDQ2211032FDOQ2211032

Authors: Jason P. Bell 

Publication date: 10 November 2020

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

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.

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

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?

zbMATH Keywords

formal languagesCobham's theoremupper densityautomatic set

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Factoring polynomials with rational coefficients
• Automatic Sequences
• Uniform tag sequences
• On \(p\)th roots of stochastic matrices
• Title not available (Why is that?)
• A note on the density of inherently ambiguous context-free languages
• Logarithmic frequency in morphic sequences
• Computer programming and formal systems

Cited In (7)

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