Erdős Problem 1097

References:

• erdosproblems.com/1097
• [Bo99] Bourgain, J., On the dimension of {K}akeya sets and related maximal inequalities. Geom. Funct. Anal. (1999), 256--282
• [KaTa99] Katz, Nets Hawk and Tao, Terence, Bounds on arithmetic projections, and applications to the {K}akeya conjecture. Math. Res. Lett. (1999), 625--630.
• [Le15] Lemm, Marius, New counterexamples for sums-differences. Proc. Amer. Math. Soc. (2015), 3863--3868.
• [GGTW25] B. Georgiev, J. Gómez-Serrano, T. Tao, and A. Wagner, Mathematical exploration and discovery at scale. arXiv:2511.02864 (2025).

def Erdos1097.CommonDifferencesThreeTermAP (A : Finset ℤ) : Set ℤ

Given a finite set of integers A (modelled as a Finset ℤ), the set CommonDifferencesThreeTermAP A consists of all integers d such that there is a non-trivial three-term arithmetic progression a, b, c ∈ A with b - a = d and c - b = d.

Equations

• Erdos1097.CommonDifferencesThreeTermAP A = {d : ℤ | d ≠ 0 ∧ ∃ a ∈ A, ∃ b ∈ A, ∃ c ∈ A, b - a = d ∧ c - b = d}

theorem Erdos1097.erdos_1097 : False ↔ ∃ C > 0, ∀ (A : Finset ℤ), ↑(CommonDifferencesThreeTermAP A).ncard ≤ C * ↑A.card ^ (3 / 2)

The main conjecture: for any finite set of integers $A$ with $|A| = n$, the number of distinct common differences in three-term arithmetic progressions is $O(n^{3/2})$.

This conjecture was resolved negatively by showing that the problem is exactly equivalent to Bourgain's sums-differences question [Bo99], which was introduced as an arithmetic path towards the Kakeya conjecture. Under this equivalence:

• The greatest achievable exponent for this problem is equal to the smallest constant $c$ achievable for Bourgain's sums-differences question: $$|A -_G B| \ll \max(|A|, |B|, |A +_G B|)^c$$
• The $O(n^{3/2})$ prediction is disproved because the lower bound has been shown to satisfy $c \ge 1.77898$ (due to Zheng and AlphaEvolve [GGTW25], improving on Lemm [Le15]), which is strictly greater than $3/2 = 1.5$.
• The best known upper bound is $c \le 11/6 \approx 1.833$ (due to Katz and Tao [KaTa99]).
• While the specific $O(n^{3/2})$ prediction is resolved negatively, the general question of determining the exact optimal exponent $c$ remains open.

theorem Erdos1097.erdos_1097.variants.weaker (A : Finset ℤ) : (CommonDifferencesThreeTermAP A).ncard ≤ A.card ^ 2

A weaker bound has been proven: there are always at most $n^2$ such values of $d$.

theorem Erdos1097.erdos_1097.variants.lower_bound : ∃ c > 0, ∀ᶠ (n : ℕ) in Filter.atTop, ∃ (A : Finset ℤ), A.card = n ∧ c * ↑n ≤ ↑(CommonDifferencesThreeTermAP A).ncard

A trivial lower bound: for sufficiently large n there exist sets $A$ with $|A| = n$ that contain at least $\Omega(n)$ distinct common differences of three-term arithmetic progressions.