Bounds for the local properties problem for difference sets

Bounds for the local properties problem for difference sets, Discrete Analysis 2025:10, 45 pp.

It is well known, and not hard to show, that if $A$ is a set of $n$ real numbers, then its difference set $A-A$ has cardinality between $2n-1$ and $n^2-n+1$, with the former bound attained by arithmetic progressions and the latter by Sidon sets, that is, sets with no non-trivial solutions to the equation $x-y=z-w$. Note that in the second case, the “global” bound of $n^2-n+1$ is a consequence of a “local” property that concerns four elements at a time. And in fact, we can reformulate the condition that there are no non-trivial solutions to the equation $x-y=z-w$ as the condition that every subset of $A$ of size 4 has a difference set of size at least (and hence exactly) 13.

Several papers have investigated the extent to which the phenomenon just described can be generalized. Suppose we fix $k$ and $\ell$ and impose on $A$ the condition that every subset of $A$ of size $k$ has a difference set of size at least $\ell$. How large must $|A-A|$ be? This paper focuses on one particular natural regime, where one wishes to determine for which pairs $(k,l)$ the condition implies a quadratic lower bound on $|A-A|$ as the size of $A$ tends to infinity.

The previous best known upper bound (for $\ell$ in terms of $k$) was $\frac{3k^2}8-\frac{3k}4+2$ if $k$ is even, obtained by Anqi Li in 2022. This paper improves the upper bound for even $k$ to $\frac{k^2}4+1$ and gives an example to show that this bound is sharp – that is, $\frac{k^2}4$ is not sufficient to guarantee a quadratic lower bound. For odd $k$, it shows that $\frac{(k+1)^2}4$ is sufficient and $\frac{(k+1)^2}4-4$ is not sufficient, so it resolves the problem up to an additive constant 3.

The paper also obtains new results for other growth rates, though these are less precise. For example, it shows that for every $c\in(1,2)$ there are constants $a$ and $b$ in $(0,1/2)$ such that if $\ell\leq ak^2$ then a growth rate of $n^c$ for $|A-A|$ is not guaranteed and if $\ell\geq bk^2$ then it is. This is the first time a non-trivial upper bound for the size of $A-A$ has been proved when $\ell$ depends quadratically on $k$.

These results, and others in the paper, sit in a broader context of “local-properties problems” that dates back at least to a question of Erdős, Gyarfas and Hajnal, who asked how many colours are needed to colour the complete graph on $n$ vertices if every clique of size $k$ must use at least $\ell$ colours. (In full generality this question is clearly very hard, since if we set $\ell=2$, then we are asking for the graph to contain no monochromatic cliques of size $k$, which is tantamount to understanding multicolour Ramsey numbers. However, interesting results have been obtained in other regimes.) The paper, with its highly ingenious proofs and surprisingly strong results, makes a valuable contribution to this literature.