Problem #1097: Let $A$ be a set of $n$ integers

---

Progress

A problem Erdős posed in the 1989 problem session of Great Western Number Theory.

He states that Erdős and Ruzsa gave an explicit construction which achieved $n^{1+c}$ for some $c>0$, and Erdős and Spencer gave a probabilistic proof which achieved $n^{3/2}$, and speculated this may be the best possible.

In the comment section, Chan has noticed that this problem is exactly equivalent to a sums-differences question of Bourgain [Bo99], introduced as an arithmetic path towards the Kakeya conjecture: find the smallest $c\in [1,2]$ such that, for any finite sets of integers $A$ and $B$ and $G\subseteq A\times B$ we have\[\lvert A\overset{G}{-}B\rvert \ll \max(\lvert A\rvert,\lvert B\rvert, \lvert A\overset{G}{+}B\rvert)^c\](where, for example, $A\overset{G}{+}B$ denotes the set of $a+b$ with $(a,b)\in G$).

This is equivalent in the sense that the greatest exponent $c$ achievable for the main problem here is equal to the smallest constant achievable for the sums-differences question. The current best bounds known are thus\[1.77898\cdots \leq c \leq 11/6 \approx 1.833.\]The upper bound is due to Katz and Tao [KaTa99]. The lower bound is due to Lemm [Le15] (with a very small improvement found by AlphaEvolve [GGTW25]).