Bounds for the local properties problem for difference sets

Abstract

We consider the local properties problem for difference sets: we define $g(n,k,\ell )$ to be the minimum value of $|A-A|$ over all $n$-element sets $A\subseteq \mathbb{R}$ with the `local property' that $|A^{\prime }-A^{\prime }|\ge \ell$ for all $k$-element subsets $A^{\prime }\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 )=\hat{I}\text{c◯}(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\le 2$, the `threshold' for $g(n,k,\ell )=\hat{I}\text{c◯}(n^c)$ is quadratic in $k$; conversely, for $\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 $\ell$ is quadratic in $k$.

45 pages, 4 figures