Erdős Problem #200
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: primes, arithmetic progressions.
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.
The question in plain language
Let \(L(N)\) be the largest integer \(k\) for which some nonconstant \(k\) term arithmetic progression of primes lies entirely within \(\{1,\ldots,N\}\):
Erdős and Graham asked whether this length is sublogarithmic:
The logarithm is natural. This is a precise asymptotic limit: \(L(N)/\log N\to0\), not merely a statement that the ratio stays bounded.
A small example
The primes \(5,11,17,23\) form a four-term arithmetic progression with common difference six. Thus \(L(23)\ge4\). For sufficiently long prime progressions, the common difference must be divisible by many small primes; otherwise one term in the progression is divisible by a small prime and must equal that prime. This elementary modular obstruction is the basis of the known logarithmic upper bound.
A finite computation finding a long progression does not refute the conjecture: the question concerns the ratio \(L(N)/\log N\) at arbitrarily large scales, not unusually large finite values.
What is known
OPEN. The maintained Erdős #200 records the classical prime-number-theorem consequence
This rules out growth faster than \(\log N\) but leaves the central question whether the ratio tends to zero. The difference between the multiplicative constant one and a term that tends to zero is the entire remaining challenge.
Green and Tao (2008) proved that the primes contain arbitrarily long arithmetic progressions. This guarantees that \(L(N)\to\infty\), but it gives no matching growth rate as a function of the largest prime \(N\) and hence does not contradict the proposed \(o(\log N)\) bound. Results on the longest progression inside arbitrary dense subsets of integers are not directly estimates for the sparse set of primes.
The source cites Erdős and Graham's original 1979 and 1980 questions. No inspected primary source proves or disproves the desired little-oh statement.
GCL's current state
Pinned and current status: OPEN. Original source issue: #1469. The exact prime-only predicate and nonzero progression step are preserved. The prime-number-theorem upper bound and Green–Tao theorem are source-attributed rather than new GCL proofs.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded task enumerates primes through \(N=100000\), finds \(L(N)\) at selected cutoffs using exact modular arithmetic, and returns one maximal progression witness and a separate exhaustive maximality certificate for each tested cutoff. Acceptance: reproduce \(5,11,17,23\), handle short progressions whose first prime divides the step separately, and report both \(L(N)\) and \(L(N)/\log N\) without extrapolating a limit from finite points.
A subsequent analytic task should isolate the exact small-prime divisibility lemma used in the PNT upper bound, including the exceptional small initial prime, and state which additional uniform estimate would be needed to achieve little-oh.
Sources and claim boundaries
- Erdős #200, classical prime-number-theorem bound and original questions [ErGr79], [ErGr80].
- GCL original issue #1469.
No new prime-progression bound, proof of little-oh or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1469 — 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.