Erdős Problem #1097
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, additive combinatorics.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
A three-term arithmetic progression is a pattern
where \(d>0\). Given \(n\) distinct integers, how many different positive common differences can occur in such progressions?
Erdős Problem #1097 asks for the maximum possible count. Erdős speculated that the answer might always be at most a constant times \(n^{3/2}\). That particular estimate has since been disproved, although the correct growth exponent remains open.
A small example
For the set \(A=\{0,1,\ldots,8\}\), a progression of difference \(d\) requires \(2d\le8\). Exactly four positive differences occur:
For the sparse set \(\{0,1,3,4,9,10\}\) there are no three-term arithmetic progressions at all. The size of a set alone does not determine how many differences it supports.
These direct checks illustrate the counting convention; they do not address the maximal asymptotic exponent.
What is known
The maintained catalogue attributes the original question to Erdős at a 1989 number-theory meeting. It describes a connection observed by Chan to Bourgain's restricted sum-and-difference question arising in approaches to the Kakeya problem.
The catalogue reports that the exponent for the maximum number of differences lies between a lower construction of about \(1.77898\) and the Katz–Tao upper exponent \(11/6\approx1.8333\):
up to the technical losses and quantifiers in the cited results. The lower constructions trace through Lemm (2015) and a reported later AlphaEvolve improvement. Since even the lower exponent exceeds \(3/2\), the proposed \(O(n^{3/2})\) bound cannot hold.
The exact equivalence of the two extremal formulations, and the precise exponent losses in those works, still require an independent primary-paper audit.
GCL's current state
Authenticated source audit #2368 reproduces the finite examples and separates the disproved \(3/2\) estimate from the still-open correct exponent.
The frozen formal statement encodes a negative answer to the \(3/2\) conjecture, but its theorem body is not a GCL-replayed Lean proof.
This is a predetermined critical-review sample, and source review is incomplete.
What remains
Examine Bourgain (1999), Katz–Tao (1999), Lemm (2015) and the later evolutionary-search report. Check the exact correspondence between common differences and restricted sum-difference pairs, including definitions of the relevant exponents. Conduct independent critical review against the actual papers before admitting the manuscript.
Sources and claim boundaries
Erdős Problem #1097, status and bibliography; frozen formal-conjectures representation; GCL source return #2368. The exponent bounds are externally reported; exact small-set counts are independently verified. The general problem remains open, and this draft is unaccepted.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2368 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.