# mathlibdocumentation

combinatorics.hales_jewett

# The Hales-Jewett theorem #

We prove the Hales-Jewett theorem and deduce Van der Waerden's theorem as a corollary.

The Hales-Jewett theorem is a result in Ramsey theory dealing with combinatorial lines. Given an 'alphabet' α : Type* and a b : α, an example of a combinatorial line in α^5 is { (a, x, x, b, x) | x : α }. See combinatorics.line for a precise general definition. The Hales-Jewett theorem states that for any fixed finite types α and κ, there exists a (potentially huge) finite type ι such that whenever ι → α is κ-colored (i.e. for any coloring C : (ι → α) → κ), there exists a monochromatic line. We prove the Hales-Jewett theorem using the idea of color focusing and a product argument. See the proof of combinatorics.line.exists_mono_in_high_dimension' for details.

The version of Van der Waerden's theorem in this file states that whenever a commutative monoid M is finitely colored and S is a finite subset, there exists a monochromatic homothetic copy of S. This follows from the Hales-Jewett theorem by considering the map (ι → S) → M sending v to ∑ i : ι, v i, which sends a combinatorial line to a homothetic copy of S.

## Main results #

• combinatorics.line.exists_mono_in_high_dimension: the Hales-Jewett theorem.
• combinatorics.exists_mono_homothetic_copy: a generalization of Van der Waerden's theorem.

## Implementation details #

For convenience, we work directly with finite types instead of natural numbers. That is, we write α, ι, κ for (finite) types where one might traditionally use natural numbers n, H, c. This allows us to work directly with α, option α, (ι → α) → κ, and ι ⊕ ι' instead of fin n, fin (n+1), fin (c^(n^H)), and fin (H + H').

## Todo #

• Prove a finitary version of Van der Waerden's theorem (either by compactness or by modifying the current proof).

• One could reformulate the proof of Hales-Jewett to give explicit upper bounds on the number of coordinates needed.

## Tags #

combinatorial line, Ramsey theory, arithmetic progession

### References #

structure combinatorics.line (α : Type u_1) (ι : Type u_2) :
Type (max u_1 u_2)
• idx_fun : ι →
• proper : ∃ (i : ι), self.idx_fun i = none

The type of combinatorial lines. A line l : line α ι in the hypercube ι → α defines a function α → ι → α from α to the hypercube, such that for each coordinate i : ι, the function λ x, l x i is either id or constant. We require lines to be nontrivial in the sense that λ x, l x i is id for at least one i.

Formally, a line is represented by the function l.idx_fun : ι → option α which says whether λ x, l x i is id (corresponding to l.idx_fun i = none) or constantly y (corresponding to l.idx_fun i = some y).

When α has size 1 there can be many elements of line α ι defining the same function.

@[instance]
def combinatorics.line.has_coe_to_fun (α : Type u_1) (ι : Type u_2) :
Equations
def combinatorics.line.is_mono {α : Type u_1} {ι : Type u_2} {κ : Sort u_3} (C : (ι → α) → κ) (l : ι) :
Prop

A line is monochromatic if all its points are the same color.

Equations
• = ∃ (c : κ), ∀ (x : α), C (l x) = c
def combinatorics.line.diagonal (α : Type u_1) (ι : Type u_2) [nonempty ι] :

The diagonal line. It is the identity at every coordinate.

Equations
@[instance]
def combinatorics.line.inhabited (α : Type u_1) (ι : Type u_2) [nonempty ι] :
Equations
structure combinatorics.line.almost_mono {α : Type u_1} {ι : Type u_2} {κ : Type u_3} (C : (ι → option α) → κ) :
Type (max u_1 u_2 u_3)
• line : ι
• color : κ
• has_color : ∀ (x : α), C ((self.line) (some x)) = self.color

The type of lines that are only one color except possibly at their endpoints.

@[instance]
def combinatorics.line.almost_mono.inhabited {α : Type u_1} {ι : Type u_2} {κ : Type u_3} [nonempty ι] [inhabited κ] :
Equations
structure combinatorics.line.color_focused {α : Type u_1} {ι : Type u_2} {κ : Type u_3} (C : (ι → option α) → κ) :
Type (max u_1 u_2 u_3)

The type of collections of lines such that

• each line is only one color except possibly at its endpoint
• the lines all have the same endpoint
• the colors of the lines are distinct. Used in the proof exists_mono_in_high_dimension.
@[instance]
def combinatorics.line.color_focused.inhabited {α : Type u_1} {ι : Type u_2} {κ : Type u_3} (C : (ι → option α) → κ) :
Equations
def combinatorics.line.map {α : Type u_1} {α' : Type u_2} {ι : Type u_3} (f : α → α') (l : ι) :

A function f : α → α' determines a function line α ι → line α' ι. For a coordinate i, l.map f is the identity at i if l is, and constantly f y if l is constantly y at i.

Equations
def combinatorics.line.vertical {α : Type u_1} {ι : Type u_2} {ι' : Type u_3} (v : ι → α) (l : ι') :
ι')

A point in ι → α and a line in ι' → α determine a line in ι ⊕ ι' → α.

Equations
def combinatorics.line.horizontal {α : Type u_1} {ι : Type u_2} {ι' : Type u_3} (l : ι) (v : ι' → α) :
ι')

A line in ι → α and a point in ι' → α determine a line in ι ⊕ ι' → α.

Equations
def combinatorics.line.prod {α : Type u_1} {ι : Type u_2} {ι' : Type u_3} (l : ι) (l' : ι') :
ι')

One line in ι → α and one in ι' → α together determine a line in ι ⊕ ι' → α.

Equations
theorem combinatorics.line.apply {α : Type u_1} {ι : Type u_2} (l : ι) (x : α) :
l x = λ (i : ι), (l.idx_fun i).get_or_else x
theorem combinatorics.line.apply_none {α : Type u_1} {ι : Type u_2} (l : ι) (x : α) (i : ι) (h : l.idx_fun i = none) :
l x i = x
theorem combinatorics.line.apply_of_ne_none {α : Type u_1} {ι : Type u_2} (l : ι) (x : α) (i : ι) (h : l.idx_fun i none) :
some (l x i) = l.idx_fun i
@[simp]
theorem combinatorics.line.map_apply {α : Type u_1} {α' : Type u_2} {ι : Type u_3} (f : α → α') (l : ι) (x : α) :
(f x) = f l x
@[simp]
theorem combinatorics.line.vertical_apply {α : Type u_1} {ι : Type u_2} {ι' : Type u_3} (v : ι → α) (l : ι') (x : α) :
x = (l x)
@[simp]
theorem combinatorics.line.horizontal_apply {α : Type u_1} {ι : Type u_2} {ι' : Type u_3} (l : ι) (v : ι' → α) (x : α) :
(l.horizontal v) x = sum.elim (l x) v
@[simp]
theorem combinatorics.line.prod_apply {α : Type u_1} {ι : Type u_2} {ι' : Type u_3} (l : ι) (l' : ι') (x : α) :
(l.prod l') x = sum.elim (l x) (l' x)
@[simp]
theorem combinatorics.line.diagonal_apply {α : Type u_1} {ι : Type u_2} [nonempty ι] (x : α) :
x = λ (i : ι), x
theorem combinatorics.line.exists_mono_in_high_dimension (α : Type u) [fintype α] (κ : Type v) [fintype κ] :
∃ (ι : Type) [_inst_3 : fintype ι], ∀ (C : (ι → α) → κ), ∃ (l : ,

The Hales-Jewett theorem: for any finite types α and κ, there exists a finite type ι such that whenever the hypercube ι → α is κ-colored, there is a monochromatic combinatorial line.

theorem combinatorics.exists_mono_homothetic_copy {M : Type u_1} {κ : Type u_2} (S : finset M) [fintype κ] (C : M → κ) :
∃ (a : ) (H : a > 0) (b : M) (c : κ), ∀ (s : M), s SC (a s + b) = c

A generalization of Van der Waerden's theorem: if M is a finitely colored commutative monoid, and S is a finite subset, then there exists a monochromatic homothetic copy of S.