/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 190

References:

    erdosproblems.com/190

    [ErGr79] P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory: van der Waerden's theorem and related topics, Enseign. Math. (2) 25 (1979), 325–344 (p. 333).

    [ErGr80] P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monogr. Enseign. Math. 28 (1980), p. 17.

    [Ba26] J. H. Bae, A resolution of Erdős Problem #190 via Erdős–Lovász, BCT, and Baker–Harman–Pintz, arXiv:2604.20588 (22 April 2026).

    [FoHu26] J. Fox and Z. Hunter, Three-color van der Waerden numbers grow super-exponentially, arXiv:2606.02541 (1 June 2026).

@[expose] public sectionopen Filternamespace Erdos190

N is canonical for k if every colouring of ${1, \ldots, N}$ contains a k-term arithmetic progression which is either monochromatic or rainbow (its terms receive pairwise distinct colours). Colours are taken in ℕ; since only the finitely many values on ${1, \ldots, N}$ matter, this covers colourings into any number of colours.

def IsCanonical (N k : ℕ) : Prop := ∀ c : ℕ → ℕ, ∃ S ⊆ Set.Icc 1 N, S.IsAPOfLength k ∧ ((∃ γ, ∀ n ∈ S, c n = γ) ∨ S.InjOn c)

The canonical van der Waerden number $H(k)$: the least N which is canonical for k (0 if there is none).

noncomputable def H (k : ℕ) : ℕ := sInf {N | IsCanonical N k}

Any two distinct points form a $2$-term progression which is monochromatic or rainbow, so ${1, 2}$ is canonical for $k = 2$.

@[category test, AMS 5 11] theorem isCanonical_two_two : IsCanonical 2 2 := ⊢ IsCanonical 2 2 c:ℕ → ℕ⊢ ∃ S ⊆ Set.Icc 1 2, S.IsAPOfLength ↑2 ∧ ((∃ γ, ∀ n ∈ S, c n = γ) ∨ Set.InjOn c S) refine ⟨{1, 2}, ?_, c:ℕ → ℕ⊢ {1, 2}.IsAPOfLength ↑2 exact_mod_cast Nat.isAPOfLength_pair (c:ℕ → ℕ⊢ 1 < 2 All goals completed! 🐙 : 1 < 2), ?_⟩ c:ℕ → ℕ⊢ {1, 2} ⊆ Set.Icc 1 2 c:ℕ → ℕ⊢ 1 ∈ Set.Icc 1 2c:ℕ → ℕ⊢ 2 ∈ Set.Icc 1 2 c:ℕ → ℕ⊢ 1 ∈ Set.Icc 1 2c:ℕ → ℕ⊢ 2 ∈ Set.Icc 1 2 All goals completed! 🐙 c:ℕ → ℕ⊢ (∃ γ, ∀ n ∈ {1, 2}, c n = γ) ∨ Set.InjOn c {1, 2} c:ℕ → ℕh:c 1 = c 2⊢ (∃ γ, ∀ n ∈ {1, 2}, c n = γ) ∨ Set.InjOn c {1, 2}c:ℕ → ℕh:¬c 1 = c 2⊢ (∃ γ, ∀ n ∈ {1, 2}, c n = γ) ∨ Set.InjOn c {1, 2} c:ℕ → ℕh:c 1 = c 2⊢ (∃ γ, ∀ n ∈ {1, 2}, c n = γ) ∨ Set.InjOn c {1, 2} exact Or.inl ⟨c 1, c:ℕ → ℕh:c 1 = c 2⊢ ∀ n ∈ {1, 2}, c n = c 1 c:ℕ → ℕh:c 1 = c 2⊢ c 1 = c 1c:ℕ → ℕh:c 1 = c 2⊢ c 2 = c 1 c:ℕ → ℕh:c 1 = c 2⊢ c 1 = c 1c:ℕ → ℕh:c 1 = c 2⊢ c 2 = c 1 All goals completed! 🐙⟩ c:ℕ → ℕh:¬c 1 = c 2⊢ (∃ γ, ∀ n ∈ {1, 2}, c n = γ) ∨ Set.InjOn c {1, 2} c:ℕ → ℕh:¬c 1 = c 2⊢ Set.InjOn c {1, 2} c:ℕ → ℕh:¬c 1 = c 2hxy:c 1 = c 1⊢ 1 = 1c:ℕ → ℕh:¬c 1 = c 2hxy:c 1 = c 2⊢ 1 = 2c:ℕ → ℕh:¬c 1 = c 2hxy:c 2 = c 1⊢ 2 = 1c:ℕ → ℕh:¬c 1 = c 2hxy:c 2 = c 2⊢ 2 = 2 c:ℕ → ℕh:¬c 1 = c 2hxy:c 1 = c 1⊢ 1 = 1c:ℕ → ℕh:¬c 1 = c 2hxy:c 1 = c 2⊢ 1 = 2c:ℕ → ℕh:¬c 1 = c 2hxy:c 2 = c 1⊢ 2 = 1c:ℕ → ℕh:¬c 1 = c 2hxy:c 2 = c 2⊢ 2 = 2 All goals completed! 🐙

${1}$ contains no $2$-term arithmetic progression, so it is not canonical for $k = 2$.

h:IsCanonical 1 2S:Set ℕhS:S ⊆ Set.Icc 1 1a:ℕd:ℕhcard:ENat.card ↑S = ↑2h1:2 ≤ 1h2:S.encard = 2⊢ False exact absurd h1 (h:IsCanonical 1 2S:Set ℕhS:S ⊆ Set.Icc 1 1a:ℕd:ℕhcard:ENat.card ↑S = ↑2h1:2 ≤ 1h2:S.encard = 2⊢ ¬2 ≤ 1 All goals completed! 🐙)

$H(2) = 2$.

N:ℕhN:0 ∈ {N | IsCanonical N 2}hlt:¬2 ≤ 0S:Set ℕhS:S ⊆ Set.Icc 1 0a:ℕd:ℕhcard:ENat.card ↑S = ↑2this:S = ∅⊢ False N:ℕhN:0 ∈ {N | IsCanonical N 2}hlt:¬2 ≤ 0a:ℕd:ℕhS:∅ ⊆ Set.Icc 1 0hcard:ENat.card ↑∅ = ↑2⊢ False All goals completed! 🐙 N:ℕhN:1 ∈ {N | IsCanonical N 2}hlt:¬2 ≤ 1⊢ False All goals completed! 🐙

Let $H(k)$ be the smallest $N$ such that in any finite colouring of ${1,\ldots,N}$ (into any number of colours) there is always either a monochromatic $k$-term arithmetic progression or a rainbow arithmetic progression (i.e. all elements are different colours). Estimate $H(k)$. Is it true that $H(k)^{1/k}/k\to\infty$ as $k\to\infty$?

The question was answered affirmatively in [Ba26] (22 April 2026), which gave the first publicly available proof, with $H(k)\geq k^{(2-o(1))k}$. The subsequent work [FoHu26] (1 June 2026) describes [Ba26] as independent work that also resolves the problem, and obtains $H(k)\geq k^{(1-o(1))k\log k}$.

The statement is formalised without assuming the existence of $H(k)$: for every $C$, every canonical $N$ exceeds $(Ck)^k$ for all large $k$. Given the existence of $H(k)$ this is equivalent to $H(k)^{1/k}/k\to\infty$ (see erdos_190.variants.H).

The formal proof (Lean 4 / Mathlib v4.33.0, following [Ba26]) is registered in the Palomar registry as PALOMAR-2026-09-15-000003. A bridge deriving this exact statement (with the definitions above) from the registered proof is available at jbaelaw/erdos190-fc-bridge.

@[category research solved, question, AMS 5 11, formal_proof using lean4 at "https://palomar-registry.org/entry.html?id=PALOMAR-2026-09-15-000003"] theorem erdos_190 : ∀ C : ℕ, ∀ᶠ k in atTop, ∀ N, IsCanonical N k → (C * k) ^ k < N := ⊢ ∀ (C : ℕ), ∀ᶠ (k : ℕ) in atTop, ∀ (N : ℕ), IsCanonical N k → (C * k) ^ k < N All goals completed! 🐙

The same statement in terms of $H(k)$, assuming that a canonical N exists for every k (the Erdős–Graham theorem, via Szemerédi's theorem).

@[category research solved, question, AMS 5 11, formal_proof using lean4 at "https://palomar-registry.org/entry.html?id=PALOMAR-2026-09-15-000003"] theorem erdos_190.variants.H : (∀ k, {N | IsCanonical N k}.Nonempty) → ∀ C : ℕ, ∀ᶠ k in atTop, (C * k) ^ k < H k := ⊢ (∀ (k : ℕ), {N | IsCanonical N k}.Nonempty) → ∀ (C : ℕ), ∀ᶠ (k : ℕ) in atTop, (C * k) ^ k < Erdos190.H k All goals completed! 🐙end Erdos190