Natural density

Last updated

In number theory, natural density, also referred to as asymptotic density or arithmetic density, is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the desired subset when combing through the interval [1, n] as n grows large.

Contents

Intuitively, it is thought that there are more positive integers than perfect squares, since every perfect square is already positive, and many other positive integers exist besides. However, the set of positive integers is not in fact larger than the set of perfect squares: both sets are infinite and countable and can therefore be put in one-to-one correspondence. Nevertheless if one goes through the natural numbers, the squares become increasingly scarce. The notion of natural density makes this intuition precise for many, but not all, subsets of the naturals (see Schnirelmann density, which is similar to natural density but defined for all subsets of ).

If an integer is randomly selected from the interval [1, n], then the probability that it belongs to A is the ratio of the number of elements of A in [1, n] to the total number of elements in [1, n]. If this probability tends to some limit as n tends to infinity, then this limit is referred to as the asymptotic density of A. This notion can be understood as a kind of probability of choosing a number from the set A. Indeed, the asymptotic density (as well as some other types of densities) is studied in probabilistic number theory.

Definition

A subset A of positive integers has natural density α if the proportion of elements of A among all natural numbers from 1 to n converges to α as n tends to infinity.

More explicitly, if one defines for any natural number n the counting function a(n) as the number of elements of A less than or equal to n, then the natural density of A being α exactly means that [1]

a(n)/nα as n → ∞.

It follows from the definition that if a set A has natural density α then 0 ≤ α ≤ 1.

Upper and lower asymptotic density

Let be a subset of the set of natural numbers For any , define to be the intersection and let be the number of elements of less than or equal to .

Define the upper asymptotic density of (also called the "upper density") by where lim sup is the limit superior.

Similarly, define the lower asymptotic density of (also called the "lower density") by where lim inf is the limit inferior. One may say has asymptotic density if , in which case is equal to this common value.

This definition can be restated in the following way: if this limit exists. [2]

These definitions may equivalently[ citation needed ] be expressed in the following way. Given a subset of , write it as an increasing sequence indexed by the natural numbers: Then and if the limit exists.

A somewhat weaker notion of density is the upper Banach density of a set This is defined as

Properties and examples

Other density functions

Other density functions on subsets of the natural numbers may be defined analogously. For example, the logarithmic density of a set A is defined as the limit (if it exists)

Upper and lower logarithmic densities are defined analogously as well.

For the set of multiples of an integer sequence, the Davenport–Erdős theorem states that the natural density, when it exists, is equal to the logarithmic density. [5]

See also

Notes

  1. 1 2 Tenenbaum (1995) p.261
  2. Nathanson (2000) pp.256–257
  3. Hall, Richard R.; Tenenbaum, Gérald (1988). Divisors. Cambridge Tracts in Mathematics. Vol. 90. Cambridge: Cambridge University Press. p. 95. ISBN   978-0-521-34056-4. Zbl   0653.10001.
  4. Deléglise, Marc (1998). "Bounds for the density of abundant integers". Experimental Mathematics. 7 (2): 137–143. CiteSeerX   10.1.1.36.8272 . doi:10.1080/10586458.1998.10504363. ISSN   1058-6458. MR   1677091. Zbl   0923.11127.
  5. Hall, Richard R. (1996), Sets of multiples, Cambridge Tracts in Mathematics, vol. 118, Cambridge University Press, Cambridge, Theorem 0.2, p. 5, doi:10.1017/CBO9780511566011, ISBN   978-0-521-40424-2, MR   1414678

Related Research Articles

<span class="mw-page-title-main">Central limit theorem</span> Fundamental theorem in probability theory and statistics

In probability theory, the central limit theorem (CLT) states that, under appropriate conditions, the distribution of a normalized version of the sample mean converges to a standard normal distribution. This holds even if the original variables themselves are not normally distributed. There are several versions of the CLT, each applying in the context of different conditions.

In number theory, a Liouville number is a real number with the property that, for every positive integer , there exists a pair of integers with such that

A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object, an action on mathematical objects, a relation between mathematical objects, or for structuring the other symbols that occur in a formula. As formulas are entirely constituted with symbols of various types, many symbols are needed for expressing all mathematics.

In mathematics, a real number is said to be simply normal in an integer base b if its infinite sequence of digits is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b. A number is said to be normal in base b if, for every positive integer n, all possible strings n digits long have density bn.

In information theory, the asymptotic equipartition property (AEP) is a general property of the output samples of a stochastic source. It is fundamental to the concept of typical set used in theories of data compression.

In mathematical analysis, a function of bounded variation, also known as BV function, is a real-valued function whose total variation is bounded (finite): the graph of a function having this property is well behaved in a precise sense. For a continuous function of a single variable, being of bounded variation means that the distance along the direction of the y-axis, neglecting the contribution of motion along x-axis, traveled by a point moving along the graph has a finite value. For a continuous function of several variables, the meaning of the definition is the same, except for the fact that the continuous path to be considered cannot be the whole graph of the given function, but can be every intersection of the graph itself with a hyperplane parallel to a fixed x-axis and to the y-axis.

In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician Lev Schnirelmann, who was the first to study it.

The Basel problem is a problem in mathematical analysis with relevance to number theory, concerning an infinite sum of inverse squares. It was first posed by Pietro Mengoli in 1650 and solved by Leonhard Euler in 1734, and read on 5 December 1735 in The Saint Petersburg Academy of Sciences. Since the problem had withstood the attacks of the leading mathematicians of the day, Euler's solution brought him immediate fame when he was twenty-eight. Euler generalised the problem considerably, and his ideas were taken up more than a century later by Bernhard Riemann in his seminal 1859 paper "On the Number of Primes Less Than a Given Magnitude", in which he defined his zeta function and proved its basic properties. The problem is named after Basel, hometown of Euler as well as of the Bernoulli family who unsuccessfully attacked the problem.

In mathematics, a homogeneous function is a function of several variables such that the following holds: If each of the function's arguments is multiplied by the same scalar, then the function's value is multiplied by some power of this scalar; the power is called the degree of homogeneity, or simply the degree. That is, if k is an integer, a function f of n variables is homogeneous of degree k if

In mathematics, a divergent series is an infinite series that is not convergent, meaning that the infinite sequence of the partial sums of the series does not have a finite limit.

In mathematics, the Mahler measureof a polynomial with complex coefficients is defined as

In mathematics, the Riemann series theorem, also called the Riemann rearrangement theorem, named after 19th-century German mathematician Bernhard Riemann, says that if an infinite series of real numbers is conditionally convergent, then its terms can be arranged in a permutation so that the new series converges to an arbitrary real number, or diverges. This implies that a series of real numbers is absolutely convergent if and only if it is unconditionally convergent.

Renewal theory is the branch of probability theory that generalizes the Poisson process for arbitrary holding times. Instead of exponentially distributed holding times, a renewal process may have any independent and identically distributed (IID) holding times that have finite mean. A renewal-reward process additionally has a random sequence of rewards incurred at each holding time, which are IID but need not be independent of the holding times.

In mathematics, specifically in category theory, an -coalgebra is a structure defined according to a functor , with specific properties as defined below. For both algebras and coalgebras, a functor is a convenient and general way of organizing a signature. This has applications in computer science: examples of coalgebras include lazy evaluation, infinite data structures, such as streams, and also transition systems.

In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a collection of sets.

In mathematics, a limit is the value that a function approaches as the argument approaches some value. Limits of functions are essential to calculus and mathematical analysis, and are used to define continuity, derivatives, and integrals. The concept of a limit of a sequence is further generalized to the concept of a limit of a topological net, and is closely related to limit and direct limit in category theory. The limit inferior and limit superior provide generalizations of the concept of a limit which are particularly relevant when the limit at a point may not exist.

In mathematics, a profinite integer is an element of the ring

In mathematics, the mean (topological) dimension of a topological dynamical system is a non-negative extended real number that is a measure of the complexity of the system. Mean dimension was first introduced in 1999 by Gromov. Shortly after it was developed and studied systematically by Lindenstrauss and Weiss. In particular they proved the following key fact: a system with finite topological entropy has zero mean dimension. For various topological dynamical systems with infinite topological entropy, the mean dimension can be calculated or at least bounded from below and above. This allows mean dimension to be used to distinguish between systems with infinite topological entropy. Mean dimension is also related to the problem of embedding topological dynamical systems in shift spaces.

In physics, the poppy-seed bagel theorem concerns interacting particles confined to a bounded surface when the particles repel each other pairwise with a magnitude that is proportional to the inverse distance between them raised to some positive power . In particular, this includes the Coulomb law observed in Electrostatics and Riesz potentials extensively studied in Potential theory. Other classes of potentials, which not necessarily involve the Riesz kernel, for example nearest neighbor interactions, are also described by this theorem in the macroscopic regime. For such particles, a stable equilibrium state, which depends on the parameter , is attained when the associated potential energy of the system is minimal. For large numbers of points, these equilibrium configurations provide a discretization of which may or may not be nearly uniform with respect to the surface area of . The poppy-seed bagel theorem asserts that for a large class of sets , the uniformity property holds when the parameter is larger than or equal to the dimension of the set . For example, when the points are confined to the 2-dimensional surface of a torus embedded in 3 dimensions, one can create a large number of points that are nearly uniformly spread on the surface by imposing a repulsion proportional to the inverse square distance between the points, or any stronger repulsion. From a culinary perspective, to create the nearly perfect poppy-seed bagel where bites of equal size anywhere on the bagel would contain essentially the same number of poppy seeds, impose at least an inverse square distance repelling force on the seeds.

In number theory, specifically in Diophantine approximation theory, the Markov constant of an irrational number is the factor for which Dirichlet's approximation theorem can be improved for .

References

This article incorporates material from Asymptotic density on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.