Davenport–Erdős theorem

In number theory, the Davenport–Erdős theorem states that, for sets of multiples of integers, several different notions of density are equivalent.^[1][2][3]

Let ${\displaystyle A=a_{1},a_{2},\dots }$ be a sequence of positive integers. Then the multiples of ${\displaystyle A}$ are another set ${\displaystyle M(A)}$ that can be defined as the set ${\displaystyle M(A)=\{ka\mid k\in \mathbb {N} ,a\in A\}}$ of numbers formed by multiplying members of ${\displaystyle A}$ by arbitrary positive integers.^[1][2][3]

According to the Davenport–Erdős theorem, for a set ${\displaystyle M(A)}$, the following notions of density are equivalent, in the sense that they all produce the same number as each other for the density of ${\displaystyle M(A)}$:^[1][2][3]

• The lower natural density, the inferior limit as ${\displaystyle n}$ goes to infinity of the proportion of members of ${\displaystyle M(A)}$ in the interval ${\displaystyle [1,n]}$.
• The logarithmic density or multiplicative density, the weighted proportion of members of ${\displaystyle M(A)}$ in the interval ${\displaystyle [1,n]}$, again in the limit, where the weight of an element ${\displaystyle a}$ is ${\displaystyle 1/a}$.
• The sequential density, defined as the limit (as ${\displaystyle i}$ goes to infinity) of the densities of the sets ${\displaystyle M(\{a_{1},\dots a_{i}\})}$ of multiples of the first ${\displaystyle i}$ elements of ${\displaystyle A}$. As these sets can be decomposed into finitely many disjoint arithmetic progressions, their densities are well defined without resort to limits.

A Behrend sequence is defined as a sequence ${\displaystyle A}$ for which the three densities ${\displaystyle M(A)}$ described by this theorem equal one.^[4] In this case, the upper natural density (taken using the superior limit in place of the inferior limit) and the natural density itself (the limit of the same sequence of values) must also equal one. However, there exist other sequences ${\displaystyle A}$ and their sets of multiples ${\displaystyle M(A)}$ for which the upper natural density differs from the lower density, and for which the natural density itself does not exist.^[5]

The theorem is named after Harold Davenport and Paul Erdős, who published it in 1936.^[6] Their original proof used the Hardy–Littlewood Tauberian theorem; later, they published another, elementary proof.^[7]