An algorithm for finding a nearly minimal balanced set in $\mathbb {F}_p$

Abstract:

For a prime $p$, we call a non-empty subset $S$ of the group $\mathbb {F}_p$ balanced if every element of $S$ is the midterm of a three-term arithmetic progression, contained in $S$. A result of Browkin, Diviš and Schinzel implies that the size of a balanced subset of $\mathbb {F}_p$ is at least $\log _{2} p + 1$. In this paper we present an efficient algorithm which yields a balanced set of size $(1 + o(1)) \log _{2} p$ as $p$ grows.