Erdős Problem #948

Erdős Problem 948

Statement and result.

Is there a function $f:\mathbb N\to\mathbb N$ and a finite number $k\geq2$ such that every $k$-colouring admits a strictly increasing sequence $a_1<a_2<\cdots$ with $a_n<f(n)$ for infinitely many $n$, whose nonempty finite sums omit a colour? No. We reconstruct the known stronger negative result: for every $f$, there is a colouring $c_f:\mathbb N\to\mathbb N$ such that every sequence obeying that growth condition has finite sums of every positive-integer colour.

The construction is credited to GPT Pro, prompted by Liam Price. The discussion on the problem page includes a sketch by Thomas Bloom. We supply the tail and separation details needed to turn that sketch into a complete proof. The sequence is one fixed infinite sequence throughout; it is not allowed to depend on a finite truncation parameter.

The scale function and colouring.

Replace $f$ by the nondecreasing integer majorant \[ F(t)=\max\{2,t,f(1),\ldots,f(t)\}. \] For every integer $h\geq0$, set \[ G(h)=h+2+\left\lceil\log_2 F(2^{h+2})\right\rceil. \] Then $G$ is nondecreasing and $G(h)\geq h$.

For a positive integer $m$, let $D(m)$ be the finite nonempty set of positions of the ones in its binary expansion, with the units digit in position zero. Cover this set greedily as follows. Let $h_1=\min D(m)$, cover all positions in $[h_1,G(h_1)]$, then let $h_2$ be the first remaining position and cover $[h_2,G(h_2)]$, and continue until none remain. Each step removes at least one position, so this terminates. Define $c_f(m)$ to be its number of steps. This defines a positive-integer colour for every $m$.

A block sum with high valuation and colour one.

Suppose $(a_i)$ is strictly increasing and $a_n<f(n)$ for infinitely many $n$. Fix a discarded initial segment length $M\geq0$ and a desired binary-position bound $B\geq0$. We claim that there is a nonempty interval of indices $I\subseteq\{M+1,M+2,\ldots\}$ such that, with $m=\sum_{i\in I}a_i$ and $s=v_2(m)$, \[ s>B,\qquad D(m)\subseteq[s,G(s)],\qquad c_f(m)=1. \tag{1} \] Choose a sufficiently large good index $n$, meaning $a_n<f(n)$, so that $n\geq2M+2$ and $h=\lfloor\log_2 n\rfloor-1>B$. We have \[ 2^{h+1}\leq n<2^{h+2},\qquad n-M\geq2^h. \] Take the first $2^h$ terms after index $M$, and consider their $2^h+1$ initial partial sums, including zero. Two of those sums are congruent modulo $2^h$. Their positive difference is the sum of a nonempty consecutive block $I$ of these indices and is divisible by $2^h$. It is positive because all $a_i$ are positive. Thus $s=v_2(m)\geq h>B$.

All indices used are at most $n$, so monotonicity of $(a_i)$ gives \[ 0<m\leq n a_n<n f(n) \leq 2^{h+2}F(2^{h+2})\leq2^{G(h)}. \] Consequently every occupied binary position of $m$ lies between $s$ and $G(h)$. Since $s\geq h$ and $G$ is nondecreasing, $G(h)\leq G(s)$. This proves $1$. Notice that the choice of a large good index is still possible after discarding any finite initial segment; no unproved growth bound for a reindexed tail is being used.

Separated blocks produce every colour.

Apply $1$ repeatedly to construct disjoint successive index intervals $I_1,I_2,\ldots$. Put \[ m_j=\sum_{i\in I_j}a_i,\qquad s_j=v_2(m_j). \] After choosing $I_j$, take $M=\max I_j$ and $B=G(s_j)$ in the next application. This ensures \[ D(m_j)\subseteq[s_j,G(s_j)],\qquad s_{j+1}>G(s_j). \tag{2} \] For any $r\geq1$, the integer \[ b_r=m_1+\cdots+m_r =\sum_{i\in I_1\cup\cdots\cup I_r}a_i \] is a finite sum of distinct terms of the original sequence. The binary supports in $2$ are disjoint, so adding the $m_j$ causes no carries. The occupied positions of $b_r$ are exactly their union.

The greedy covering of $D(b_r)$ first starts at $s_1$ and covers the entire first support, while leaving all later supports untouched by $2$. Its next start is exactly $s_2$, and the same statement repeats. There are exactly $r$ covering steps. Hence \[ c_f(b_r)=r\qquad\text{for every }r\geq1. \] Thus the finite-sums set contains every positive-integer colour.

The finite-colour question follows.

For any given $k\geq2$, define \[ c_{f,k}(m)=1+\left((c_f(m)-1)\bmod k\right). \] Every sequence satisfying the growth condition has finite sums of colours $1,\ldots,k$, because it already has a sum of each corresponding colour under $c_f$. Therefore its finite-sums set omits no colour. This gives a counter-colouring for every proposed pair $(f,k)$, which is the full negation of the original assertion.

The construction concerns nonempty finite sums of positive integers. If the problem also includes the empty sum or asks for a colouring of all integers, assigning colours arbitrarily to zero and the negative integers does not affect the obstruction on the positive finite sums.

Attribution and assessment.

See https://www.erdosproblems.com/948 and https://www.erdosproblems.com/forum/thread/948, checked 24 September 2026. Price posted the disproof on 21 June 2026; Bloom's 6 July 2026 explanation describes the greedy binary-support colouring used here. The older sentence in the editorial calling the question open is superseded by its later resolution paragraph and discussion. Every mathematical ingredient in the proof above is elementary and supplied explicitly: majorization, the pigeonhole block, valuation separation, absence of carries, and finite-colour reduction. No novelty or local Lean verification is claimed.

Completion rate estimate: 100%.

Is there a function $f(n)$ and a $k$ such that in any $k$-colouring of the integers there exists a sequence $a_1<\cdots$ such that $a_n<f(n)$ for infinitely many $n$ and the set\[\left\{ \sum_{i\in S}a_i : \textrm{finite }S\right\}\]does not contain all colours? Erdős initially asked whether this is possible with the set being monochromatic, but Galvin showed that this is not always possible, considering the two colouring where, writing $n=2^km$ with $m$ odd, we colour $n$ red if $m\geq F(k)$ and blue if $m<F(k)$ (for some sufficiently quickly growing $F$). This is open even in the case of $\aleph_0$-many colours. This is asking about a variant of Hindman's theorem (see [532] ).

FORMAL RESTATEMENT

Fix $k\in\mathbb{N}$ and a function $f:\mathbb{N}\to\mathbb{N}$. A $k$-colouring of the positive integers is a map $c:\mathbb{N}\to\{1,2,\dots,k\}$. Given a strictly increasing sequence of positive integers $a_1<a_2<\cdots$, define its finite-sums set \[ \mathrm{FS}(a_i) := \Big\{\sum_{i\in S} a_i : S\subseteq \mathbb{N} \text{ finite, nonempty}\Big\} \subseteq \mathbb{N}. \] Question: Do there exist some $k\ge 2$ and some function $f$ such that for every $k$-colouring $c$ there exists an increasing sequence $(a_i)$ with

1. $a_n < f(n)$ for infinitely many $n$, and
2. $c(\mathrm{FS}(a_i))\ne \{1,2,\dots,k\}$ (i.e. $\mathrm{FS}(a_i)$ omits at least one colour).

QUICK LITERATURE/CONTEXT CHECK

I do not use external results beyond what is in the problem text. The text states that the stronger requirement "$\mathrm{FS}(a_i)$ is monochromatic" is not always possible under the growth constraint, due to a construction of Galvin using a 2-adic valuation based colouring with a rapidly growing threshold function $F$.

ATTACK PLAN

Proof-track ideas.

• Try to obtain a positive answer for some $k\ge 3$ by weakening the target from monochromaticity to omitting at least one colour, perhaps allowing a bounded-growth subsequence.
• Seek finite (compactness-type) reductions: show that if the statement fails, there is a finite colouring on $[1,N]$ obstructing all sequences with many small terms.

Disproof-track ideas.

• Generalize Galvin-type colourings to $k\ge 3$ to force any finite-sums set coming from a sequence with infinitely many "small" terms to hit all colours.

WORK

Fast sanity checks (toy colourings).

• For the 2-colouring by parity, the sequence $a_n=2n$ satisfies $a_n<3n$ for all $n$, and $\mathrm{FS}(a_i)$ consists only of even numbers, hence omits the odd colour. So for some colourings the desired conclusion is easy.
• However, the question asks for a uniform $(k,f)$ that works for every $k$-colouring.

Lemma 948.1 (for $k=2$, "omits a colour" $\Leftrightarrow$ monochromatic).

Let $k=2$ and let $c:\mathbb{N}\to\{\text{red},\text{blue}\}$ be a 2-colouring. For any sequence $(a_i)$, the set $\mathrm{FS}(a_i)$ omits a colour if and only if it is monochromatic.

Proof. If $\mathrm{FS}(a_i)$ is monochromatic, it uses only one of the two colours, hence omits the other. Conversely, if $\mathrm{FS}(a_i)$ omits one of the two colours, then every element of $\mathrm{FS}(a_i)$ has the remaining colour, i.e. it is monochromatic. $\Box$

Lemma 948.2 (unique representation for superincreasing sequences).

Suppose $(a_i)$ satisfies the superincreasing condition \[ a_{n+1} > \sum_{i=1}^n a_i \quad\text{for all }n\ge 1. \] Then every $s\in \mathrm{FS}(a_i)$ has a unique representation $s=\sum_{i\in S} a_i$ with $S$ finite.

Proof. Assume $\sum_{i\in S} a_i = \sum_{i\in T} a_i$ with distinct finite sets $S\ne T$. Let $j$ be the largest index in the symmetric difference $S\triangle T$. Without loss of generality, assume $j\in S\setminus T$. Then \[ 0 = \sum_{i\in S} a_i - \sum_{i\in T} a_i = a_j + \sum_{i\in S\cap[1,j-1]} a_i - \sum_{i\in T\cap[1,j-1]} a_i. \] Taking absolute values and using that all terms are positive, \[ a_j = \Big|\sum_{i\in T\cap[1,j-1]} a_i - \sum_{i\in S\cap[1,j-1]} a_i\Big| \le \sum_{i=1}^{j-1} a_i. \] This contradicts the superincreasing hypothesis applied at $n=j-1$, which gives $a_j>\sum_{i=1}^{j-1} a_i$. Therefore no two distinct finite subsets can yield the same sum. $\Box$

VERIFICATION

• Lemma 948.1: checked both directions rely only on having exactly two colours.
• Lemma 948.2: checked the "largest differing index" argument forces the contradiction because the remaining sums involve only indices $<j$.
• Edge conventions: I defined $\mathrm{FS}(a_i)$ using nonempty finite $S$ so that $0$ is excluded (the problem statement does not specify whether $S=\emptyset$ is allowed; including or excluding $0$ does not change the "omits a colour" question unless a colouring treats $0$ specially).

FINAL

UNRESOLVED (i) Strongest proved partial result: for $k=2$ the requirement "$\mathrm{FS}(a_i)$ omits a colour" is equivalent to "$\mathrm{FS}(a_i)$ is monochromatic" (Lemma 948.1). Thus any negative result for the monochromatic version under growth constraints (such as the Galvin construction described in the problem text) automatically blocks $k=2$. (ii) First gap: produce either (a) some explicit $k\ge 3$ and $f$ and a proof that the statement holds for all $k$-colourings, or (b) for each candidate $(k,f)$ construct a $k$-colouring forcing every sequence with $a_n<f(n)$ infinitely often to have $\mathrm{FS}(a_i)$ hit all $k$ colours. (iii) Top 3 next moves:

1. Try to generalize Galvin's 2-adic-threshold colouring to $k\ge 3$ in a way that forces colour-surjectivity on finite-sums sets generated by "slow-growing" sequences.
2. Attempt a positive result for $k=3$ by allowing $\mathrm{FS}(a_i)$ to occupy only 2 of the 3 colours: look for a combinatorial selection argument producing a subsequence with controlled growth and restricted colour set.
3. Implement finite searches: for small $k$ and small bounds $f(n)$, brute-force all colourings of $[1,N]$ to see whether every colouring admits a short initial segment whose finite sums miss a colour; look for patterns that could extend to an infinite construction.

(iv) Minimal counterexample structure (to a positive answer): a colouring $c$ for which every sequence $(a_i)$ having infinitely many indices with $a_n<f(n)$ generates a finite-sums set that is colour-surjective; such a colouring would likely encode information at many scales (e.g. via valuations or growth thresholds) so that subset sums inevitably realize all colours.