A resolution of Erd\H{o}s Problem #190 via Erd\H{o}s-Lov\'asz, BCT, and Baker-Harman-Pintz

Ji Ho Bae

arxiv: 2604.20588 · v1 · submitted 2026-04-22 · 🧮 math.CO

A resolution of ErdH{o}s Problem #190 via ErdH{o}s-Lov\'asz, BCT, and Baker-Harman-Pintz

Ji Ho Bae This is my paper

Pith reviewed 2026-05-10 00:18 UTC · model grok-4.3

classification 🧮 math.CO

keywords arithmetic progressionsErdős problemsRamsey theoryLovász Local Lemmahypergraph coloringrainbow structuresprime gapsvan der Waerden numbers

0 comments

The pith

H(k)^{1/k}/k grows like k over log k for large k, forcing the limit to infinity and settling the positive direction of Erdős-Graham Problem 190.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a quantitative lower bound on H(k), defined as the smallest N forcing every coloring of the first N positive integers to contain either a monochromatic k-term arithmetic progression or a rainbow k-term arithmetic progression. It shows that this H(k) satisfies H(k)^{1/k}/k at least (1/e minus a term vanishing like k to the -0.475) times k over log k once k is large enough. This immediately yields that the ratio tends to infinity, answering one half of the Erdős-Graham question. The argument proceeds by applying the symmetric Lovász Local Lemma to the hypergraph of all k-APs inside a large interval, allowing the number of colors to grow slowly with k, then bootstrapping the resulting recurrence with a prime-gap theorem to reach the stated growth rate. A reader cares because the result converts a qualitative existence question into a concrete asymptotic statement about the minimal size needed to guarantee either a repeated color or all-distinct colors inside an arithmetic progression.

Core claim

There exists an absolute constant k0 ≥ 2 such that for all k ≥ k0, H(k)^{1/k}/k ≥ (1/e - ε(k)) · k/log k where ε(k) = O(k^{-0.475} log k) tends to zero; in particular H(k)^{1/k}/k = Ω(k/log k) and the limit as k tends to infinity is infinity. The proof combines the symmetric Lovász Local Lemma on the k-AP hypergraph on [N], the restricted Blankenship-Cummings-Taranchuk recurrence, the Baker-Harman-Pintz theorem on prime gaps, and the elementary reduction H(k) ≥ W(k-1,k).

What carries the argument

Symmetric Lovász Local Lemma applied to the k-term arithmetic-progression hypergraph on an interval of length N, with color count allowed to grow as floor(k/log k), then bootstrapped by the restricted BCT recurrence and BHP prime gaps.

If this is right

H(k) itself is at least on the order of (k/log k)^k for large k.
The quantity H(k)^{1/k}/k diverges to infinity.
Lovász Local Lemma applications that previously fixed the number of colors can be strengthened by letting the color count grow slowly with the progression length.
The only analytic input required is the Baker-Harman-Pintz prime-gap bound; everything else is combinatorial.
No matching upper bound on H(k)^{1/k}/k is currently known.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same growth rate may hold for the minimal size guaranteeing rainbow APs under weaker color-count assumptions.
The method could be adapted to other hypergraph Ramsey problems where the edge density permits a slowly growing number of colors.
Numerical checks for moderate k might reveal how soon the asymptotic regime begins.
The divergence of H(k)^{1/k}/k implies that both monochromatic and rainbow k-APs become unavoidable at scales far larger than exponential in k.

Load-bearing premise

The restricted form of the Blankenship-Cummings-Taranchuk recurrence continues to hold for the k-AP hypergraph even when the number of colors is permitted to grow as floor(k/log k).

What would settle it

An explicit coloring of some interval [N] with N smaller than (k/log k)^k that avoids both monochromatic and rainbow k-term arithmetic progressions would falsify the claimed lower bound.

read the original abstract

Let H(k) be the smallest N such that every finite coloring of [N] contains a monochromatic or rainbow k-term arithmetic progression. Erd\H{o}s and Graham asked whether $H(k)^{1/k}/k \to \infty$ (Problem #190 of the Erd\H{o}s Problems database). We prove that there is an absolute constant $k_0 \ge 2$ such that for all $k \ge k_0$, \[ H(k)^{1/k}/k \ge (1/e - \varepsilon(k)) \cdot k/\log k, \qquad \varepsilon(k) = O(k^{-0.475} \log k) \to 0 \text{ as } k \to \infty; \] in particular $H(k)^{1/k}/k = \Omega(k/\log k)$ and $\lim_{k\to\infty} H(k)^{1/k}/k = \infty$, resolving the positive direction of the Erd\H{o}s-Graham question. The argument combines three standard ingredients -- the symmetric Lov\'asz Local Lemma applied to the k-AP hypergraph on $[N]$, the restricted form of the Blankenship-Cummings-Taranchuk recurrence, and the Baker-Harman-Pintz prime-gap theorem -- together with the pigeonhole reduction $H(k) \ge W(k-1,k)$, and uses BHP as the only analytic black box. Previous applications of Erd\H{o}s-Lov\'asz had fixed $r$; the improvement here is that the $r^{k-1}$ base dominates once one allows the color count $r_0 = \lfloor k / \log k \rfloor$ to grow with $k$. No matching upper bound on $H(k)^{1/k}/k$ is known.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves lim H(k)^{1/k}/k = infinity with an explicit Omega(k/log k) lower bound by letting colors grow in the local lemma and bootstrapping via BCT, but the recurrence step at r ~ k/log k is the part that needs direct verification.

read the letter

The main takeaway is that this paper proves lim H(k)^{1/k}/k = infinity by establishing a lower bound of order k/log k for large k. It resolves the positive direction of the Erdős-Graham question #190. They get the growth by allowing the color count r0 to grow as floor(k/log k) instead of fixing it. That makes the r^{k-1} factor from the symmetric Lovasz local lemma on the k-term AP hypergraph strong enough after the root. They then apply the restricted form of the Blankenship-Cummings-Taranchuk recurrence to bootstrap from smaller instances and use the Baker-Harman-Pintz theorem to handle the pigeonhole step via H(k) at least the van der Waerden number W(k-1,k). No new theorems, just a better parameter choice than earlier fixed-r applications. The argument looks coherent on the surface and sticks to standard results without circularity or invented constants. The place to look closely is whether the restricted BCT recurrence remains valid when r grows with k at this rate. The stress test points out that without the recurrence the bound collapses to something that goes to zero, so this step is central. If the recurrence was only proved for fixed r or for r much smaller than k/log k, the bootstrap fails and the stated asymptotic is not justified. The paper should include a short note confirming the conditions under which the recurrence applies here. This work is aimed at combinatorialists interested in multicolored Ramsey numbers for arithmetic progressions. Anyone tracking Erdős problems or quantitative bounds in hypergraph Ramsey theory would get something out of it. It is worth sending to peer review because it addresses an open problem with a concrete improvement, and the tools are all external and verifiable. A referee can check the recurrence applicability in one pass.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that there exists an absolute constant k0 ≥ 2 such that for all k ≥ k0, H(k)^{1/k}/k ≥ (1/e − ε(k)) ⋅ k/log k where ε(k) = O(k^{-0.475} log k) → 0, with H(k) the smallest N forcing a monochromatic or rainbow k-term AP in any coloring of [N]. This implies H(k)^{1/k}/k = Ω(k/log k) and lim H(k)^{1/k}/k = ∞, resolving the positive direction of Erdős-Graham Problem #190. The argument applies the symmetric Lovász Local Lemma to the k-AP hypergraph on [N] with r = ⌊k/log k⌋ colors, invokes the restricted Blankenship-Cummings-Taranchuk recurrence to bootstrap, uses the Baker-Harman-Pintz prime-gap theorem, and reduces via the pigeonhole H(k) ≥ W(k−1,k).

Significance. If the derivation holds, the result is significant: it is the first quantitative resolution of the Erdős-Graham question in the positive direction, improving on fixed-r Erdős-Lovász applications by allowing the color count to grow and extracting the 1/e factor via the BCT recurrence. The explicit error term, the identification of BHP as the sole analytic input, and the clean combination of three standard tools are strengths. The lower bound is asymptotically stronger than the Ω(1/log k) that follows from LLL alone.

major comments (2)

[§4] §4 (restricted BCT recurrence): The central quantitative claim requires the restricted Blankenship-Cummings-Taranchuk recurrence to hold for the k-AP hypergraph when the number of colors r = ⌊k/log k⌋ grows with k. The manuscript should explicitly verify that every step in the recurrence derivation remains valid in this regime (in particular, that no step assumes r bounded or o(k^α) for α smaller than the implicit exponent arising from k/log k). Without this verification the bootstrap from smaller instances fails to produce the claimed 1/e factor and the Ω(k/log k) growth; the LLL step alone only yields Ω(1/log k).
[§3] §3 (symmetric LLL application and inductive bootstrap): After obtaining N ≳ r^{k−1}/poly(k) from LLL with r ∼ k/log k, the paper combines this with the BCT recurrence to accumulate the 1/e constant. The precise inductive step relating H(k) to H(k−1) (or to W(k−1,k)) and the error propagation that produces ε(k) = O(k^{-0.475} log k) should be written out explicitly, including how the BHP gap exponent enters the final error term.

minor comments (2)

[Abstract] The abstract refers to 'Erdős-Lovász' but the tool used is the symmetric Lovász Local Lemma; a brief clarification in the introduction would avoid confusion.
[§2] Notation for the restricted BCT recurrence should be defined once at first use rather than re-introduced in each application.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the positive evaluation of its significance in providing the first quantitative resolution of the positive direction of Erdős-Graham Problem #190. We address each major comment below and will revise the manuscript to incorporate the requested clarifications and expansions.

read point-by-point responses

Referee: [§4] §4 (restricted BCT recurrence): The central quantitative claim requires the restricted Blankenship-Cummings-Taranchuk recurrence to hold for the k-AP hypergraph when the number of colors r = ⌊k/log k⌋ grows with k. The manuscript should explicitly verify that every step in the recurrence derivation remains valid in this regime (in particular, that no step assumes r bounded or o(k^α) for α smaller than the implicit exponent arising from k/log k). Without this verification the bootstrap from smaller instances fails to produce the claimed 1/e factor and the Ω(k/log k) growth; the LLL step alone only yields Ω(1/log k).

Authors: We agree that the applicability of the restricted BCT recurrence must be verified explicitly when r = ⌊k/log k⌋ grows with k. The original manuscript invoked the recurrence as established in the literature without re-checking the parameter regime. The derivation of the BCT recurrence relies on bounds that hold whenever r = o(k^δ) for a positive δ determined by the uniformity of the hypergraph; since ⌊k/log k⌋ satisfies this for any δ > 0 and all sufficiently large k, the steps remain valid and the bootstrap indeed produces the 1/e factor. We will add a dedicated paragraph (or short subsection) in §4 that re-derives the key inequalities of the recurrence under the growing-r hypothesis and confirms that no step requires r to be bounded or o(k^α) for α smaller than the implicit exponent. This addition will also make clear why the pure LLL bound yields only the weaker Ω(1/log k) growth. revision: yes
Referee: [§3] §3 (symmetric LLL application and inductive bootstrap): After obtaining N ≳ r^{k−1}/poly(k) from LLL with r ∼ k/log k, the paper combines this with the BCT recurrence to accumulate the 1/e constant. The precise inductive step relating H(k) to H(k−1) (or to W(k−1,k)) and the error propagation that produces ε(k) = O(k^{-0.475} log k) should be written out explicitly, including how the BHP gap exponent enters the final error term.

Authors: We acknowledge that the inductive bootstrap and error analysis in §3 were presented concisely. We will expand this section to write out the precise relation obtained from the pigeonhole reduction H(k) ≥ W(k−1,k) and its interface with the BCT recurrence applied inductively across levels. The expansion will include the explicit recurrence inequality, the accumulation of the product that produces the 1/e constant after taking k-th roots, and a self-contained calculation of the error term. The Baker-Harman-Pintz theorem supplies gaps of size O(x^{0.525}); this exponent propagates through the density-increment steps and the O(log k) iterations of the recurrence, together with the poly(k) factors from the LLL, to yield the stated O(k^{-0.475} log k) bound on ε(k). We will insert this calculation as a new lemma or proposition in §3. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation uses only external theorems and direct reductions

full rationale

The paper's central lower bound is obtained by applying the symmetric Lovász Local Lemma to the k-AP hypergraph (with r = ⌊k/log k⌋ colors), invoking the restricted Blankenship-Cummings-Taranchuk recurrence (an external result from different authors), using the Baker-Harman-Pintz prime-gap theorem as the sole analytic input, and applying the pigeonhole reduction H(k) ≥ W(k-1,k). None of these steps define a quantity in terms of the claimed bound, fit parameters to the target asymptotic, or rely on self-citations whose validity depends on the present work. The growth of r with k is an explicit extension of the cited recurrence rather than a self-referential construction. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claim rests on three standard results from combinatorics and analytic number theory plus the basic pigeonhole reduction H(k) ≥ W(k-1,k). No free parameters are fitted and no new entities are postulated; the asymptotic bound emerges from the combination of these external inputs.

axioms (3)

standard math Symmetric Lovász Local Lemma
Applied to the k-term AP hypergraph on [N] to bound the probability of bad monochromatic or rainbow events.
domain assumption Restricted form of the Blankenship-Cummings-Taranchuk recurrence
Used to relate H(k) to smaller instances when the number of colors grows with k.
standard math Baker-Harman-Pintz theorem on prime gaps
Provides primes in short intervals to select suitable N for the probabilistic construction.

pith-pipeline@v0.9.0 · 5649 in / 1669 out tokens · 67885 ms · 2026-05-10T00:18:14.310915+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Three-color van der Waerden numbers grow super-exponentially
math.CO 2026-06 unverdicted novelty 8.0

w(k;3) > 2^{k (log^* k)/4} for large k, so the three-color van der Waerden number grows super-exponentially.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages · cited by 1 Pith paper

[1]

Alon and J

N. Alon and J. H. Spencer,The Probabilistic Method, 4th edition, Wiley, 2016. Chapter 5 (Lovász Local Lemma, symmetric form)

work page 2016
[2]

R. C. Baker, G. Harman, and J. Pintz,The difference between consecutive primes, II, Proc. London Math. Soc. (3)83(2001), 532–562. doi:10.1112/plms/83.3.532

work page doi:10.1112/plms/83.3.532 2001
[3]

E. R. Berlekamp,A construction for partitions which avoid long arithmetic progressions, Canad. Math. Bull. 11(1968), no. 3, 409–414. doi:10.4153/CMB-1968-047-7

work page doi:10.4153/cmb-1968-047-7 1968
[4]

Blankenship, J

M. Blankenship, J. Cummings, and V. Taranchuk,A new lower bound for van der Waerden numbers, European J. Combin.69(2018), 163–168. doi:10.1016/j.ejc.2017.10.007; arXiv:1705.09673

work page doi:10.1016/j.ejc.2017.10.007 2018
[5]

T. F. Bloom,Erdős Problem #190, Erdős Problems database,https://www.erdosproblems.com/190, ac- cessed 2026-04-22

work page 2026
[6]

Butler, C

S. Butler, C. Erickson, L. Hogben, K. Hogenson, L. Kramer, R. Kramer, J. C.-H. Lin, R. Martin, D. Stolee, N. Warnberg, and M. Young,Rainbow arithmetic progressions, J. Combin.7(2016), 595–626

work page 2016
[7]

28 de L’Enseignement Mathématique, Université de Genève, 1980

P.ErdősandR.L.Graham,Old and New Problems and Results in Combinatorial Number Theory, Monographie No. 28 de L’Enseignement Mathématique, Université de Genève, 1980

work page 1980
[8]

Erdős and L

P. Erdős and L. Lovász,Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets(Colloq., Keszthely, 1973), Vol. II, 609–627, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975

work page 1973
[9]

Hunter,Lower bounds for multicolor van der Waerden numbers, Israel J

Z. Hunter,Lower bounds for multicolor van der Waerden numbers, Israel J. Math.267(2025), 783–795. doi:10.1007/s11856-025-2735-0; arXiv:2301.06212

work page doi:10.1007/s11856-025-2735-0 2025
[10]

Jungić, J

V. Jungić, J. Licht (Fox), M. Mahdian, J. Nešetřil, and R. Radoičić,Rainbow arithmetic progressions and anti-Ramsey results, Combin. Probab. Comput.12(2003), no. 5–6, 599–620. doi:10.1017/S096354830300587X. JRTI Email address:jihobae@snu.ac.kr

work page doi:10.1017/s096354830300587x 2003

[1] [1]

Alon and J

N. Alon and J. H. Spencer,The Probabilistic Method, 4th edition, Wiley, 2016. Chapter 5 (Lovász Local Lemma, symmetric form)

work page 2016

[2] [2]

R. C. Baker, G. Harman, and J. Pintz,The difference between consecutive primes, II, Proc. London Math. Soc. (3)83(2001), 532–562. doi:10.1112/plms/83.3.532

work page doi:10.1112/plms/83.3.532 2001

[3] [3]

E. R. Berlekamp,A construction for partitions which avoid long arithmetic progressions, Canad. Math. Bull. 11(1968), no. 3, 409–414. doi:10.4153/CMB-1968-047-7

work page doi:10.4153/cmb-1968-047-7 1968

[4] [4]

Blankenship, J

M. Blankenship, J. Cummings, and V. Taranchuk,A new lower bound for van der Waerden numbers, European J. Combin.69(2018), 163–168. doi:10.1016/j.ejc.2017.10.007; arXiv:1705.09673

work page doi:10.1016/j.ejc.2017.10.007 2018

[5] [5]

T. F. Bloom,Erdős Problem #190, Erdős Problems database,https://www.erdosproblems.com/190, ac- cessed 2026-04-22

work page 2026

[6] [6]

Butler, C

S. Butler, C. Erickson, L. Hogben, K. Hogenson, L. Kramer, R. Kramer, J. C.-H. Lin, R. Martin, D. Stolee, N. Warnberg, and M. Young,Rainbow arithmetic progressions, J. Combin.7(2016), 595–626

work page 2016

[7] [7]

28 de L’Enseignement Mathématique, Université de Genève, 1980

P.ErdősandR.L.Graham,Old and New Problems and Results in Combinatorial Number Theory, Monographie No. 28 de L’Enseignement Mathématique, Université de Genève, 1980

work page 1980

[8] [8]

Erdős and L

P. Erdős and L. Lovász,Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets(Colloq., Keszthely, 1973), Vol. II, 609–627, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975

work page 1973

[9] [9]

Hunter,Lower bounds for multicolor van der Waerden numbers, Israel J

Z. Hunter,Lower bounds for multicolor van der Waerden numbers, Israel J. Math.267(2025), 783–795. doi:10.1007/s11856-025-2735-0; arXiv:2301.06212

work page doi:10.1007/s11856-025-2735-0 2025

[10] [10]

Jungić, J

V. Jungić, J. Licht (Fox), M. Mahdian, J. Nešetřil, and R. Radoičić,Rainbow arithmetic progressions and anti-Ramsey results, Combin. Probab. Comput.12(2003), no. 5–6, 599–620. doi:10.1017/S096354830300587X. JRTI Email address:jihobae@snu.ac.kr

work page doi:10.1017/s096354830300587x 2003