Probabilistic construction of small strongly sum-free sets via large Sidon sets

We give simple randomized algorithms leading to new upper bounds for combinatorial problems of Choi and Erdős: For an arbitrary additive group G let ${\displaystyle P_n\left(G\right)}$ denote the set of all subsets S of G with n elements having the property that 0 is not in S+S. Call a subset A of G admissible with respect to a set S from ${\displaystyle P_n\left(G\right)}$ if the sum of each pair of distinct elements of A lies outside S. Suppose first that S is a subset of the positive integers in the interval [2n,4n). Denote by f(S) the number of elements in a maximum subset of [n,2n) admissible with respect to S. Choi showed that ${\displaystyle f\left(n\right):=min\{\left|S\right|+f\left(S\right)\mid S\subseteq [2n,4n)\}=O{n}^{\frac{3}{4}})}$. We improve this bound to ${\displaystyle O{\left(n\ln \left(n\right)\right)}^{\frac{2}{3}})}$. Turning to a problem of Erdős, suppose that S is an element of ${\displaystyle P_n\left(G\right)}$, where G is an arbitrary additive group, and denote by h(S) the maximum cardinality of a subset A of S admissible with respect to S. We show ${\displaystyle h\left(n\right):=min\{h\left(S\right)\mid Gagroup,S\in P_n\left(G\right)\}=O{\left(\ln \left(n\right)\right)}^2)}$. Our approach relies on the existence of large Sidon sets.