Sum-free sets:

A subset \(A'\) of an abelian group \((A,+)\) is sum-free if there are no elements \(a,b,c \in A'\) with \(a+b = c\).

Theorem:

Every set of \(n\) non-zero integers contains a sum-free set of size at least \(\frac{n}{3}\).

Proof:

Let \(A\) be a set of non-zero integers with \(\lvert A \rvert = n\). Now, if we choose a real number \(\theta \in [0,1]\) we may define:

\begin{equation} A_{\theta} = \{a \in A | a \cdot \theta - \lfloor a \cdot \theta \rfloor \in (\frac{1}{3}, \frac{2}{3}) \} \end{equation}

and we’ll note that \(A_{\theta}\) is always sum-free since:

\begin{equation} \forall a, b, c \in (\frac{1}{3}, \frac{2}{3}), a + b \neq c \end{equation}

Moreover, if we sample uniformly from \([0,1]\) we will observe that:

\begin{equation} P(a \in A_{\theta}) = \frac{1}{3} \end{equation}

wince \(a_{\theta} \sim U([0,a])\). This implies that for any \(A \subset \mathbb{N}^*\) there is a sum-free subset with size at least \(\frac{\lvert A \rvert}{3}\).

References:

  1. Noga Alon & Joel Spencer. The probabilistic method. John Wiley & Sons. 2000.

  2. Yufei Zhao. Probabilistic Methods in Combinatorics. MIT. 2020.