In arithmetic combinatorics, Behrend's theorem states that the subsets of the integers from 1 to
in which no member of the set is a multiple of any other must have a logarithmic density that goes to zero as
The theorem is named after Felix Behrend, who published it in 1935.
th partial sum of the harmonic series (or, equivalently for the purposes of asymptotic analysis, dividing by
Behrend's theorem states that the logarithmic density of any primitive subset must be small.
More precisely, the logarithmic density of such a set must be
[1] For infinite primitive sequences, the maximum possible density is smaller,
Both of these subsets have significantly smaller logarithmic density than the bound given by Behrend's theorem.
Resolving a conjecture of G. H. Hardy, both Paul Erdős and Subbayya Sivasankaranarayana Pillai showed that, for
prime factors (counted with multiplicity) has logarithmic density exactly matching the form of Behrend's theorem.
[3] This example is best possible, in the sense that no other primitive subset has logarithmic density with the same form and a larger leading constant.
[5] Paul Erdős proved the same result, on a 1934 train trip from Hungary to Cambridge to escape the growing anti-semitism in Europe, but on his arrival he discovered that Behrend's proof was already known.