Bounds for the local properties problem for difference sets

We consider the local properties problem for difference sets: we define $g(n,k,\mathrm{\ell })$ to be the minimum value of $\mid A-A\mid$ over all $n$-element sets $A\subseteq \mathbb{R}$ with the local property' that $\lvert A' - A'\rvert \geq \ell$ for all $k$-element subsets $A' \subseteq A$. We view $k$ and $\ell$ as fixed, and study the asymptotic behavior of $g(n, k, \ell)$ as $n \to \infty$. One of our main results concerns the quadratic threshold, i.e., the minimum value of $\ell$ such that $g(n, k, \ell) = Ω(n^2)$; we determine this value exactly for even $k$, and we determine it up to an additive constant for odd $k$. We also show that for all $1 < c \leq 2$, the threshold’ for $g(n,k,\mathrm{\ell })=\mathrm{\Omega }(n^c)$ is quadratic in $k$; conversely, for $\mathrm{\ell }$ quadratic in $k$, we obtain upper and lower bounds of the form $n^c$ for (not necessarily equal) constants $c>1$. In particular, this provides the first nontrivial upper bounds in the regime where $\mathrm{\ell }$ is quadratic in $k$.