Erdős Problem #360
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: number 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
Fix a positive integer \(n\). Colour each of the integers \(1,2,\ldots,n-1\) with one of some number of colours. A monochromatic subset sum is a sum of distinct integers that all have the same colour. Let \(f(n)\) be the least number of colours for which one can arrange the colouring so that no monochromatic subset sum equals \(n\).
The distinctness condition matters: an integer may be used at most once in a sum, because the available objects are the elements of the set \(\{1,\ldots,n-1\}\). The question asks for the growth of \(f(n)\) as \(n\) becomes large. It is not asking whether \(n\) has some representation as an unrestricted sum, and it is not the different problem of avoiding a target sum inside an arbitrary subset of \(\{1,\ldots,n\}\).
The problem is Erdős Problem 360 in the original GCL issue. The maintained Erdős Problems entry attributes the question to Erdős and records its resolution through successive estimates.
A small example
The smallest nontrivial check already illustrates the definition. For \(n=5\), use two colour classes
The subset sums of \(C_1\) are \(0,1,2,3\), while those of \(C_2\) are \(0,3,4,7\). Neither list contains \(5\), so two colours suffice. One colour cannot suffice, because the single class \(\{1,2,3,4\}\) contains the distinct-element sums \(1+4=5\) and \(2+3=5\). Therefore the exact finite calculation is \(f(5)=2\).
This is an exact-arithmetic verification of one small instance, not numerical evidence for the asymptotic theorem. It checks neither the constants hidden in asymptotic notation nor the analytic and additive-combinatorial arguments needed for large \(n\).
What is known
The live entry reports the earlier bounds of Alon and Erdős and the improvement by Vu. The directly inspected primary source is David Conlon, Jacob Fox, and Huy Tuan Pham, “Subset sums, completeness and colorings,” arXiv:2104.14766v1, submitted 30 April 2021. In Section 1.2.1, Theorem 1.5, they use exactly the definition above and prove
where \(\phi(n)\) is Euler’s totient function. In particular, the paper supplies matching upper and lower bounds up to absolute constant factors. Its proof uses colourings organized by size and congruence information for the upper bound, and subset-sum structure for the lower bound.
The same paper identifies the earlier primary references as Noga Alon and Paul Erdős, “Sure monochromatic subset sums,” Acta Arithmetica 74 (1996), 269–272, and Van H. Vu, “Some new results on subset sums,” Journal of Number Theory (2007), 229–233. The live entry also gives Erdős and Graham, Old and new problems and results in combinatorial number theory (1980), p. 59, as the catalogue source for the question. Those references explain the historical chain; the Conlon–Fox–Pham paper is the source directly checked here for the final order of growth.
GCL's current state
The pinned catalogue evidence is the exact teorth/erdosproblems revision 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889, entry number: "360". At that revision the informal and overall status is solved, last updated 2025-08-31; the formal status is unformalized, and formalized is no.
The live page currently agrees with the solved mathematical status and displays the sharper formula, but it is a moving maintained page rather than the protected source lock. Its access date is 2026-10-13. The issue packet also states that the admitted FC-GDM-85F86371 provider snapshot contains no statement file for this problem. No pinned FormalConjectures theorem was located in this checkout. Thus the external theorem is evidence about the mathematics, while formal theorem availability, replay, and GCL certification remain separate questions.
There is also an important scope distinction inside the formula. The factor \(n/\phi(n)\) means that the answer can fluctuate with the prime divisors of \(n\); two nearby integers need not have comparable values for the same elementary reason. The theorem is therefore stronger than a bare statement such as \(f(n)=n^{1/3+o(1)}\): it records the arithmetic dependence that controls those fluctuations. The paper explains this phenomenon immediately after Theorem 1.5 and describes the result as confirming the conjectured order, not as producing a single universal exact integer value for every \(n\).
What remains
A useful bounded successor would first freeze a statement record containing the set-theoretic definition of \(f(n)\), the quantifiers in Theorem 1.5, the meaning of \(\Theta\), and the domain convention for logarithms. It could then formalize a finite lemma such as \(f(5)=2\), with explicit colour classes and exhaustive checking of the finitely many subsets. A later, separately scoped task could formalize the elementary upper-bound constructions for selected \(n\) or selected congruence classes.
The asymptotic theorem is a substantially larger target. A responsible formalization would need definitions for colourings, distinct subset sums, Euler’s totient, asymptotic comparison, and the imported additive-number-theory estimates. A successful finite replay would not certify the theorem, and a Lean declaration containing sorry would be a theorem interface with an unresolved proof, not a checked proof.
Sources and claim boundaries
The source chain used here is the original GCL issue, the pinned catalogue blob, the maintained problem page, and the checked Conlon–Fox–Pham primary paper. The paper’s arXiv source archive was read at SHA-256 8a61ce85e643a4708ac4a36308a9d316f94719642659587fc34090248259adcd; this identifies the inspected source bytes, not a GCL certification.
The catalogue status is not itself a proof, and the live page is not a formalization record. No claim is made here that GCL has independently verified the external proof, certified the mathematics, or accepted formal coverage. The original SOURCE RESULT/1 citation is authenticated original RESULT/1. Accepted coverage and editorial disposition remain matters for the applicable V2 ledger.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1630 — 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.