Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED)

Statement

Let $H(k)$ be the smallest $N$ such that every finite colouring (any number of colours) of $[N]=\{1,\ldots,N\}$ contains a $k$-term arithmetic progression that is either monochromatic or rainbow (all $k$ terms differently coloured). The existence of $H(k)$ for every $k$ is the Erdős–Rado / Erdős–Gallai-style canonical van der Waerden theorem (an application of Szemerédi's theorem: with too many colours a rainbow AP is forced, with too few a monochromatic one is), so $H(k)$ is well defined and $H(k)^{1/k}\to\infty$ is easy.

Erdős and Graham (*Old and New Problems and Results in Combinatorial Number Theory*, Monographie No. 28 de L'Enseignement Mathématique, 1980) asked the sharper quantitative question: $$\lim_{k\to\infty}\frac{H(k)^{1/k}}{k}=\infty\ ?$$ i.e. does $H(k)$ grow super-exponentially relative to $k^k$ (not merely super-exponentially in $k$)? This is erdosproblems.com problem #190.

Facts

- Status: SOLVED (2026), affirmatively — $\lim_{k\to\infty}H(k)^{1/k}/k=\infty$ is now a theorem, resolving the positive direction Erdős and Graham asked about. - First resolution: Ji Ho Bae, "A resolution of Erdős Problem #190 via Erdős–Lovász, BCT, and Baker–Harman–Pintz," arXiv:2604.20588 (submitted 22 Apr 2026). Main theorem: for all sufficiently large $k$, $$\frac{H(k)^{1/k}}{k}\ \ge\ \left(\frac1e-\varepsilon(k)\right)\frac{k}{\log k},\qquad \varepsilon(k)=O(k^{-0.475}\log k)\to0,$$ equivalently $H(k)\ge k^{(2-o(1))k}$, which immediately gives the $\to\infty$ limit as a corollary. - Second, independent, and quantitatively stronger resolution: Jacob Fox and Zach Hunter, "Three-color van der Waerden numbers grow super-exponentially," arXiv:2606.02541 (June 2026) — a paper primarily about 3-colour van der Waerden numbers whose §6 separately derives new lower bounds on multicolour van der Waerden numbers that resolve "a problem of Erdős and Graham on canonical van der Waerden numbers" (quoted from the paper's own abstract), reportedly giving the stronger bound $H(k)\ge k^{(1-o(1))k\log k}$ — a full extra $\log k$ in the exponent over Bae's bound (per this wiki's sibling page Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?; not independently re-verified from full PDF text in this session — flagged in provenance above). - Reduction that both proofs share: the pigeonhole reduction $H(k)\ge W(k-1,k)$, where $W(r,k)$ is the (fixed-colour-count) van der Waerden number — any $(k-1)$-colouring of $[N]$ with no monochromatic $k$-AP *automatically* has no rainbow $k$-AP either (a rainbow $k$-AP needs $k$ distinct colours, but only $k-1$ are available), so a lower bound on $W(k-1,k)$ transfers immediately to a lower bound on $H(k)$. This converts the *canonical* (colour-count-unconstrained) problem into an *ordinary* van der Waerden lower-bound problem at a specific, growing colour count $r=k-1$. - Ingredient inputs to Bae's proof: (1) Erdős–Lovász, "Problems and results on 3-chromatic hypergraphs and some related questions" (in *Infinite and Finite Sets* II, 1975) — symmetric Lovász Local Lemma applied to the $k$-AP hypergraph gives $W(r,k)\gg r^{k-1}/k$ for *any* fixed $r$; (2) Blankenship, Cummings, Taranchuk, "A new lower bound for van der Waerden numbers," *European J. Combin.* 69 (2018) 163–168 — the recurrence $W(r,k) > p\,(W(r-\lceil r/p\rceil,k)-1)$ for primes $p\le k$, used here in restricted single-step form $W(r,k)\ge p\,(W(r-1,k)-1)$ to iterate the colour count upward; (3) Baker, Harman, Pintz, "The difference between consecutive primes, II," *Proc. London Math. Soc.* 83(3) (2001) 532–562 — supplies a prime $p^*\in[k-1-(k-1)^{0.525},\,k-1]$ close enough to $k-1$ to make the BCT-iteration step count sufficient. - Sibling problem on the same wiki: Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? asks the *fixed*-colour ($r=2$) analogue, $W(k)^{1/k}\to\infty$ for the ordinary van der Waerden number — still open. That page's own analysis flags the structural reason #190's technique does *not* transfer: the winning move here is letting the colour count $r_0=\lfloor k/\log k\rfloor$ grow with $k$, which is exactly the freedom #138's fixed $r=2$ setting does not have. - Origin of the problem statement: Erdős, P. and Graham, R. L., *Old and New Problems and Results in Combinatorial Number Theory*, L'Enseignement Mathématique Monographie No. 28 (1980) — cited as [ErGr80] in the erdosproblems.com bibliography per Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?'s provenance record.

Solution

Answer: yes — $H(k)^{1/k}/k\to\infty$, and in fact $H(k)$ grows at least like $k^{(2-o(1))k}$ (Bae), improved to $k^{(1-o(1))k\log k}$ (Fox–Hunter).

**The transferable technique — turn a "canonical" (any-number-of-colours) Ramsey-type question into an ordinary fixed-colour Ramsey lower-bound question *at a colour count that grows with the parameter*, then push the fixed-colour bound as far as it will go by chaining three off-the-shelf tools:**

1. Pigeonhole collapse of "canonical" to "monochromatic." The single move that makes the whole problem tractable: $H(k)\ge W(k-1,k)$. A canonical Ramsey number ("mono or rainbow") is *at least* as large as the ordinary van der Waerden number at exactly one colour short of the AP length, because with only $k-1$ colours a rainbow $k$-AP is combinatorially impossible — so *any* lower bound on ordinary $W(r,k)$ at $r=k-1$ instantly becomes a lower bound on the canonical number $H(k)$. This is the generic bridge: whenever a "no monochromatic-or-rainbow structure" question is in view, check whether "colours $=$ pattern-size $-1$" collapses it to an ordinary fixed-colour lower bound. 2. Let the colour count grow with $k$, not stay fixed. Prior applications of the Erdős–Lovász Lovász-Local-Lemma bound $W(r,k)\gg r^{k-1}/k$ always held $r$ fixed (as in the *ordinary* van der Waerden problem, Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?, where $r=2$ is baked into the question). Bae's key innovation is applying it instead at $r_0=\lfloor k/\log k\rfloor$ — a colour count that scales with $k$ — so the base of the exponential, $r_0^{k-1}$, itself grows with $k$, not just the exponent. This single reparametrization is what turns an exponential-in-$k$ bound into a genuinely super-$k^k$ one. 3. Iterate a recurrence to reach the target colour count. Erdős–Lovász alone only gives a bound *at* $r_0$; the problem needs a bound at $r=k-1$ (to feed step 1). The Blankenship–Cummings–Taranchuk recurrence $W(r,k)\ge p\,(W(r-1,k)-1)$ is applied repeatedly, once per unit increase in colour count, from $r=r_0$ up to a prime $p^*$ close to $k-1$ — each step multiplying the running bound by a factor of roughly $p^*$. 4. Use a strong prime-gap theorem to make the iteration count controllable. The number of BCT iterations needed, and the size of the prime $p^*$ available to drive them, is exactly what a classical prime-gap estimate (van der Waerden numbers being naturally prime-indexed via Berlekamp-style constructions) controls; Baker–Harman–Pintz's strong bound on gaps between consecutive primes guarantees a prime $p^*$ within $(k-1)^{0.525}$ of $k-1$, which is close enough that the accumulated iteration factor $(p^*)^{p^*-r_0}$ dominates and delivers the final super-exponential rate. 5. Collect the exponents. Combining the growing-base Erdős–Lovász term with the BCT-iteration multiplier yields, after optimizing $r_0$ against $\log k$, the stated bound $H(k)^{1/k}/k\ge(1/e-o(1))\,k/\log k\to\infty$.

Why this is the reusable part. The generic recipe — *(a) reduce a "canonical"/colour-count-unconstrained extremal question to an ordinary fixed-colour-count question via a pigeonhole/exhaustion argument at colour count "target size $-1$"; (b) if the fixed-colour bound is only ever proven for constant colour counts, check whether letting the colour count itself grow with the main parameter unlocks a bigger base; (c) chain a Local-Lemma-type existence bound with a "one-more-colour" recurrence, driven by a strong prime-gap or similar analytic-number-theory input to control the number of iterations* — is exactly the kind of composition that has no analogue yet for the fixed-colour sibling Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? (there $r=2$ is fixed by the problem, so step (b) is structurally unavailable), which is precisely why #190 fell while #138 remains open despite sharing the same $W(r,k)$ machinery.

Related

- Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — open sibling: the *fixed*-colour ($r=2$) van der Waerden analogue $W(k)^{1/k}\to\infty$. Directly documents this page's resolution and explains why the growing-colour-count trick that cracked #190 does not transfer to #138's fixed-$r$ setting. - Jacobsthal's function h(k) — finiteness and near-matching two-sided bounds — Jacobsthal's function $h(k)$, a separately-solved (finiteness / two-sided-bounds) sibling problem in the same "gaps/coverings among primes and residues" cluster that Baker–Harman–Pintz-type prime-gap inputs also touch. - Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent — the symmetric LLL existence argument (Erdős–Lovász 1975) supplying the base lower bound $W(r,k)\gg r^{k-1}/k$ that both this page's proof and Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?'s best-known bound are built on.