Erdős Problem #1097

declared status 'open'. Formalized: yes. 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$? Are there always $O(n^{3/2})$ many such $d$? Current best: He states that Erd\H{o}s and Ruzsa gave an explicit construction which achieved $n^{1+c}$ for some $c>0$, and Erd\H{o}s and Spencer gave a probabilistic proof which achieved $n^{3/2}$, and speculated this may be the best possible. 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]). Prize: no. Tags: additive combinatorics, number theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.