Skip to content

Erdős problem 1097

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

Sources

The source's own material, retained exactly.

3 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

1097.lean

Retained formal statement1 of 3

The main conjecture: for any finite set of integers AA with ∣A∣=n|A| = n, the number of distinct common differences in three-term arithmetic progressions is O(n3/2)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 cc achievable for Bourgain's sums-differences question: ∣A−GB∣≪max⁡(∣A∣,∣B∣,∣A+GB∣)c|A -_G B| \ll \max(|A|, |B|, |A +_G B|)^c - The O(n3/2)O(n^{3/2}) prediction is disproved because the lower bound has been shown to satisfy c≥1.77898c \ge 1.77898 (due to Zheng and AlphaEvolve [GGTW25], improving on Lemm [Le15]), which is strictly greater than 3/2=1.53/2 = 1.5. - The best known upper bound is c≤11/6≈1.833c \le 11/6 \approx 1.833 (due to Katz and Tao [KaTa99]). - While the specific O(n3/2)O(n^{3/2}) prediction is resolved negatively, the general question of determining the exact optimal exponent cc remains open.

FormalConjectures/ErdosProblems/1097.leanErdos1097.erdos_10971 lineExact file
False ↔ ∃ C > 0, ∀ (A : Finset ℤ), ↑(Erdos1097.CommonDifferencesThreeTermAP A).ncard ≤ C * ↑A.card ^ (3 / 2)
SolvedProof has a holeformal conjecturesexternal proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.