1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.