This site is supported by donations to The OEIS Foundation.

Density

From OeisWiki
Jump to: navigation, search

There are many different mathematical definitions of density. The most common is asymptotic density, which does not exist for all sequences. Consequently a number of other densities have been developed to fill those gaps or to serve different purposes. Although some types may generalize further, this article is about densities on subsets of the natural numbers.

Asymptotic density

Asymptotic density (or natural density) is a common way to measure the size of a subset of the natural numbers.

The lower asymptotic density of a set is defined as

and the upper asymptotic density of a set is defined as

where is the characteristic function of the set .

Both exist for all sets If the two are equal, the asymptotic density is said to exist and is equal to both.

The asymptotic density is finitely additive when it exists. In particular, for disjoint sets and , we have

Szemerédi's theorem[1] shows that if a set has positive upper asymptotic density, then it contains arbitrarily long arithmetic progressions.[2]

Let be the set of fractions of . If has positive asymptotic density, then is (topologically) dense in the positive reals. If is not dense in the reals then has lower asymptotic density less than 1/2 and upper asymptotic density less than 1; and any such lower or upper density is achievable.[3]

Relative density

Sometimes it is natural to look not at the density compared to all natural numbers but to some base set. For example, the asymptotic density of the primes which are 1 mod 3 is 0 but it would be useful for this to be 1/2 in some sense. Relative density simply divides by the number of members of the base set up to rather than by . It is thus a generalization of asymptotic density, the special case where the base set is Most densities can be specialized in a natural way to a relative density of some kind, but when used without quantification "relative density" always means relative asymptotic density.

Logarithmic density

Compared to asymptotic density, logarithmic density is less sensitive to certain perturbations and hence may exist when the asymptotic density does not. If the asymptotic density does exist, so does the logarithmic density and the two are equal.

The lower logarithmic density of a set is defined as

where is the characteristic function of the set .

The upper logarithmic density is obtained analogously. If both exist then the logarithmic density exists and is equal to both.

Logarithmic density is related to asymptotic density by

There exist sequences which have any chosen values as the logarithmic and asymptotic densities, provided they meet these inequalities.[4]

Although the multiples of a set of positive integers may have no asymptotic density,[5] it has logarithmic density[6][7][8] equal to its lower asymptotic density. (This is of course positive if the set is nonempty.)

If the fractions are not dense in the positive real numbers, cannot have upper (or lower) logarithmic density greater than or equal to 1/2; for any there is such a set with logarithmic density (and hence lower and upper logarithmic density) equal to .[3]

Generalized densities

Grekos[9] defines a family of densities by

and as usual for and where is an unbounded increasing function on

Exponential density

This is the special case . This density has the property that the -th powers have exponential density , hence the name.

Multiplicative density

The multiplicative density was defined by Davenport & Erdős[7] and is defined as

if this limit exists.

Uniform density

The uniform density (or Banach density)[10] shows the extent of the variability of the sequence.

Define

While logarithmic density is less sensitive than asymptotic density, uniform density is more sensitive; the three are related by

Of course if the uniform density exists it is equal to the asymptotic and logarithmic densities.


Schnirelmann density

Schnirelmann introduced a concept of density useful in additive combinatorics. The Schnirelmann density is defined as

and the upper Schnirelmann density can be defined analogously as

though this is rarely used. Note that the two are never equal: . Further, the asymptotic densities are bounds:

(at least one of the inequalities being strict).

Mann's theorem states that[11]

Here the + on the left denotes Minkowski addition. Lepson[12] shows that this is the best possible result in that equality can be obtained for any choice of

Niven[13] shows that

.

Dirichlet density

Also known as the analytic density, the Dirichlet density is commonly used in multiplicative number theory where it is often more convenient to calculate than other densities. It is defined as

or equivalently as

with upper and lower Dirichlet densities defined as usual by replacing the limit with the limit superior and limit inferior, respectively.

The Dirichlet density exists (that is, the limit superior equals the limit inferior) precisely when the logarithmic density of the sequence exists.

Divisor density

A subset S of the positive integers has divisor density[14] z if for almost all n it holds that

(where ~ is as n increases without bound).

For any and any there is a set S with divisor density α and logarithmic density β, and this remains true if one or both are replaced with "undefined".

Other densities

  • Lacunary density[15]
  • Mean density, Abel density, Poisson density, logarithmic block density[16]
  • Ψ-density[17]

Properties

It seems reasonable to require that for any density when Further, and

Grekos[9] suggests four properties which may be desirable:

  1. Translation invariance: for any , where + is the Minkowski sum.
  2. Homogeneity: , where denotes
  3. Finiteness: If is finite, then
  4. Finite additivity: If and are disjoint then

I also suggest

3a. If the symmetric difference is finite, then

which, in the presence of the 'reasonable' requirement , is a strengthening of #3. Note that sigma additivity, a strengthening of #4, is not possible in this setting: densities are not measures.

Axioms 1 and 2 mean that homothetic transformations have the expected densities. If they are replaced with

1a.

then the result is a nonprincipal ultrafilter.


Notes

  1. Endre Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica 27 (1975), pp. 199–245.
  2. Note that the converse is not true: if a set contains arbitrarily long arithmetic progressions, it may have null upper asymptotic density. The Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, states that the sequence of prime numbers (which have null upper asymptotic density) contains arbitrarily long arithmetic progressions. In other words there exist arithmetic progressions of primes, with terms, where can be any natural number. The proof is an extension of Szemerédi's theorem.
  3. 3.0 3.1 Ladislav Mišík and János T. Tóth, Logarithmic density of a sequence of integers and density of its ratio set, Journal de théorie des nombres de Bordeaux 15:1 (2003), pp. 309–318, doi: 10.5802/jtnb.404
  4. Ladislav Mišík, Sets of positive integers with prescribed values of densities, Mathematica Slovaca 52:3 (2002), pp. 289–296.
  5. A. S. Besicovitch, On the density of certain sequences of integers, Mathematische Annalen 110 (1934), pp. 336–341.
  6. H. Davenport and P. Erdős, On sequences of positive integers, Acta Arithmetica 2 (1936), pp. 147-151.
  7. 7.0 7.1 H. Davenport and P. Erdős, On sequences of positive integers, J. Indian Math. Soc. 15 (1951), pp. 19–24.
  8. Vilius Stakėnas, On the densities of rational multiples, Lith. Math. J. 50:4 (2010), pp. 459–473. arXiv:1002.3808
  9. 9.0 9.1 Georges Grekos, On various definitions of density (survey), Tatra Mt. Math. Publ. 31 (2005), pp. 17–27.
  10. Georges Grekos, Vladimír Toma, and Jana Tomanová, A note on uniform or Banach density, Annales mathématiques Blaise Pascal 17:1 (2010), pp. 153–163, doi: 10.5802/ambp.280.
  11. Henry B. Mann, A proof of the fundamental theorem on the density of sums of sets of positive integers, Annals of Mathematics. Second Series 43:3 (1942), pp. 523–527.
  12. Benjamin Lepson, Certain best possible results in the theory of Schnirelmann density, Proc. Amer. Math. Soc. 1 (1950), pp. 592–594.
  13. Ivan Niven, The asymptotic density of sequences, Bull. Amer. Math. Soc. 57:6 (1951), pp. 420–434.
  14. R. R. Hall, The divisor density of integer sequences
  15. T. C. Brown and A. R. Freedman, Arithmetic progressions in lacunary sets, Rocky Mountain J. Math. 17:3 (1987), pp. 587–596.
  16. L. A. Rubel, Necessary and sufficient conditions for Carlson's theorem, Transactions of the American Mathematical Society 83 (1956), pp. 417–429.
  17. K. G. Binmore, A density theorem with an application to gap power series, Transactions of the American Mathematical Society 148:2 (1970), pp. 367–384.

Cite this page as

Charles R Greathouse IV, Density. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki. (Available at https://oeis.org/wiki/Density)