Erdős Problem #54
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: number theory, ramsey theory.
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
Color every element of an infinite set of positive integers with one of two colors. Can every sufficiently large integer be written as a sum of distinct elements all of one color? Erdős asked how sparse such a set can be. Conlon, Fox and Pham determined the optimal quadratic-logarithmic counting scale.
Registered statement:
A set of integers \(A\) is Ramsey \(2\)‑complete if, whenever \(A\) is \(2\)‑coloured, all sufficiently large integers can be written as a monochromatic sum of elements of \(A\).
A small example
Let \(S\) be a finite sequence of positive integers, and let \(\Sigma(S)\) be its distinct-element subset sums. For positive integers \(m,q\),
To verify it, expand the product. Each chosen subcollection with sum \(s\le m\) contributes
Hence the weighted total counts every representable \(s\le m\) at least once. Finally,
gives
For example, with \(S=\{3,5\}\), \(m=8\), and \(q=2\),
so the left side is \(3\), while the displayed upper bound is larger, as required. CFP use this lemma in their lower-bound coloring argument.
What is known
Burr and Erdős introduced Ramsey completeness using sequences and subset sums. Their notation \(P(A)\) means sums of distinct terms of the sequence \(A\).
They proved two things:
- Every Ramsey-complete sequence must have at least order \((\log N)^2\) terms up to \(N\) along an unbounded sequence of cutoffs; this is not a pointwise lower bound at every \(N\).
- They constructed an entirely Ramsey-complete sequence with growth of order at most \((\log N)^3\).
Their paper also explains that repeated values are convenient but not necessary; Theorem 1c gives a strictly increasing version. Burr–Erdős, 1985
Thus the open issue was whether the cubic upper bound could be reduced to the quadratic scale suggested by the lower bound.
Conlon, Fox, and Pham proved the stronger general theorem:
such that \(A\) is \(r\)‑Ramsey complete and
for all sufficiently large \(N\). They also proved that a sequence satisfying
eventually cannot be \(r\)‑Ramsey complete, for an absolute \(c>0\).
Setting \(r=2\) gives an \(O((\log N)^2)\) construction, together with a universal \(\limsup_{N\to\infty}|A\cap[1,N]|/(\log N)^2>0\) lower bound. Thus the quadratic-logarithmic growth order is optimal in this upper-versus-limsup-lower sense; a pointwise \(\Theta((\log N)^2)\) bound for every Ramsey-complete set does not follow. Problem 54 is solved in this extremal order-of-magnitude sense, although the optimal constants are not determined. Theorem 1.1
The key ingredient is CFP Lemma 2.8.
For large \(x\), choose roughly \(C r\log x\) integers from \([x,2x)\) having no small prime factor. The lemma says that one can choose them so that every subcollection containing at least a \(1/r\) fraction has subset sums covering a long interval of integers around \(x\log x\).
In any \(r\)‑coloring, one color occupies at least a \(1/r\) fraction of the selected block. Therefore that color alone represents the whole interval.
Now repeat this independently in every dyadic interval
The represented intervals overlap because their lengths and locations grow on the same \(x_i\log x_i\) scale. Concatenating the blocks gives a Ramsey-complete sequence. There are \(O(r\log x_i)\) elements in block \(i\), and only \(O(\log N)\) relevant blocks below \(N\), so
This is an existence proof: the block selection is obtained probabilistically, not as a short explicit formula.
GCL's current state
As of 2026-10-12, the maintained catalogue status is SOLVED. GCL source assignment and evidence (source report pending posting). This is an editorial source audit, not GCL proof certification or mathematical acceptance.
Source lock is ready. No blocker prevents the editorial result. A formalization would require creating a statement file because the admitted snapshot contains no formal statement for Problem 54. The full primary proof is not certified here line-by-line.
The original issue contains the authenticated RESULT/1 source report. This is source evidence, not independent mathematical certification or editorial admission.
What remains
- Input: the normalized statement, CFP21 Theorem 1.1, Lemma 2.8, Lemma 3.4, and Theorem 3.5.
- Target: formalize the finite-subset-sum predicate and verify Lemma 3.4, then formalize only the \(r=2\) interface “Lemma 2.8 plus dyadic concatenation implies \(A(n)=O((\log n)^2)\).”
- Method: one bounded proof pass; explicitly distinguish sets from sequences and distinct subset sums from repeated summands.
- Acceptance: all quantifiers compile to the normalized predicate; the resulting theorem has an explicit eventual threshold and \(O((\log n)^2)\) counting bound.
- Falsification: any use of repeated summands, an omitted “sufficiently large” quantifier, or an unjustified conversion from the CFP sequence formulation to sets.
- Stopping rule: stop after Lemma 3.4 and the \(r=2\) dyadic concatenation interface; do not attempt formalization of the full probabilistic Lemma 2.8.
Sources and claim boundaries
Maintained problem #54; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
- Original provenance: Paul Erdős, “Some of my favourite problems in number theory, combinatorics, and geometry,” Resenhas 2 (1995), 165–186, Problem p.172, recorded as
[Er95]on the live problem page. - Burr–Erdős: S. A. Burr and P. Erdős, “A Ramsey-type property in additive number theory,” Glasgow Mathematical Journal 27 (1985), 5–10. Their definitions and Theorems 1/2 appear on pp.1–3 of the primary scan. The paper also gives a strictly increasing entirely Ramsey-complete sequence in Theorem 1c. Primary paper
- Conlon–Fox–Pham: D. Conlon, J. Fox, and H. T. Pham, “Subset sums, completeness and colorings,” arXiv:2104.14766v1, submitted 30 April 2021. Theorem 1.1 is on p.2; Lemma 2.8 and the upper-bound deduction are on pp.11–12; the lower-bound proof is Lemma 3.4 and Theorem 3.5 on pp.26–29. arXiv record · PDF
- The pinned catalogue packet identifies revision
536408716724a2402bdfa7c1d764bf83d64a8c89, entrynumber: '54', blob4e60263a80af6207aca494d2e1388e44fa372889, statussolved, last update2025-08-31, and formalization statusunformalized. - The supplied live page was last edited 28 October 2025 and records the same statement and resolution by Conlon–Fox–Pham. This is drift in page date only; the mathematical statement and solved status agree. Formalized statement remains “No.” Live page
- The primary CFP proof is accessible and its theorem interfaces are checkable. I do not claim a line-by-line independent verification of all 75 pages of analytic and probabilistic estimates.
Reused only the supplied issue packet, the supplied live page, and public primary sources above. No sibling returns were inspected. This report does not claim Lean formalization, exact optimal constants, an explicit deterministic construction, publication certification beyond the cited sources, an award claim, or any mathematical acceptance decision. No posting, repository mutation, or commit was performed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1323 — 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.