Behrend's theorem
In arithmetic combinatorics, Behrend's theorem states that the subsets of the integers from 1 to formula_1 in which no member of the set is a multiple of any other must have a logarithmic density that goes to zero as formula_1 becomes large. The theorem is named after Felix Behrend, who published it in 1935. Statement. The logarithmic density of a set of integers from 1 to formula_1 can be defined by setting the weight of each integer formula_4 to be formula_5, and dividing the total weight of the set by the formula_1th partial sum of the  harmonic series (or, equivalently for the purposes of asymptotic analysis, dividing by formula_7). The resulting number is 1 or close to 1 when the set includes all of the integers in that range, but smaller when many integers are missing, and particularly when the missing integers are themselves small. A subset of formula_8 is called "primitive" if it has the property that no subset element is a multiple of any other element. 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 formula_9. For  infinite primitive sequences, the maximum possible density is smaller, formula_10. Examples. There exist large primitive subsets of formula_8. However, these sets still have small logarithmic density. 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 formula_17, the set of numbers with exactly formula_18 prime factors (counted with multiplicity) has logarithmic density exactly matching the form of Behrend's theorem. 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. History. This theorem is known as Behrend's theorem because Felix Behrend proved it in 1934, and published it in 1935. Paul Erdős proved the same result, on a train ride in 1934 in which he traveled from Hungary to Cambridge to escape the growing anti-semitism of Europe at that time, but on his arrival he discovered that Behrend's proof was already known.