I'd like to prove that for a set of nonzero integers, call it $S$, there exist two disjoint subsets $S_1$ and $S_2$ such that $S_1$ and $S_2$ are sum-free (i.e., if $a,b \in S_i$, then $a+b \notin S_i$), and $$|S_1 \cup S_2| > 2 \frac{|S|}{3}.$$ I've seen a proof of the fact that any set of nonzero integers $S$ has a sum-free subset of cardinality at least $\frac{|S|}{3}$ using a probabilistic argument (e.g. pages 1-2 here), but I'm not sure how to adapt/generalize the proof to the problem above.
Any help or hint appreciated!
Best Answer
This is simply a slight modification of the proof in the link.
Pick a prime $p > \max_{s \in S}\{|s|\}$ such that $p \equiv 1 \mod 6$, write $p = 6k + 1$ and let $S_1 = \{2k+1, 2k+2, \ldots, 4k+1\}$, $S_2 = \{k+1,\ldots,2k\}$ and $S_3 = \{4k+2,\ldots,5k+1\}$. Note that $S_1$ is sum free as before. By a simple calculation, so is $S_2 \cup S_3$ (consider all cases of taking two elements from either set). Finally, write $T = S_1 \cup S_2 \cup S_3$ (note: $|T| = 4k+1$).
For a fixed $s \in S$ and $\alpha \in \{1,\ldots, p -1\} = \mathbb{Z}^*_p$ chosen uniformly at random, the random variable $\alpha \cdot s$ distributes uniformly over $\mathbb{Z}^*_p$ (as $p > |s|$) and so, letting $\mathbb{I}_\alpha(s)$ denote an indicator random variable which is $1$ iff $\alpha s \in T$ we get $\mathbb{E}_\alpha[\mathbb{I}_\alpha(s)] = |T|/(p-1) > 2/3$.
By linearlity of expectation: $\mathbb{E}_\alpha[\sum_{s} \mathbb{I}_\alpha(s)] > |S|2/3$ and for an $\alpha$ which attains the expected value (or above), the elements mapped to $S_1$ and the elements mapped to $S_2 \cup S_3$ prove the claim.