Erdős Problem #190

Erdős Problem #190

1. FORMAL RESTATEMENT

Let $H(k)$ be the least $N$ such that every colouring of $[N]$ with any number of colours contains a monochromatic or rainbow $k$-term arithmetic progression. Both alternatives have length $k$, and common differences are positive. Estimate $H(k)$; in particular, does $H(k)^{1/k}/k\to\infty$?

2. CURRENT STATUS AND ATTEMPT SCOPE

The question is now settled affirmatively. Fox and Hunter's Theorem 3 gives $H(k)\ge k^{(1-o(1))k\log k}$; their Theorem 2 supplies the stronger multicolour van der Waerden input. Bae independently obtained $k^{(2-o(1))k}$. The old local attempt's open-status discussion is therefore superseded. We prove an exponential-scale lower bound, the canonical existence reduction, and explain exactly where our independent reconstruction falls short of the new lower bound.

3. LOWER BOUND BY LOCAL AVOIDANCE

Use $r=k-1$ colours independently and uniformly on $[N]$. A fixed $k$-term progression is monochromatic with probability $p=r^{1-k}$. It cannot be rainbow, since fewer than $k$ colours are available.

A vertex belongs to at most $k\lfloor(N-1)/(k-1)\rfloor\le2N$ progressions: choose its position and the common difference. A bad monochromatic-progression event is independent of all events on disjoint vertex sets, so it has at most $2kN$ neighbours in a dependency graph. The symmetric Lovász local lemma states that if $ep(D+1)\le1$, events of probability at most $p$ with dependency degree at most $D$ can all be avoided.

For $k\ge4$ take \[ N=\left\lfloor\frac{(k-1)^{k-1}}{8ek}\right\rfloor. \] Whenever $N\ge1$, the local-lemma condition holds, since $ep(2kN+1)\le1/4+e(k-1)^{1-k}<1$. For $N=0$ the lower bound is trivial. Hence \[ H(k)>\left\lfloor\frac{(k-1)^{k-1}}{8ek}\right\rfloor, \qquad \liminf_{k\to\infty}\frac{H(k)^{1/k}}k\ge1. \tag{1} \] The local lemma is a declared standard external input here, not an independence assertion for overlapping progressions.

4. WHY AN ARBITRARY NUMBER OF COLOURS STILL GIVES FINITE $H(k)$

Fix $k\ge3$ and $\delta=1/(4k^3)$. By the finite density form of Szemerédi's theorem, a colour class of size at least $\delta N$ contains a $k$-term progression once $N$ is sufficiently large. Otherwise every colour class has fewer than $\delta N$ points, and the number of equal-colour unordered pairs is at most $\delta N^2/2$.

A pair of positions in a $k$-term progression, together with two distinct specified integers, determines at most one progression. Therefore the number of progressions that have any repeated colour is at most \[ \binom{k}{2}\frac{\delta N^2}{2}<\frac{N^2}{16k}. \] For $N\ge4(k-1)$, the progressions with $1\le d\le\lfloor N/(2(k-1))\rfloor$ and $1\le a\le N-(k-1)d$ number at least \[ \frac{N^2}{8(k-1)}. \] Since the latter bound is larger, at least one of them is rainbow. This proves finiteness of $H(k)$ using the explicitly stated density theorem, uniformly over the number of colours.

5. COMPARISON WITH THE KNOWN RESOLUTION

If $w(k;r)$ denotes the usual multicolour van der Waerden number, then $H(k)\ge w(k;k-1)$: a counterexample using $k-1$ colours has no rainbow $k$-progression. Fox--Hunter prove that for every fixed $\epsilon>0$ and all sufficiently large $k$, whenever $r\ge(\log k)^{3/\epsilon}$, \[ w(k;r)\ge r^{(1-\epsilon)k\log k}. \] Putting $r=k-1$ makes the threshold condition valid and yields their recorded affirmative resolution. This theorem is substantially stronger than $1$; its random shifted product construction is not reproved in this attempt. Merely citing it does not turn our local-lemma calculation into a new proof of that construction.

6. FINAL

UNRESOLVED in this independent reconstruction; known affirmative resolution recorded. The proved work upgrades the previous elementary quadratic lower bound to nearly $k^k$, and supplies a complete reduction for existence using Szemerédi's theorem. The missing growth factor in $H(k)^{1/k}/k$ is precisely the part not established by these arguments. The completion estimate describes this proof attempt rather than the database status.

7. SOURCES

https://www.erdosproblems.com/190; J. Fox and Z. Hunter, Three-color van der Waerden numbers grow super-exponentially, https://arxiv.org/abs/2606.02541, Theorems 2--3 and Section 1.1; J. H. Bae, https://arxiv.org/abs/2604.20588. The former primary source also records the classical local-lemma lower bound and the canonical existence argument's dependence on Szemerédi's theorem.

COMPLETION ESTIMATE

COMPLETION: 40%

Erdős problem 190

1) FORMAL RESTATEMENT

Let $H(k)$ be the smallest $N$ such that for every colouring $\chi:\{1,\dots,N\}\to\mathcal{C}$ into any set of colours, there exists a $k$-term arithmetic progression $a,a+d,\dots,a+(k-1)d$ with either: (i) all $k$ points the same colour (monochromatic), or (ii) all $k$ points distinct colours (rainbow). Estimate $H(k)$ and ask whether $H(k)^{1/k}/k\to\infty$.

2) QUICK LITERATURE/CONTEXT CHECK

Problem text says: existence of $H(k)$ follows from Szemerédi’s theorem and $H(k)^{1/k}\to\infty$ is easy. No further claims are used here.

3) ATTACK PLAN

Give: $1$ an explicit general lower bound construction, $2$ exact computation for $k=3$ by exhaustive search (computer-assisted).

4) WORK

Lemma 4.1 (Explicit lower bound $H(k)\ge (k-1)^2+1$).

For every $k\ge 3$, there exists a colouring of $\{1,\dots,(k-1)^2\}$ with no monochromatic $k$-AP and no rainbow $k$-AP. Hence $H(k)\ge (k-1)^2+1$. Proof. Colour $n$ by its residue class modulo $(k-1)$, using exactly $(k-1)$ colours. Then no rainbow $k$-AP exists because there are only $k-1$ colours total. If a $k$-term AP is monochromatic under this colouring, all its terms are congruent mod $(k-1)$, so its common difference $d$ is a multiple of $(k-1)$. Then the span from first to last term is $(k-1)d\ge (k-1)^2$. But within $\{1,\dots,(k-1)^2\}$, any $k$-AP would require $a+(k-1)d\le (k-1)^2$; if $d\ge (k-1)$ this forces $a\le 0$, impossible. Thus no monochromatic $k$-AP exists either. $\square$

Lemma 4.2 ($H(3)=9$, computer-assisted).

$H(3)=9$. Proof (with exhaustive computation). A colouring of $\{1,\dots,8\}$ avoiding both monochromatic and rainbow 3-APs is: \[ \chi(1..8)=(0,0,1,0,1,1,2,1). \] Thus $H(3)\ge 9$.

For $N=9$, I performed exhaustive backtracking over canonical colourings (restricted-growth strings: new colours may appear only as the next unused label), checking each colouring against all 3-term APs in $\{1,\dots,9\}$. No colouring avoids both a monochromatic 3-AP and a rainbow 3-AP. Therefore every colouring of $\{1,\dots,9\}$ has one of the two patterns, so $H(3)\le 9$. Hence $H(3)=9$. $\square$

FAST REALITY CHECK (computed)

Exhaustive search results: For $N=8$ an avoiding colouring exists (given above). For $N=9$ no avoiding colouring exists (backtracking over canonical colourings).

6) FINAL

UNRESOLVED

(i) Strongest proved partial results: explicit lower bound $H(k)\ge (k-1)^2+1$ (Lemma 4.1) and exact value $H(3)=9$ (Lemma 4.2).

(ii) First gap: asymptotic growth of $H(k)$; in particular whether $H(k)^{1/k}/k\to\infty$.

(iii) Top 3 next moves: 1. Derive nontrivial upper bounds via a canonical-structure theorem for AP-colourings (analogue of canonical Ramsey). 2. Search for improved lower-bound constructions beyond $(k-1)^2$ using structured colourings. 3. Compute $H(4)$ on computers (SAT/backtracking) to identify growth behaviour.

(iv) Minimal counterexample structure (to fast growth): a family of colourings on $[N]$ with many colours but with strong restrictions ensuring every $k$-AP repeats a colour while also preventing $k$ identical colours along an AP.