Behrend's theorem

In arithmetic combinatorics, Behrend's theorem states that the subsets of the integers from 1 to n in which no member of the set is a multiple of any other must have a logarithmic density that goes to zero as n 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 n can be defined by setting the weight of each integer i to be 1/i, and dividing the total weight of the set by the nth partial sum of the harmonic series (or, equivalently for the purposes of asymptotic analysis, dividing by log⁡n). 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 {1,…n} 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 O(1/log⁡log⁡n).

For infinite primitive sequences, the maximum possible density is smaller, o(1/log⁡log⁡n).

Examples

There exist large primitive subsets of {1,…n}. 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 k≈log⁡log⁡n, the set of numbers with exactly k prime factors (counted with multiplicity) has logarithmic density

1+o(1)2πlog⁡log⁡n,

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.