Erdős Problem #179
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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
For integers \(1\le k<\ell\) and a positive integer \(N\), consider subsets \(A\) of the positive integers with exactly \(N\) elements. Let \(F_k(N,\ell)\) denote the threshold number of nonconstant \(k\) term arithmetic progressions that forces \(A\) to contain an \(\ell\) term progression. Erdős asked how large this threshold can be and, particularly, whether
He also asked whether, for every fixed \(\ell>3\), the logarithmic growth exponent of \(F_3(N,\ell)\) tends to two. The universal quantifier is over all \(N\) element sets of integers, not only subsets of \([1,N]\). A progression is counted as a set, with positive common difference to avoid duplicate orientation.
A small example
The set \(A=\{1,2,3,4\}\) has two nonconstant three-term progressions, \((1,2,3)\) and \((2,3,4)\), and a four-term progression \((1,2,3,4)\). A much denser set can have many three-term progressions without a long progression when only a finite, carefully chosen universe is examined; determining the maximum over all \(\ell\) progression-free \(N\) sets requires an extremal argument.
If \(M\) is the maximum number of \(k\) term progressions in an \(N\) set containing no \(\ell\) term progression, then the smallest forcing threshold is \(M+1\). This precise plus-one convention matters for finite calculations but not for the large-scale estimates.
What is known
PROVED for the highlighted asymptotic questions. Fox and Pohoata, Sets without k-term progressions can have many shorter progressions, established an essentially quadratic growth law, \(F_k(N,\ell)=N^{2-o(1)}\) for fixed progression lengths \(3\le k<\ell\), together with
for some fixed \(C_\ell>0\). The bound is \(o(N^2)\), but its logarithmic growth exponent is still two. These statements are compatible: the saving grows more slowly than every positive power of \(N\).
The maintained Erdős #179, updated April 2026, also records refinements using improved quantitative versions of Szemerédi's theorem by Leng, Sah and Sawhney, of the form \(N^2/\exp((\log\log N)^{c_\ell})\). The source relates the extremal threshold to \(r_\ell(N)\), the maximum size of a subset of \([1,N]\) without an \(\ell\) term progression. Full quantitative proofs have not been independently reconstructed.
GCL's current state
The pinned and maintained catalogue classify #179 PROVED. Original source issue: #1448. The statement's exponent-two limit and a subquadratic upper bound are kept distinct. Any apparent formula with \(k=1\) or \(k=2\) must be normalized against trivial short-progression counting before transferring the general source claim.
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 fixture enumerates subsets of \([1,12]\) of size at most six, counts their three-term and four-term progressions exactly, and computes the finite maximum \(M\) among sets without four-term progressions. Acceptance: the four-element example has two three-term progressions and one four-term progression; the threshold equals \(M+1\). Finite extremal counts are not asymptotic source proofs.
Sources and claim boundaries
- Fox–Pohoata, Random Structures & Algorithms 58 (2021), primary original theorem.
- Maintained Erdős #179, Leng–Sah–Sawhney [LSS24] improvement.
- Original GCL issue #1448.
No new Szemerédi-type estimate, independent full proof replay or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1448 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.