Behrend's theorem

This article is about the theorem on multiple-free sets. For the theorem on arithmetic-progression-free sets, see Salem–Spencer set.

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 $\log n$ (or, equivalently for the purposes of asymptotic analysis, dividing by the $n$th partial sum of the harmonic series). 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.

There exist large subsets of $\{1,\dots n\}$ in which no two are multiples of each other. For instance, the subset $\{\lceil (n+1)/2\rceil ,\dots n\}$ has this property. By Dilworth's theorem (using a partition of the integers into chains of powers of two multiplied by an odd number) this subset has maximum cardinality among all such subsets. But because all of its elements are large, this subset has low logarithmic density, only $O(1/\log n)$. Behrend's theorem states that it is impossible to modify this example by replacing these large numbers by smaller ones, preserving the property that no two are multiples, and by so doing to achieve a logarithmic density that is bounded away from zero. More precisely, the logarithmic density of such a set must be $O(1/{\sqrt {\log \log n}})$.

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.

Related results

Behrend's bound of $O(1/{\sqrt {\log \log n}})$ on the density of a multiple-free sequence cannot be improved, because Subbayya Sivasankaranarayana Pillai constructed sequences with logarithmic density $\Omega (1/{\sqrt {\log \log n}})$. Concrete bounds on the constant factor in this formula for the density were given by Ian Anderson. However, for infinite multiple-free sequences, the maximum possible density is smaller, $o(1/{\sqrt {\log \log n}})$.