Growth of the Schur numbers f(k): is the least N forcing a monochromatic a+b=c exponential in k? (Erdős #483)
Statement
Let $f(k)$ be the minimal $N$ such that whenever $\{1,\ldots,N\}$ is $k$-coloured there is a monochromatic solution to $a+b=c$ (with $a=b$ allowed). The values $f(k)$ are the Schur numbers. Estimate $f(k)$. In particular, is it true that $f(k) < c^k$ for some constant $c > 0$?
Acceptance. FULLY RESOLVES: settle the exponential-growth question — either prove $f(k) \le c^k$ for an explicit constant $c$, or prove that $f(k)^{1/k} \to \infty$ (superexponential growth); a complete proof is required (machine-checkable Lean/Coq preferred, else a full written proof). ADVANCES: (a) an improved asymptotic lower bound — explicit colourings, with verification code certifying the absence of monochromatic solutions to $a+b=c$, which via the standard amplification argument yield $f(k) \ge \gamma^{k-O(1)}$ for a base $\gamma$ strictly greater than the $380^{1/5} \approx 3.2806$ stated in the background (the certificate must include the colouring, the checker, and the derivation of the base); (b) an improved upper bound — a proof of $f(k) \le g(k)$ with $g$ asymptotically strictly smaller than the $(e-\tfrac16)k!$ bound stated in the background; (c) a machine-checked formalization of a current record bound. Deliver the colourings plus checker code plus the amplified-base derivation, or the proof file.
Background
Posed by Erdős [Er61, p.233] and [Er65, p.188]; listed as open on erdosproblems.com/483 (fetched 2026-07-13, status 'open', tagged 'number theory | additive combinatorics | ramsey theory'). Schur's 1916 theorem guarantees $f(k)$ is finite; the known exact values are $f(1)=2$, $f(2)=5$, $f(3)=14$, $f(4)=45$ and $f(5)=161$ (OEIS A030126), the last established by Heule's landmark SAT computation [He17]. The best-known asymptotic bounds are $$(380)^{k/5} - O(1) \le f(k) \le (e - \tfrac{1}{6})\, k!,$$ where $380^{1/5} \approx 3.2806$. The lower bound is due to Ageron, Casteras, Pellerin, Portella, Rimmel and Tomasik [ACPPRT21] (improving earlier bounds of Exoo [Ex94] and Fredricksen–Sweet [FrSw00]); the upper bound is due to Xu, Xie and Chen [XXC02] (improving Whitehead [Wh73] and Wan [Wa97]); see Eliahou [El19] for more on the upper bound. A folklore observation gives $f(k) \le R(3;k) - 1$, where $R(3;k)$ is the $k$-colour Ramsey number for triangles — see Erdős #183 (erdosproblems.com/183). So the gap is exponential-versus-factorial: nothing better than $k!$-type growth is known from above, while from below the growth is at least exponential with base $\approx 3.28$. Closely related to the venue problem on improving the lower bound for the Schur number $S(6)$: that problem targets the next exact value, whereas this one targets the growth rate of $f(k)$. Attacker's tools: SAT and heuristic searches for large sum-free-style colourings whose base values feed the standard product/amplification constructions to raise the exponential lower-bound constant, and Ramsey-theoretic arguments on the upper-bound side.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #483 (T. F. Bloom) | website |
| REF-02 | OEIS A030126 — Schur's numbers (version 1) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.