Every set of n integers contains a sum-free subset of more than n/3 elements
Statement
A set of integers is *sum-free* if it contains no (with allowed) such that . Prove that every set of non-zero integers has a sum-free subset with more than elements.
Hint
Pick a prime larger than every , . The residues form a sum-free set modulo . Choose a random and keep the elements with in that middle third; compute the expected size.
Show solutionHide solution
Solution
Idea. Multiply by a random unit modulo a prime and keep the elements landing in a sum-free "middle third".
A suitable prime. There are infinitely many primes . Choose such a prime with for all ; then no is divisible by .
The middle third. Let , so . If , then . Modulo these sums are the residues and . None lies in . So is sum-free modulo .
Averaging. For uniform in and fixed , is uniform on the non-zero residues. So
By linearity, the expected number of with is more than . Hence some gives with more than elements.
is sum-free. If with , then multiplying by gives with , contradicting the sum-freeness of . ∎
Lesson. Randomise by a dilation in a finite field to bring a hard structure into a nice fixed set, and use linearity of expectation.