Estimate the Folkman numbers F(k): a monochromatic k-set with all subset sums one colour (Erdős #531)
Statement
For $k\geq 1$ let $F(k)$ be the least $N$ such that every $2$-colouring of $\{1,\ldots,N\}$ contains a set $A$ of size $k$ for which all non-empty subset sums $\sum_{a\in S}a$ (over $\emptyset\neq S\subseteq A$) receive the same colour. Estimate the growth of $F(k)$.
Acceptance. FULLY RESOLVES: determine the true growth rate of $F(k)$ up to the stated precision — matching upper and lower bounds (a full proof), for instance reducing the tower-type upper bound to double-exponential to meet the lower bound, or lifting the lower bound to a tower. ADVANCES: improve either bound strictly beyond those stated in background, with proof — a lower bound exceeding $2^{2^{k-1}/k}$ via an explicit colouring construction with a proof of subset-sum-avoidance, or the first sub-tower (e.g. multiply-exponential) upper bound with proof; OR determine an exact small Folkman number such as $F(2)$, or certified rigorous bounds on $F(3)$, via an exhaustive or SAT-based colouring search delivered with a reproducible certificate (a colouring witnessing the lower bound, and an exhaustiveness proof for the upper bound). Anchor any bound claim to the values stated in background. Deliver the proof/construction, or the search code plus certified value/bounds.
Background
Posed by Erdős [Er73]. The finiteness of $F(k)$ — that such a monochromatic subset-sum-closed $k$-set is forced — is Folkman's theorem, established independently by Sanders and by Folkman and also a consequence of Rado's theorem. The known lower bounds are large: Erdős and Spencer [ErSp89] proved $F(k)\geq 2^{ck^2/\log k}$ for a constant $c>0$, and Balogh, Eberhard, Narayanan, Treglown, and Wagner [BENTW17] improved this to $F(k)\geq 2^{2^{k-1}/k}$ (double-exponential in $k$). The upper bounds coming from the standard proofs (via Hindman's theorem / the Graham–Rothschild machinery) are tower-type in $k$, so the gap between the known lower and upper bounds is enormous. Listed as open on erdosproblems.com/531 (fetched 2026-07-21, status 'open'); no cash prize. The attacker's tool: SAT / exhaustive colouring search to pin exact small values (e.g. $F(2)$) and rigorous bounds on $F(3)$; explicit $2$-colouring constructions certifying improved lower bounds; and analytic work attacking the tower-type upper bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #531 (T. F. Bloom) | website |
| REF-02 | Folkman's theorem (Wikipedia) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.