Erdős Problem #160
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics, 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
Colour each integer from \(1\) to \(N\). Erdős and Freud asked how few colours can suffice if every four-term arithmetic progression must use at least three distinct colours.
Let \(h(N)\) be the minimum number of colours meeting that condition. A progression has the form
The four entries may use three or four colours, but never only one or two. This condition is stronger than forbidding monochromatic four-term progressions and should not be confused with van der Waerden's theorem.
A small example
In \(\{1,2,3,4\}\) the only four-term progression is \((1,2,3,4)\). It must have at least three colours. For \(N\le3\) no four-term progression exists, so one colour suffices. Therefore \(h(4)=3\).
For \(N=5\), the progressions include \((1,2,3,4)\) and \((2,3,4,5)\). A colouring assigning three different colours to positions \(2,3,4\) and reusing them at the endpoints satisfies both constraints, so \(h(5)\le3\). One colour on the entire interval is forbidden as soon as \(N\ge4\).
What is known
The sharp growth remains OPEN. The maintained Erdős #160 attributes the earlier upper estimate \(h(N)\ll N^{2/3}\) to a MathOverflow argument, and the stronger bound
to Zach Hunter's October 2025 observation, building on the methods of Deng, Tidor and Zhao in arXiv:2307.06914. Since \(\log3/\log22\approx0.3554\), this improves the older exponent.
The same source records the lower bound
for some \(c>0\), via Hunter's observation combined with modern results on sets avoiding three-term progressions, including work of Bloom–Sisask and Kelley–Meka. Both bounds tend to infinity but are far apart; they do not establish an exact power law. The reduction details in the external MathOverflow commentary have not been independently written out here.
GCL's current state
The pinned and current catalogue classify the problem OPEN. Original issue: #1429. The exact four-term/all-progression quantifier and no-two-colours condition are preserved. The cited construction and modern lower-bound deductions are source-attributed, not 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 models the colouring condition as a finite constraint satisfaction problem and searches exact minimum colourings for \(4\le N\le14\). Acceptance: enumerate every step \(d\) and start \(a\), enforce at least three distinct colours, prove \(h(4)=3\), and use a second checker to validate every purported witness and every impossibility certificate. Stop at finite enumeration and avoid treating finite-size patterns as an asymptotic law.
Sources and claim boundaries
- Maintained Erdős #160, bounds and 2025 Hunter commentary.
- Deng–Tidor–Zhao, arXiv:2307.06914, colouring construction methods.
- Original GCL source issue #1429.
No new asymptotic bound, independent modern-proof certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1429 — 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.