Van der Waerden's theorem (Gallai's multidimensional form)
ProvedFamousTheorems.van_der_waerdenVan der Waerden's theorem (Gallai's multidimensional form). Let be a commutative monoid, finite, and colour with finitely many colours. Then some homothetic copy with , , is monochromatic.
Taking and gives van der Waerden's theorem: every finite colouring of contains monochromatic arithmetic progressions of every length. Taking gives the Gallai–Witt theorem on monochromatic homothetic copies of any finite configuration.
Formalization note. Mathlib's Combinatorics.exists_mono_homothetic_copy, derived from the Hales–Jewett theorem; a • s is the natural-number scalar action.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem van_der_waerden {M κ : Type*} [AddCommMonoid M] (S : Finset M) [Finite κ] (C : M → κ) :
∃ a > 0, ∃ (b : M) (c : κ), ∀ s ∈ S, C (a • s + b) = c := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Combinatorics.exists_mono_homothetic_copy`. Proof here reduces to that Mathlib result.