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 ${\displaystyle n}$ in which no member of the set is a multiple of any other must have a logarithmic density that goes to zero as ${\displaystyle 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 ${\displaystyle n}$ can be defined by setting the weight of each integer ${\displaystyle i}$ to be ${\displaystyle 1/i}$, and dividing the total weight of the set by the ${\displaystyle n}$th partial sum of the harmonic series (or, equivalently for the purposes of asymptotic analysis, dividing by ${\displaystyle \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.[1]

A subset of ${\displaystyle \{1,\dots 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 ${\displaystyle O(1/{\sqrt {\log \log n}})}$.[1]

For infinite primitive sequences, the maximum possible density is smaller, ${\displaystyle o(1/{\sqrt {\log \log n}})}$.[2]

Examples

There exist large primitive subsets of ${\displaystyle \{1,\dots n\}}$. However, these sets still have small logarithmic density.

• In the subset ${\displaystyle \{\lceil (n+1)/2\rceil ,\dots n\}}$, all pairs of numbers are within a factor of less than two of each other, so no two can be multiples. It includes approximately half of the numbers from ${\displaystyle 1}$ to ${\displaystyle n}$. 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 subsets in which no two are multiples. But because all of its elements are large, this subset has low logarithmic density, only ${\displaystyle O(1/\log n)}$.
• Another primitive subset is the set of prime numbers. Despite there being fewer prime numbers than the number of elements in the previous example, this set has larger logarithmic density, ${\displaystyle O(\log \log n/\log n)}$, according to the divergence of the sum of the reciprocals of the primes.

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 ${\displaystyle k\approx \log \log n}$, the set of numbers with exactly ${\displaystyle k}$ prime factors (counted with multiplicity) has logarithmic density

${\displaystyle {\frac {1+o(1)}{\sqrt {2\pi \log \log n}}},}$

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.[4]

History

This theorem is known as Behrend's theorem because Felix Behrend proved it in 1934,[1] and published it in 1935.[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.[1]

References

1. Sárközy, A. (2013), "On divisibility properties of sequences of integers", in Graham, Ronald L.; Nešetřil, Jaroslav (eds.), The mathematics of Paul Erdős, I, Algorithms and Combinatorics, vol. 13 (2nd ed.), Berlin: Springer, pp. 221–232, doi:10.1007/978-3-642-60408-9_19, MR 1425189. See in particular p. 222.
2. Erdős, P.; Sárközy, A.; Szemerédi, E. (1967), "On a theorem of Behrend" (PDF), Journal of the Australian Mathematical Society, 7: 9–16, MR 0209246
3. Erdős, P. (1948), "On the integers having exactly ${\displaystyle K}$ prime factors" (PDF), Annals of Mathematics, Second Series, 49: 53–66, doi:10.2307/1969113, MR 0023279
4. Erdős, P.; Sárközy, A.; Szemerédi, E. (1967), "On an extremal problem concerning primitive sequences" (PDF), Journal of the London Mathematical Society, Second Series, 42: 484–488, doi:10.1112/jlms/s1-42.1.484, MR 0218325
5. Behrend, Felix (January 1935), "On sequences of numbers not divisible one by another", Journal of the London Mathematical Society, s1-10 (1): 42–44, doi:10.1112/jlms/s1-10.37.42