On subsets of the integers in which no member of the set is a multiple of any other
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
formula_19
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 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.
References.
 ;templatestyles src="Reflist/styles.css" / ;