This page was last edited 10 April 2026. View history
| Likes this problem | Dogmachine |
| Interested in collaborating | None |
| Currently working on this problem | None |
| This problem looks difficult | None |
| This problem looks tractable | None |
| The results on this problem could be formalisable | None |
| I am working on formalising the results on this problem | None |
This problem is also mentioned as Problem 4.2 in "Some Ramsey-type theorems" by Erdos and Galvin (1991). (However, the version for $\aleph_0$ - many colors is not mentioned as it is in the earlier problem paper.) The main reason I mention this is that the Galvin example is explicitly described in Theorem 4.1 and this might help clear up some of the discussion in the comments.
Since Galvin excluded the cases of a $2$-colouring, I will explain that construction.
Assume such a sequence exists which is monochromatic.
$\textbf{red}$
There is a large $n$, such that $n>k_0 2^{k_0}$ with $F(k_0)>2^{k_0}f(n)$,
and all sumsets formed with $a_1, a_2 , \ldots, a_n$ (which are bounded by $f(n)$) are red.
By definition of the colouring, and the above choice, the pigeon hole principle says that there is a valuation $k< k_0$ such that at least $2^{k_0}$ values $a_i$ ($i \le n$) have $2$-adic valuation $k$.
Then (again by the pigeon hole principle) there are some (and we need no more than $2^{k_0}$ of them) of the $a_i$ who sum to a multiple of $2^{k+k_0}$.
Now $\sum a_i <2^{k_0} f(n)<F(k_0)<F( v_2( \sum a_i) ),$
and thus it was coloured blue, leading to a contradiction with being monochromatic.
$\textbf{blue}$
Since $k=v_2(a_1)$ is fixed, it is bounded.
Now for $n>2^{k+1}F(k)$, either there are half of $a_1$ up to $a_n$ with $2$-adic valuation bounded by $k$, or half of them above $k$.
In both cases, we can take a subset of them (with at least $(n-1)/2$ elements) whose sum $\sum a_i$ has $2$-adic valuation bounded by $k$.
But that sum is coloured red, leading to a contradiction.
(post to save time on failed attempt)
Two natural extensions of Galvin do not work already for $3$ colours;
*having multiple function $F_1,F_2$ (suff. quick growing) such that the size of the odd part (as function of $v_2$) determines the colour.
[one can ensure that the odd part is either small or big, but never medium]
*partitioning red (or blue) numbers depending on parity of $v_2$ into two colours
[by taking numbers with different $v_2$, one is free to avoid one of the two colours]
the sequence $a_1,\dots,a_n$ is not supposed to be allowed to depend on $n$.
also the counterexample seems over complicated to me. can't we simply color all $m>f(1)$ red, and $m\le f(1)$ blue? and for the multicolor version, why can't we have $m\le f(1)$ color one, $m\in (f(1),\sum_{i=1}^{f(1)} f(i)]$ color 2, and so on, so that all sufficiently large $n$ hit every color?
I'm not sure what you mean by not supposed to depend on $n$ - in [Er77c] Erdős certainly writes $a_1<\cdots <a_n$, so I interpreted that as choosing $n$ elements from $[1,f(n)]$. (He earlier discusses another question of his which fixes a single infinite sequence $a_i$ independent of $n$, for which Galvin's construction was originally introduced, but this problem is slightly different).
Regarding your colouring, we could take $A$ to be any subset of $[f(1),f(n)]$, so all subset sums are red, which works provided $f(n)-f(1)\geq n$ (but I assume you're talking about a different problem here, taking your first comment into account).
if the sequence can depend on $n$, then this should just be true by Folkman's Theorem (subset sums are partition regular).
Doh, of course. So on a third reading you're right, the sequence shouldn't depend on $n$ (my brain had inserted a $<$ where one didn't exist somehow).
So I think the revised problem is 'Is there an $f(n)$ and integer $k$ such that in any $k$-colouring there is a sequence $a_1<a_2<\cdots$ such that $a_n<f(n)$ for infinitely many $n$ and the set $\sum_{i\in S}a_i$ (as $S$ ranges over all finite sets) does not contain all colours?'
So your simple example still doesn't work (we only need $a_n<f(n)$ infinitely often).
Erdos wrote there are two potential versions to extend the initial question. In the first interpretation, he also adds a weaker statement for $\aleph_0$ with almost disjoint sets, but if the interpretation is as above, the latter should be a stronger variant, isn't it?
It may be those are indeed just directions of what would be a potential good question, without Erdos knowing yet what would be.
I think Galvin's construction is mistated. you want to infinitely flip flop between red and blue.
Note that it flips infinitely often, since the colouring depends on the $2$-adic valuation of the number.
I have given the explanation why the colouring works below.
We want $f: \mathbb Z^+ \to \mathbb Z^+$ and $k \ge 3$ such that there is an infinite sequence with $a_n<f(n)$ infinitely often.
For fixed $f$, this implies that Folkman's theorem does not work due to the additional restriction already for length $n$, and the infinite sequence is not implied either.
Log in to add a comment.
