Skip to content

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

\[ a,\quad a+d,\quad a+2d, \]

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:

\[ d\in\{1,2,3,4\}. \]

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\):

\[ n^{1.77898\ldots}\lesssim \max_{|A|=n}|\{d:a,a+d,a+2d\in A\}| \lesssim n^{11/6} \]

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.

Back to catalogue · Compendium introduction