The board / number theory / #948
Erdős Problem #948
SOLVEDdatabase updated 2026-07-06
Resolved in some way other than a straight proof or disproof — usual for open-ended questions, or for multi-part problems whose parts went different ways.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Is there a function \(f(n)\) and a \(k\) such that in any \(k\)-colouring of the integers there exists a sequence \(a_1 < a_2 < \cdots\) such that \(a_n < f(n)\) for infinitely many \(n\) and the set \[\left\{ \sum_{i \in S} a_i : \textrm{finite nonempty } S \right\}\] does not contain all colours? A question of Erdős [Er77c] and Erdős and Galvin [ErGa91]. The answer is no: GPT-5.5 Pro (prompted by Price) showed that for every \(f\) there is a colouring of the integers such that the finite sums of every such sequence use all colours. The linked formal proof (Codex and GPT-5.6 Sol) gives, for every \(f\) and \(k \ge 1\), a colouring \(c : \mathbb{Z} \to \{0, \ldots, k - 1\}\) such that for every strictly increasing \(a\) with \(a_n < f(n)\) infinitely often and every colour, some nonempty finite sum of the \(a_i\) has that colour.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/948.Prizenone
Topicsnumber theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/948
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.