Lesson 2

Theorem (Erdős, 1965). Any finite set \(A \subset \mathbb{Z}\setminus \{0\}\) contains a sum-free subset of size greater than \(|A|/3\).

Proof. Dirichlet's theorem on prime numbers in an arithmetic progression states that for any coprime numbers \(a,d \in \mathbb{Z}_{>0}\), there exist infinitely many prime numbers of the form \(dk+a\) (where \(k \in \mathbb{Z}_{>0}\)). Using this theorem, we take a prime number \(p=3k+2\) satisfying \(p > 2\max_{a \in A}|a|\). Then all elements of \(A\) are distinct nonzero residues modulo \(p\), i.e., \(A \subset \mathbb{Z}_{p}\).

It is easy to see that \(S=\{k+1,k+2, \dotsc, k+(k+1)\}\) is a sum-free subset of the group \(\mathbb{Z}_{p}\): the sum \((k+1)+(k+1)=2k+2\) is too large, and the sum \((2k+1)+(2k+1)=4k+2=k \bmod p\) is too small. Thus, we consider \(S\) as a subset of the additive group \(\mathbb{Z}_{p}\): we sum its elements modulo \(p\).

We choose a subset \(A\) as follows. Take a random element \(0 \neq t \in \mathbb{Z}_{p}\) and consider \[A_{t}=\{a \in A \colon at \bmod p \in S\} \ .\] It is clear that \(A_{t}\) is sum-free: for any \(a,b \in A_{t}\), we have \(at \bmod p \in S\) and \(bt \bmod p \in S\), but \((a+b)t \bmod p\) cannot belong to \(S\), since \(S\) is sum-free. We now show that for at least one \(t\), the set \(A_{t}\) has a sufficiently large size. To do this, we fix \(0 \neq a \in \mathbb{Z}_{p}\) and note that \[\{at\bmod p \colon 0 \neq t \in \mathbb{Z}_{p}\}=\mathbb{Z}_{p} \setminus \{0\} \ ,\] that is, \(at \bmod p\) takes all values \(1,\dotsc,p-1\) as \(t\) runs through \(1,\dotsc,p-1\) (indeed, if \(at_{1} \bmod p = at_{2} \bmod p\), then \(a(t_{1}-t_{2})\) is divisible by \(p\), which is possible only in the case \(t_{1}=t_{2}\)). Hence, for any \(a \neq 0\) we have \[\Pr[at \bmod p \in S]=\frac{|S|}{p-1}=\frac{k+1}{3k+1}> \frac{1}{3}.\] Thus, \[\operatorname{E}[|A_{t}|] =\sum_{a \in A}\Pr[at \bmod p \in S] > \frac{|A|}{3}\ .\] Therefore, for some \(t\), the size of \(A_{t}\) will be greater than \(|A|/3\).◼