Distinct common differences of 3-APs in an n-element integer set: pin down the maximal order (Erdős #1097)
Statement
Let $A$ be a set of $n$ integers. How many distinct $d$ can occur as the common difference of a three-term arithmetic progression in $A$ (a triple $a$, $a+d$, $a+2d$, all lying in $A$, with $d \neq 0$)? In particular, are there always $O(n^{3/2})$ many such $d$? The second question is now known to have a negative answer (see background), so the operative open problem is the first: determine the correct maximal order of magnitude — the largest exponent $\theta$ such that there exist $n$-element sets whose set of common differences of three-term progressions has size $n^{\theta-o(1)}$, together with a matching upper bound.
Acceptance. FULLY RESOLVES: determine the maximal order of magnitude — prove an upper bound of $n^{c+o(1)}$ on the number of distinct three-term-progression common differences valid for every $n$-element integer set, and construct sets achieving $n^{c-o(1)}$ for the same explicit exponent $c$; a complete proof is required (machine-checkable Lean/Coq preferred, else a full written proof with all steps). ADVANCES: (a) an improved lower bound — an explicit finite configuration (sets $A$, $B$ and relation $G \subseteq A\times B$, or an explicit family of integer sets) together with a reproducible verification script and the amplification argument certifying an exponent strictly better than the best lower bound stated in the background; (b) an improved upper bound — a proof giving an exponent strictly below the $11/6$ bound stated in the background; (c) a machine-checked formalization of the equivalence with the sums-differences problem or of either current record bound. Deliver the configuration plus verification code plus exponent derivation, or the proof file.
Background
Erdős posed this at the 1989 problem session of the Great Western (West Coast) Number Theory conference [GWNT89]; listed as open on erdosproblems.com/1097 (fetched 2026-07-13, status 'open', tagged 'number theory | additive combinatorics'). There Erdős reported an explicit Erdős–Ruzsa construction achieving $n^{1+c}$ distinct common differences for some $c>0$ and an Erdős–Spencer probabilistic construction achieving $n^{3/2}$, and speculated $n^{3/2}$ might be best possible. Chan observed (recorded in the site commentary) that the problem is exactly equivalent to Bourgain's sums-differences question [Bo99], which Bourgain put forward as an arithmetic approach to the Kakeya conjecture: determine the smallest $c \in [1,2]$ such that for all finite sets of integers $A,B$ and every $G \subseteq A \times B$ one has $$\lvert A \overset{G}{-} B \rvert \ll \max(\lvert A\rvert, \lvert B\rvert, \lvert A \overset{G}{+} B\rvert)^c,$$ where $A \overset{G}{+} B = \{a+b : (a,b) \in G\}$ and similarly for $\overset{G}{-}$. The maximal exponent achievable in the common-differences problem equals the smallest admissible $c$. The current record is $1.77898\cdots \le c \le 11/6 \approx 1.8333$: the upper bound is due to Katz–Tao [KaTa99], the lower bound to Lemm [Le15], with a very small further improvement found by the AlphaEvolve automated-search system [GGTW25]. Since $1.77898 > 3/2$, sets exist with far more than $n^{3/2}$ distinct common differences — the $O(n^{3/2})$ guess is false — but the correct order of magnitude remains open, with a gap between exponents $\approx 1.779$ and $11/6$. Lower bounds come from explicit finite configurations $G \subseteq A \times B$ whose sums/differences counts are verified exactly and then amplified (tensor-power style) to an exponent; the attacker's tool is programmatic search over such finite configurations (exactly the channel AlphaEvolve exploited) with exact certification of the achieved exponent, alongside proof-side work on the $11/6$ upper bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1097 (T. F. Bloom) | website |
| REF-02 | West Coast Number Theory 1989 problem session (source [GWNT89]) | website |
| REF-03 | Formalised statement (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.