Topic Archive: asymptotic density
We develop and discuss some of the theory relating asymptotic density and computability, with attention to the inherent complexity of sets with density invariant under computable permutation. We will make a brief excursion into reverse mathematics on the way, pointing out that a key equivalence of Kjos-Hanssen, Merkle, and Stephan holds over RCA0.
The idea of a negligible subset of the natural numbers is highly appealing; bad behavior often seems restricted to a “small” set. Asymptotic density (the usual solution) has been used repeatedly in many fields, most prominently in number theory. Unfortunately, this is largely incompatible with the computability theorist’s perspective; even 1-equivalent sets can have wildly different densities. However, by restricting to cases where density is computably invariant, we develop a new notion with appealing properties. We will characterize exactly how hard it is to make a set with intrinsic density, and uncover connections to both computability and randomness. In particular, we suggest that Post missed a very natural immunity property when developing his notions of hyperimmunity.