Sum-Free Sets of Integers with a Forbidden Sum

Abstract

A set of integers is sum-free if it contains no solution to the equation $x+y=z$. We study sum-free subsets of the set of integers $[n]=\{ 1, \ldots ,n \}$ for which the integer $2n+1$ cannot be represented as a sum of their elements. We prove a bound of $O(2^{n/3})$ on the number of these sets, which matches, up to a multiplicative constant, the lower bound obtained by considering all subsets of $B_n = \{ \lceil \frac{2}{3}(n+1) \rceil, \ldots, n \}$. A main ingredient in the proof is a stability theorem saying that if a subset of $[n]$ of size close to $|B_n|$ contains only a few subsets that contradict the sum-freeness or the forbidden sum, then it is almost contained in $B_n$. Our results are motivated by the question of counting symmetric complete sum-free subsets of cyclic groups of prime order. The proofs involve Freiman's 3k-4 theorem, Green's arithmetic removal lemma, and structural results on independent sets in hypergraphs.

Locations

• SIAM Journal on Discrete Mathematics - View
• arXiv (Cornell University) - View - PDF