gpt pro 5.2 attempt on Math-6010
mathematicsErdős problemscontributionManuscript
Contents
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- $a_n < f(n)$ for infinitely many $n$, and
- $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.
- 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:- 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.
- 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.
- 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.