combinatorics.hales_jewett | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

1126441d

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

23aa88e3

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -381,11 +381,11 @@ theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finse
   · rw [← Finset.sum_const]
     apply Finset.sum_congr rfl
     intro i hi
-    rw [hs, Finset.sep_def, Finset.mem_filter] at hi 
+    rw [hs, Finset.sep_def, Finset.mem_filter] at hi
     rw [l.apply_none _ _ hi.right, Subtype.coe_mk]
   · apply Finset.sum_congr rfl
     intro i hi
-    rw [hs, Finset.sep_def, Finset.compl_filter, Finset.mem_filter] at hi 
+    rw [hs, Finset.sep_def, Finset.compl_filter, Finset.mem_filter] at hi
     obtain ⟨y, hy⟩ := option.ne_none_iff_exists.mp hi.right
     simp_rw [line.apply, ← hy, Option.map_some', Option.getD_some]
 #align combinatorics.exists_mono_homothetic_copy Combinatorics.exists_mono_homothetic_copy

23aa88e3

bump to nightly-2024-02-09-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

3ad77742

Diff

@@ -312,6 +312,7 @@ private theorem exists_mono_in_high_dimension' :
       -- By choice of `ι`, `C'` either has `r` color-focused lines or a monochromatic line.
       specialize hι C'
       rcases hι with (⟨s, sr⟩ | _)
+      -- By above, we are done if `C'` has a monochromatic line.
       on_goal 2 => exact Or.inr (mono_of_mono hι)
       -- Here we assume `C'` has `r` color focused lines. We split into cases depending on whether one of
       -- these `r` lines has the same color as the focus point.

23aa88e3

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,10 +3,10 @@ Copyright (c) 2021 David Wärn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
 -/
-import Mathbin.Data.Fintype.Option
-import Mathbin.Data.Fintype.Pi
-import Mathbin.Data.Fintype.Sum
-import Mathbin.Algebra.BigOperators.Basic
+import Data.Fintype.Option
+import Data.Fintype.Pi
+import Data.Fintype.Sum
+import Algebra.BigOperators.Basic
 
 #align_import combinatorics.hales_jewett from "leanprover-community/mathlib"@"23aa88e32dcc9d2a24cca7bc23268567ed4cd7d6"

23aa88e3

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2021 David Wärn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
-
-! This file was ported from Lean 3 source module combinatorics.hales_jewett
-! leanprover-community/mathlib commit 23aa88e32dcc9d2a24cca7bc23268567ed4cd7d6
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Fintype.Option
 import Mathbin.Data.Fintype.Pi
 import Mathbin.Data.Fintype.Sum
 import Mathbin.Algebra.BigOperators.Basic
 
+#align_import combinatorics.hales_jewett from "leanprover-community/mathlib"@"23aa88e32dcc9d2a24cca7bc23268567ed4cd7d6"
+
 /-!
 # The Hales-Jewett theorem

23aa88e3

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -185,42 +185,58 @@ def prod {α ι ι'} (l : Line α ι) (l' : Line α ι') : Line α (Sum ι ι')
 #align combinatorics.line.prod Combinatorics.Line.prod
 -/
 
+#print Combinatorics.Line.apply /-
 theorem apply {α ι} (l : Line α ι) (x : α) : l x = fun i => (l.idxFun i).getD x :=
   rfl
 #align combinatorics.line.apply Combinatorics.Line.apply
+-/
 
+#print Combinatorics.Line.apply_none /-
 theorem apply_none {α ι} (l : Line α ι) (x : α) (i : ι) (h : l.idxFun i = none) : l x i = x := by
   simp only [Option.getD_none, h, l.apply]
 #align combinatorics.line.apply_none Combinatorics.Line.apply_none
+-/
 
+#print Combinatorics.Line.apply_of_ne_none /-
 theorem apply_of_ne_none {α ι} (l : Line α ι) (x : α) (i : ι) (h : l.idxFun i ≠ none) :
     some (l x i) = l.idxFun i := by rw [l.apply, Option.getD_of_ne_none h]
 #align combinatorics.line.apply_of_ne_none Combinatorics.Line.apply_of_ne_none
+-/
 
+#print Combinatorics.Line.map_apply /-
 @[simp]
 theorem map_apply {α α' ι} (f : α → α') (l : Line α ι) (x : α) : l.map f (f x) = f ∘ l x := by
   simp only [line.apply, line.map, Option.getD_map]
 #align combinatorics.line.map_apply Combinatorics.Line.map_apply
+-/
 
+#print Combinatorics.Line.vertical_apply /-
 @[simp]
 theorem vertical_apply {α ι ι'} (v : ι → α) (l : Line α ι') (x : α) :
     l.vertical v x = Sum.elim v (l x) := by funext i; cases i <;> rfl
 #align combinatorics.line.vertical_apply Combinatorics.Line.vertical_apply
+-/
 
+#print Combinatorics.Line.horizontal_apply /-
 @[simp]
 theorem horizontal_apply {α ι ι'} (l : Line α ι) (v : ι' → α) (x : α) :
     l.horizontal v x = Sum.elim (l x) v := by funext i; cases i <;> rfl
 #align combinatorics.line.horizontal_apply Combinatorics.Line.horizontal_apply
+-/
 
+#print Combinatorics.Line.prod_apply /-
 @[simp]
 theorem prod_apply {α ι ι'} (l : Line α ι) (l' : Line α ι') (x : α) :
     l.Prod l' x = Sum.elim (l x) (l' x) := by funext i; cases i <;> rfl
 #align combinatorics.line.prod_apply Combinatorics.Line.prod_apply
+-/
 
+#print Combinatorics.Line.diagonal_apply /-
 @[simp]
 theorem diagonal_apply {α ι} [Nonempty ι] (x : α) : Line.diagonal α ι x = fun i => x := by
   simp_rw [line.apply, line.diagonal, Option.getD_none]
 #align combinatorics.line.diagonal_apply Combinatorics.Line.diagonal_apply
+-/
 
 /-- The Hales-Jewett theorem. This version has a restriction on universe levels which is necessary
 for the proof. See `exists_mono_in_high_dimension` for a fully universe-polymorphic version. -/
@@ -344,6 +360,7 @@ theorem exists_mono_in_high_dimension (α : Type u) [Finite α] (κ : Type v) [F
 
 end Line
 
+#print Combinatorics.exists_mono_homothetic_copy /-
 /-- 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`. -/
 theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finset M) [Finite κ]
@@ -374,6 +391,7 @@ theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finse
     obtain ⟨y, hy⟩ := option.ne_none_iff_exists.mp hi.right
     simp_rw [line.apply, ← hy, Option.map_some', Option.getD_some]
 #align combinatorics.exists_mono_homothetic_copy Combinatorics.exists_mono_homothetic_copy
+-/
 
 end Combinatorics

23aa88e3

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -353,7 +353,7 @@ theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finse
   skip
   specialize hι fun v => C <| ∑ i, v i
   obtain ⟨l, c, hl⟩ := hι
-  set s : Finset ι := { i ∈ Finset.univ | l.idx_fun i = none } with hs
+  set s : Finset ι := {i ∈ Finset.univ | l.idx_fun i = none} with hs
   refine'
     ⟨s.card, finset.card_pos.mpr ⟨l.proper.some, _⟩, ∑ i in sᶜ, ((l.idx_fun i).map coe).getD 0, c,
       _⟩

23aa88e3

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -226,7 +226,7 @@ theorem diagonal_apply {α ι} [Nonempty ι] (x : α) : Line.diagonal α ι x =
 for the proof. See `exists_mono_in_high_dimension` for a fully universe-polymorphic version. -/
 private theorem exists_mono_in_high_dimension' :
     ∀ (α : Type u) [Finite α] (κ : Type max v u) [Finite κ],
-      ∃ (ι : Type)(_ : Fintype ι), ∀ C : (ι → α) → κ, ∃ l : Line α ι, l.IsMono C :=
+      ∃ (ι : Type) (_ : Fintype ι), ∀ C : (ι → α) → κ, ∃ l : Line α ι, l.IsMono C :=
   -- The proof proceeds by induction on `α`.
     Finite.induction_empty_option
     (-- We have to show that the theorem is invariant under `α ≃ α'` for the induction to work.
@@ -258,7 +258,7 @@ private theorem exists_mono_in_high_dimension' :
       -- `r` color focused lines or a monochromatic line.
       suffices key :
         ∀ r : ℕ,
-          ∃ (ι : Type)(_ : Fintype ι),
+          ∃ (ι : Type) (_ : Fintype ι),
             ∀ C : (ι → Option α) → κ, (∃ s : color_focused C, s.lines.card = r) ∨ ∃ l, is_mono C l
       -- Given the key claim, we simply take `r = |κ| + 1`. We cannot have this many distinct colors so
       -- we must be in the second case, where there is a monochromatic line.
@@ -334,7 +334,7 @@ private theorem exists_mono_in_high_dimension' :
 /-- 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 exists_mono_in_high_dimension (α : Type u) [Finite α] (κ : Type v) [Finite κ] :
-    ∃ (ι : Type)(_ : Fintype ι), ∀ C : (ι → α) → κ, ∃ l : Line α ι, l.IsMono C :=
+    ∃ (ι : Type) (_ : Fintype ι), ∀ C : (ι → α) → κ, ∃ l : Line α ι, l.IsMono C :=
   let ⟨ι, ιfin, hι⟩ := exists_mono_in_high_dimension' α (ULift κ)
   ⟨ι, ιfin, fun C =>
     let ⟨l, c, hc⟩ := hι (ULift.up ∘ C)
@@ -347,7 +347,7 @@ end Line
 /-- 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`. -/
 theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finset M) [Finite κ]
-    (C : M → κ) : ∃ a > 0, ∃ (b : M)(c : κ), ∀ s ∈ S, C (a • s + b) = c :=
+    (C : M → κ) : ∃ a > 0, ∃ (b : M) (c : κ), ∀ s ∈ S, C (a • s + b) = c :=
   by
   obtain ⟨ι, _inst, hι⟩ := line.exists_mono_in_high_dimension S κ
   skip
@@ -366,11 +366,11 @@ theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finse
   · rw [← Finset.sum_const]
     apply Finset.sum_congr rfl
     intro i hi
-    rw [hs, Finset.sep_def, Finset.mem_filter] at hi
+    rw [hs, Finset.sep_def, Finset.mem_filter] at hi 
     rw [l.apply_none _ _ hi.right, Subtype.coe_mk]
   · apply Finset.sum_congr rfl
     intro i hi
-    rw [hs, Finset.sep_def, Finset.compl_filter, Finset.mem_filter] at hi
+    rw [hs, Finset.sep_def, Finset.compl_filter, Finset.mem_filter] at hi 
     obtain ⟨y, hy⟩ := option.ne_none_iff_exists.mp hi.right
     simp_rw [line.apply, ← hy, Option.map_some', Option.getD_some]
 #align combinatorics.exists_mono_homothetic_copy Combinatorics.exists_mono_homothetic_copy

23aa88e3

bump to nightly-2023-06-01-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

4d9eaa85

Diff

@@ -222,12 +222,9 @@ theorem diagonal_apply {α ι} [Nonempty ι] (x : α) : Line.diagonal α ι x =
   simp_rw [line.apply, line.diagonal, Option.getD_none]
 #align combinatorics.line.diagonal_apply Combinatorics.Line.diagonal_apply
 
-/- warning: combinatorics.line.exists_mono_in_high_dimension' clashes with [anonymous] -> [anonymous]
-Case conversion may be inaccurate. Consider using '#align combinatorics.line.exists_mono_in_high_dimension' [anonymous]ₓ'. -/
-#print [anonymous] /-
 /-- The Hales-Jewett theorem. This version has a restriction on universe levels which is necessary
 for the proof. See `exists_mono_in_high_dimension` for a fully universe-polymorphic version. -/
-private theorem [anonymous] :
+private theorem exists_mono_in_high_dimension' :
     ∀ (α : Type u) [Finite α] (κ : Type max v u) [Finite κ],
       ∃ (ι : Type)(_ : Fintype ι), ∀ C : (ι → α) → κ, ∃ l : Line α ι, l.IsMono C :=
   -- The proof proceeds by induction on `α`.
@@ -332,7 +329,6 @@ private theorem [anonymous] :
         exact ⟨fun ⟨q, hq, he⟩ => h ⟨q, hq, he⟩, s.distinct_colors⟩
       -- Finally, we really do have `r+1` lines!
       · rw [Multiset.card_cons, Multiset.card_map, sr])
--/
 
 #print Combinatorics.Line.exists_mono_in_high_dimension /-
 /-- The Hales-Jewett theorem: for any finite types `α` and `κ`, there exists a finite type `ι` such

23aa88e3

bump to nightly-2023-05-28-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

8d353152

Diff

@@ -66,9 +66,9 @@ combinatorial line, Ramsey theory, arithmetic progession
 -/
 
 
-open Classical
+open scoped Classical
 
-open BigOperators
+open scoped BigOperators
 
 universe u v

23aa88e3

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -185,86 +185,38 @@ def prod {α ι ι'} (l : Line α ι) (l' : Line α ι') : Line α (Sum ι ι')
 #align combinatorics.line.prod Combinatorics.Line.prod
 -/
 
-/- warning: combinatorics.line.apply -> Combinatorics.Line.apply is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {ι : Type.{u2}} (l : Combinatorics.Line.{u1, u2} α ι) (x : α), Eq.{max (succ u2) (succ u1)} (ι -> α) (coeFn.{max (succ u1) (succ u2), max (succ u2) (succ u1)} (Combinatorics.Line.{u1, u2} α ι) (fun (_x : Combinatorics.Line.{u1, u2} α ι) => α -> ι -> α) (Combinatorics.Line.hasCoeToFun.{u1, u2} α ι) l x) (fun (i : ι) => Option.getD.{u1} α (Combinatorics.Line.idxFun.{u1, u2} α ι l i) x)
-but is expected to have type
-  forall {α : Type.{u2}} {ι : Type.{u1}} (l : Combinatorics.Line.{u2, u1} α ι) (x : α), Eq.{max (succ u1) (succ u2)} (ι -> α) ((fun (x : α) (i : ι) => Option.getD.{u2} α (Combinatorics.Line.idxFun.{u2, u1} α ι l i) x) x) (fun (i : ι) => Option.getD.{u2} α (Combinatorics.Line.idxFun.{u2, u1} α ι l i) x)
-Case conversion may be inaccurate. Consider using '#align combinatorics.line.apply Combinatorics.Line.applyₓ'. -/
 theorem apply {α ι} (l : Line α ι) (x : α) : l x = fun i => (l.idxFun i).getD x :=
   rfl
 #align combinatorics.line.apply Combinatorics.Line.apply
 
-/- warning: combinatorics.line.apply_none -> Combinatorics.Line.apply_none is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {ι : Type.{u2}} (l : Combinatorics.Line.{u1, u2} α ι) (x : α) (i : ι), (Eq.{succ u1} (Option.{u1} α) (Combinatorics.Line.idxFun.{u1, u2} α ι l i) (Option.none.{u1} α)) -> (Eq.{succ u1} α (coeFn.{max (succ u1) (succ u2), max (succ u2) (succ u1)} (Combinatorics.Line.{u1, u2} α ι) (fun (_x : Combinatorics.Line.{u1, u2} α ι) => α -> ι -> α) (Combinatorics.Line.hasCoeToFun.{u1, u2} α ι) l x i) x)
-but is expected to have type
-  forall {α : Type.{u2}} {ι : Type.{u1}} (l : Combinatorics.Line.{u2, u1} α ι) (x : α) (i : ι), (Eq.{succ u2} (Option.{u2} α) (Combinatorics.Line.idxFun.{u2, u1} α ι l i) (Option.none.{u2} α)) -> (Eq.{succ u2} α ((fun (x : α) (i : ι) => Option.getD.{u2} α (Combinatorics.Line.idxFun.{u2, u1} α ι l i) x) x i) x)
-Case conversion may be inaccurate. Consider using '#align combinatorics.line.apply_none Combinatorics.Line.apply_noneₓ'. -/
 theorem apply_none {α ι} (l : Line α ι) (x : α) (i : ι) (h : l.idxFun i = none) : l x i = x := by
   simp only [Option.getD_none, h, l.apply]
 #align combinatorics.line.apply_none Combinatorics.Line.apply_none
 
-/- warning: combinatorics.line.apply_of_ne_none -> Combinatorics.Line.apply_of_ne_none is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {ι : Type.{u2}} (l : Combinatorics.Line.{u1, u2} α ι) (x : α) (i : ι), (Ne.{succ u1} (Option.{u1} α) (Combinatorics.Line.idxFun.{u1, u2} α ι l i) (Option.none.{u1} α)) -> (Eq.{succ u1} (Option.{u1} α) (Option.some.{u1} α (coeFn.{max (succ u1) (succ u2), max (succ u2) (succ u1)} (Combinatorics.Line.{u1, u2} α ι) (fun (_x : Combinatorics.Line.{u1, u2} α ι) => α -> ι -> α) (Combinatorics.Line.hasCoeToFun.{u1, u2} α ι) l x i)) (Combinatorics.Line.idxFun.{u1, u2} α ι l i))
-but is expected to have type
-  forall {α : Type.{u2}} {ι : Type.{u1}} (l : Combinatorics.Line.{u2, u1} α ι) (x : α) (i : ι), (Ne.{succ u2} (Option.{u2} α) (Combinatorics.Line.idxFun.{u2, u1} α ι l i) (Option.none.{u2} α)) -> (Eq.{succ u2} (Option.{u2} α) (Option.some.{u2} α ((fun (x : α) (i : ι) => Option.getD.{u2} α (Combinatorics.Line.idxFun.{u2, u1} α ι l i) x) x i)) (Combinatorics.Line.idxFun.{u2, u1} α ι l i))
-Case conversion may be inaccurate. Consider using '#align combinatorics.line.apply_of_ne_none Combinatorics.Line.apply_of_ne_noneₓ'. -/
 theorem apply_of_ne_none {α ι} (l : Line α ι) (x : α) (i : ι) (h : l.idxFun i ≠ none) :
     some (l x i) = l.idxFun i := by rw [l.apply, Option.getD_of_ne_none h]
 #align combinatorics.line.apply_of_ne_none Combinatorics.Line.apply_of_ne_none
 
-/- warning: combinatorics.line.map_apply -> Combinatorics.Line.map_apply is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {α' : Type.{u2}} {ι : Type.{u3}} (f : α -> α') (l : Combinatorics.Line.{u1, u3} α ι) (x : α), Eq.{max (succ u3) (succ u2)} (ι -> α') (coeFn.{max (succ u2) (succ u3), max (succ u3) (succ u2)} (Combinatorics.Line.{u2, u3} α' ι) (fun (_x : Combinatorics.Line.{u2, u3} α' ι) => α' -> ι -> α') (Combinatorics.Line.hasCoeToFun.{u2, u3} α' ι) (Combinatorics.Line.map.{u1, u2, u3} α α' ι f l) (f x)) (Function.comp.{succ u3, succ u1, succ u2} ι α α' f (coeFn.{max (succ u1) (succ u3), max (succ u3) (succ u1)} (Combinatorics.Line.{u1, u3} α ι) (fun (_x : Combinatorics.Line.{u1, u3} α ι) => α -> ι -> α) (Combinatorics.Line.hasCoeToFun.{u1, u3} α ι) l x))
-but is expected to have type
-  forall {α : Type.{u3}} {α' : Type.{u2}} {ι : Type.{u1}} (f : α -> α') (l : Combinatorics.Line.{u3, u1} α ι) (x : α), Eq.{max (succ u1) (succ u2)} (ι -> α') ((fun (x : α') (i : ι) => Option.getD.{u2} α' (Combinatorics.Line.idxFun.{u2, u1} α' ι (Combinatorics.Line.map.{u3, u2, u1} α α' ι f l) i) x) (f x)) (Function.comp.{succ u1, succ u3, succ u2} ι α α' f ((fun (x : α) (i : ι) => Option.getD.{u3} α (Combinatorics.Line.idxFun.{u3, u1} α ι l i) x) x))
-Case conversion may be inaccurate. Consider using '#align combinatorics.line.map_apply Combinatorics.Line.map_applyₓ'. -/
 @[simp]
 theorem map_apply {α α' ι} (f : α → α') (l : Line α ι) (x : α) : l.map f (f x) = f ∘ l x := by
   simp only [line.apply, line.map, Option.getD_map]
 #align combinatorics.line.map_apply Combinatorics.Line.map_apply
 
-/- warning: combinatorics.line.vertical_apply -> Combinatorics.Line.vertical_apply is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {ι : Type.{u2}} {ι' : Type.{u3}} (v : ι -> α) (l : Combinatorics.Line.{u1, u3} α ι') (x : α), Eq.{max (max (succ u2) (succ u3)) (succ u1)} ((Sum.{u2, u3} ι ι') -> α) (coeFn.{max (succ u1) (succ (max u2 u3)), max (succ (max u2 u3)) (succ u1)} (Combinatorics.Line.{u1, max u2 u3} α (Sum.{u2, u3} ι ι')) (fun (_x : Combinatorics.Line.{u1, max u2 u3} α (Sum.{u2, u3} ι ι')) => α -> (Sum.{u2, u3} ι ι') -> α) (Combinatorics.Line.hasCoeToFun.{u1, max u2 u3} α (Sum.{u2, u3} ι ι')) (Combinatorics.Line.vertical.{u1, u2, u3} α ι ι' v l) x) (Sum.elim.{u2, u3, succ u1} ι ι' α v (coeFn.{max (succ u1) (succ u3), max (succ u3) (succ u1)} (Combinatorics.Line.{u1, u3} α ι') (fun (_x : Combinatorics.Line.{u1, u3} α ι') => α -> ι' -> α) (Combinatorics.Line.hasCoeToFun.{u1, u3} α ι') l x))
-but is expected to have type
-  forall {α : Type.{u3}} {ι : Type.{u2}} {ι' : Type.{u1}} (v : ι -> α) (l : Combinatorics.Line.{u3, u1} α ι') (x : α), Eq.{max (max (succ u1) (succ u3)) (succ u2)} ((Sum.{u2, u1} ι ι') -> α) ((fun (x : α) (i : Sum.{u2, u1} ι ι') => Option.getD.{u3} α (Combinatorics.Line.idxFun.{u3, max u1 u2} α (Sum.{u2, u1} ι ι') (Combinatorics.Line.vertical.{u3, u2, u1} α ι ι' v l) i) x) x) (Sum.elim.{u2, u1, succ u3} ι ι' α v ((fun (x : α) (i : ι') => Option.getD.{u3} α (Combinatorics.Line.idxFun.{u3, u1} α ι' l i) x) x))
-Case conversion may be inaccurate. Consider using '#align combinatorics.line.vertical_apply Combinatorics.Line.vertical_applyₓ'. -/
 @[simp]
 theorem vertical_apply {α ι ι'} (v : ι → α) (l : Line α ι') (x : α) :
     l.vertical v x = Sum.elim v (l x) := by funext i; cases i <;> rfl
 #align combinatorics.line.vertical_apply Combinatorics.Line.vertical_apply
 
-/- warning: combinatorics.line.horizontal_apply -> Combinatorics.Line.horizontal_apply is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {ι : Type.{u2}} {ι' : Type.{u3}} (l : Combinatorics.Line.{u1, u2} α ι) (v : ι' -> α) (x : α), Eq.{max (max (succ u2) (succ u3)) (succ u1)} ((Sum.{u2, u3} ι ι') -> α) (coeFn.{max (succ u1) (succ (max u2 u3)), max (succ (max u2 u3)) (succ u1)} (Combinatorics.Line.{u1, max u2 u3} α (Sum.{u2, u3} ι ι')) (fun (_x : Combinatorics.Line.{u1, max u2 u3} α (Sum.{u2, u3} ι ι')) => α -> (Sum.{u2, u3} ι ι') -> α) (Combinatorics.Line.hasCoeToFun.{u1, max u2 u3} α (Sum.{u2, u3} ι ι')) (Combinatorics.Line.horizontal.{u1, u2, u3} α ι ι' l v) x) (Sum.elim.{u2, u3, succ u1} ι ι' α (coeFn.{max (succ u1) (succ u2), max (succ u2) (succ u1)} (Combinatorics.Line.{u1, u2} α ι) (fun (_x : Combinatorics.Line.{u1, u2} α ι) => α -> ι -> α) (Combinatorics.Line.hasCoeToFun.{u1, u2} α ι) l x) v)
-but is expected to have type
-  forall {α : Type.{u3}} {ι : Type.{u2}} {ι' : Type.{u1}} (l : Combinatorics.Line.{u3, u2} α ι) (v : ι' -> α) (x : α), Eq.{max (max (succ u2) (succ u3)) (succ u1)} ((Sum.{u2, u1} ι ι') -> α) ((fun (x : α) (i : Sum.{u2, u1} ι ι') => Option.getD.{u3} α (Combinatorics.Line.idxFun.{u3, max u2 u1} α (Sum.{u2, u1} ι ι') (Combinatorics.Line.horizontal.{u3, u2, u1} α ι ι' l v) i) x) x) (Sum.elim.{u2, u1, succ u3} ι ι' α ((fun (x : α) (i : ι) => Option.getD.{u3} α (Combinatorics.Line.idxFun.{u3, u2} α ι l i) x) x) v)
-Case conversion may be inaccurate. Consider using '#align combinatorics.line.horizontal_apply Combinatorics.Line.horizontal_applyₓ'. -/
 @[simp]
 theorem horizontal_apply {α ι ι'} (l : Line α ι) (v : ι' → α) (x : α) :
     l.horizontal v x = Sum.elim (l x) v := by funext i; cases i <;> rfl
 #align combinatorics.line.horizontal_apply Combinatorics.Line.horizontal_apply
 
-/- warning: combinatorics.line.prod_apply -> Combinatorics.Line.prod_apply is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {ι : Type.{u2}} {ι' : Type.{u3}} (l : Combinatorics.Line.{u1, u2} α ι) (l' : Combinatorics.Line.{u1, u3} α ι') (x : α), Eq.{max (max (succ u2) (succ u3)) (succ u1)} ((Sum.{u2, u3} ι ι') -> α) (coeFn.{max (succ u1) (succ (max u2 u3)), max (succ (max u2 u3)) (succ u1)} (Combinatorics.Line.{u1, max u2 u3} α (Sum.{u2, u3} ι ι')) (fun (_x : Combinatorics.Line.{u1, max u2 u3} α (Sum.{u2, u3} ι ι')) => α -> (Sum.{u2, u3} ι ι') -> α) (Combinatorics.Line.hasCoeToFun.{u1, max u2 u3} α (Sum.{u2, u3} ι ι')) (Combinatorics.Line.prod.{u1, u2, u3} α ι ι' l l') x) (Sum.elim.{u2, u3, succ u1} ι ι' α (coeFn.{max (succ u1) (succ u2), max (succ u2) (succ u1)} (Combinatorics.Line.{u1, u2} α ι) (fun (_x : Combinatorics.Line.{u1, u2} α ι) => α -> ι -> α) (Combinatorics.Line.hasCoeToFun.{u1, u2} α ι) l x) (coeFn.{max (succ u1) (succ u3), max (succ u3) (succ u1)} (Combinatorics.Line.{u1, u3} α ι') (fun (_x : Combinatorics.Line.{u1, u3} α ι') => α -> ι' -> α) (Combinatorics.Line.hasCoeToFun.{u1, u3} α ι') l' x))
-but is expected to have type
-  forall {α : Type.{u3}} {ι : Type.{u2}} {ι' : Type.{u1}} (l : Combinatorics.Line.{u3, u2} α ι) (l' : Combinatorics.Line.{u3, u1} α ι') (x : α), Eq.{max (max (succ u2) (succ u3)) (succ u1)} ((Sum.{u2, u1} ι ι') -> α) ((fun (x : α) (i : Sum.{u2, u1} ι ι') => Option.getD.{u3} α (Combinatorics.Line.idxFun.{u3, max u2 u1} α (Sum.{u2, u1} ι ι') (Combinatorics.Line.prod.{u3, u2, u1} α ι ι' l l') i) x) x) (Sum.elim.{u2, u1, succ u3} ι ι' α ((fun (x : α) (i : ι) => Option.getD.{u3} α (Combinatorics.Line.idxFun.{u3, u2} α ι l i) x) x) ((fun (x : α) (i : ι') => Option.getD.{u3} α (Combinatorics.Line.idxFun.{u3, u1} α ι' l' i) x) x))
-Case conversion may be inaccurate. Consider using '#align combinatorics.line.prod_apply Combinatorics.Line.prod_applyₓ'. -/
 @[simp]
 theorem prod_apply {α ι ι'} (l : Line α ι) (l' : Line α ι') (x : α) :
     l.Prod l' x = Sum.elim (l x) (l' x) := by funext i; cases i <;> rfl
 #align combinatorics.line.prod_apply Combinatorics.Line.prod_apply
 
-/- warning: combinatorics.line.diagonal_apply -> Combinatorics.Line.diagonal_apply is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {ι : Type.{u2}} [_inst_1 : Nonempty.{succ u2} ι] (x : α), Eq.{max (succ u2) (succ u1)} (ι -> α) (coeFn.{max (succ u1) (succ u2), max (succ u2) (succ u1)} (Combinatorics.Line.{u1, u2} α ι) (fun (_x : Combinatorics.Line.{u1, u2} α ι) => α -> ι -> α) (Combinatorics.Line.hasCoeToFun.{u1, u2} α ι) (Combinatorics.Line.diagonal.{u1, u2} α ι _inst_1) x) (fun (i : ι) => x)
-but is expected to have type
-  forall {α : Type.{u2}} {ι : Type.{u1}} [_inst_1 : Nonempty.{succ u1} ι] (x : α), Eq.{max (succ u1) (succ u2)} (ι -> α) ((fun (x : α) (i : ι) => Option.getD.{u2} α (Combinatorics.Line.idxFun.{u2, u1} α ι (Combinatorics.Line.diagonal.{u2, u1} α ι _inst_1) i) x) x) (fun (i : ι) => x)
-Case conversion may be inaccurate. Consider using '#align combinatorics.line.diagonal_apply Combinatorics.Line.diagonal_applyₓ'. -/
 @[simp]
 theorem diagonal_apply {α ι} [Nonempty ι] (x : α) : Line.diagonal α ι x = fun i => x := by
   simp_rw [line.apply, line.diagonal, Option.getD_none]
@@ -396,12 +348,6 @@ theorem exists_mono_in_high_dimension (α : Type u) [Finite α] (κ : Type v) [F
 
 end Line
 
-/- warning: combinatorics.exists_mono_homothetic_copy -> Combinatorics.exists_mono_homothetic_copy is a dubious translation:
-lean 3 declaration is
-  forall {M : Type.{u1}} {κ : Type.{u2}} [_inst_1 : AddCommMonoid.{u1} M] (S : Finset.{u1} M) [_inst_2 : Finite.{succ u2} κ] (C : M -> κ), Exists.{1} Nat (fun (a : Nat) => Exists.{0} (GT.gt.{0} Nat Nat.hasLt a (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (fun (H : GT.gt.{0} Nat Nat.hasLt a (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) => Exists.{succ u1} M (fun (b : M) => Exists.{succ u2} κ (fun (c : κ) => forall (s : M), (Membership.Mem.{u1, u1} M (Finset.{u1} M) (Finset.hasMem.{u1} M) s S) -> (Eq.{succ u2} κ (C (HAdd.hAdd.{u1, u1, u1} M M M (instHAdd.{u1} M (AddZeroClass.toHasAdd.{u1} M (AddMonoid.toAddZeroClass.{u1} M (AddCommMonoid.toAddMonoid.{u1} M _inst_1)))) (SMul.smul.{0, u1} Nat M (AddMonoid.SMul.{u1} M (AddCommMonoid.toAddMonoid.{u1} M _inst_1)) a s) b)) c)))))
-but is expected to have type
-  forall {M : Type.{u2}} {κ : Type.{u1}} [_inst_1 : AddCommMonoid.{u2} M] (S : Finset.{u2} M) [_inst_2 : Finite.{succ u1} κ] (C : M -> κ), Exists.{1} Nat (fun (a : Nat) => And (GT.gt.{0} Nat instLTNat a (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (Exists.{succ u2} M (fun (b : M) => Exists.{succ u1} κ (fun (c : κ) => forall (s : M), (Membership.mem.{u2, u2} M (Finset.{u2} M) (Finset.instMembershipFinset.{u2} M) s S) -> (Eq.{succ u1} κ (C (HAdd.hAdd.{u2, u2, u2} M M M (instHAdd.{u2} M (AddZeroClass.toAdd.{u2} M (AddMonoid.toAddZeroClass.{u2} M (AddCommMonoid.toAddMonoid.{u2} M _inst_1)))) (HSMul.hSMul.{0, u2, u2} Nat M M (instHSMul.{0, u2} Nat M (AddMonoid.SMul.{u2} M (AddCommMonoid.toAddMonoid.{u2} M _inst_1))) a s) b)) c)))))
-Case conversion may be inaccurate. Consider using '#align combinatorics.exists_mono_homothetic_copy Combinatorics.exists_mono_homothetic_copyₓ'. -/
 /-- 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`. -/
 theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finset M) [Finite κ]

23aa88e3

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -234,9 +234,7 @@ but is expected to have type
 Case conversion may be inaccurate. Consider using '#align combinatorics.line.vertical_apply Combinatorics.Line.vertical_applyₓ'. -/
 @[simp]
 theorem vertical_apply {α ι ι'} (v : ι → α) (l : Line α ι') (x : α) :
-    l.vertical v x = Sum.elim v (l x) := by
-  funext i
-  cases i <;> rfl
+    l.vertical v x = Sum.elim v (l x) := by funext i; cases i <;> rfl
 #align combinatorics.line.vertical_apply Combinatorics.Line.vertical_apply
 
 /- warning: combinatorics.line.horizontal_apply -> Combinatorics.Line.horizontal_apply is a dubious translation:
@@ -247,9 +245,7 @@ but is expected to have type
 Case conversion may be inaccurate. Consider using '#align combinatorics.line.horizontal_apply Combinatorics.Line.horizontal_applyₓ'. -/
 @[simp]
 theorem horizontal_apply {α ι ι'} (l : Line α ι) (v : ι' → α) (x : α) :
-    l.horizontal v x = Sum.elim (l x) v := by
-  funext i
-  cases i <;> rfl
+    l.horizontal v x = Sum.elim (l x) v := by funext i; cases i <;> rfl
 #align combinatorics.line.horizontal_apply Combinatorics.Line.horizontal_apply
 
 /- warning: combinatorics.line.prod_apply -> Combinatorics.Line.prod_apply is a dubious translation:
@@ -260,9 +256,7 @@ but is expected to have type
 Case conversion may be inaccurate. Consider using '#align combinatorics.line.prod_apply Combinatorics.Line.prod_applyₓ'. -/
 @[simp]
 theorem prod_apply {α ι ι'} (l : Line α ι) (l' : Line α ι') (x : α) :
-    l.Prod l' x = Sum.elim (l x) (l' x) := by
-  funext i
-  cases i <;> rfl
+    l.Prod l' x = Sum.elim (l x) (l' x) := by funext i; cases i <;> rfl
 #align combinatorics.line.prod_apply Combinatorics.Line.prod_apply
 
 /- warning: combinatorics.line.diagonal_apply -> Combinatorics.Line.diagonal_apply is a dubious translation:
@@ -298,8 +292,7 @@ private theorem [anonymous] :
       -- This deals with the degenerate case where `α` is empty.
       intro κ _
       by_cases h : Nonempty κ
-      · skip
-        exact ⟨Unit, inferInstance, fun C => ⟨default, Classical.arbitrary _, PEmpty.rec _⟩⟩
+      · skip; exact ⟨Unit, inferInstance, fun C => ⟨default, Classical.arbitrary _, PEmpty.rec _⟩⟩
       · exact ⟨Empty, inferInstance, fun C => (h ⟨C (Empty.rec _)⟩).elim⟩)
     (by
       -- Now we have to show that the theorem holds for `option α` if it holds for `α`.
@@ -364,9 +357,7 @@ private theorem [anonymous] :
       -- If so then this is a `C'`-monochromatic line and we are done.
       · obtain ⟨p, p_mem, hp⟩ := h
         refine' Or.inr (mono_of_mono ⟨p.line, p.color, _⟩)
-        rintro (_ | _)
-        rw [hp, s.is_focused p p_mem]
-        apply p.has_color
+        rintro (_ | _); rw [hp, s.is_focused p p_mem]; apply p.has_color
       -- If not, we get `r+1` color focused lines by taking the product of the `r` lines with `l'` and
       -- adding to this the vertical line obtained by the focus point and `l`.
       refine'
@@ -424,8 +415,7 @@ theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finse
   refine'
     ⟨s.card, finset.card_pos.mpr ⟨l.proper.some, _⟩, ∑ i in sᶜ, ((l.idx_fun i).map coe).getD 0, c,
       _⟩
-  · rw [hs, Finset.sep_def, Finset.mem_filter]
-    exact ⟨Finset.mem_univ _, l.proper.some_spec⟩
+  · rw [hs, Finset.sep_def, Finset.mem_filter]; exact ⟨Finset.mem_univ _, l.proper.some_spec⟩
   intro x xs
   rw [← hl ⟨x, xs⟩]
   clear hl; congr

23aa88e3

bump to nightly-2023-05-28-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6c6011cf

Diff

@@ -389,7 +389,6 @@ private theorem [anonymous] :
         exact ⟨fun ⟨q, hq, he⟩ => h ⟨q, hq, he⟩, s.distinct_colors⟩
       -- Finally, we really do have `r+1` lines!
       · rw [Multiset.card_cons, Multiset.card_map, sr])
-#align combinatorics.line.exists_mono_in_high_dimension' [anonymous]
 -/
 
 #print Combinatorics.Line.exists_mono_in_high_dimension /-

23aa88e3

bump to nightly-2023-02-23-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/3ade05ac9447ae31a22d2ea5423435e054131240

5c91f1b0

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
 
 ! This file was ported from Lean 3 source module combinatorics.hales_jewett
-! leanprover-community/mathlib commit c3019c79074b0619edb4b27553a91b2e82242395
+! leanprover-community/mathlib commit 23aa88e32dcc9d2a24cca7bc23268567ed4cd7d6
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -16,6 +16,9 @@ import Mathbin.Algebra.BigOperators.Basic
 /-!
 # The Hales-Jewett theorem
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 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

c3019c79

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

1126441d

chore: replace refine' that already have a ?_ (#12261)

Co-authored-by: Moritz Firsching <firsching@google.com>

94b44d32

Diff

@@ -245,7 +245,7 @@ private theorem exists_mono_in_high_dimension' :
     -- Then `Option α` has only one element, so any line is monochromatic.
     by_cases h : Nonempty α
     case neg =>
-      refine' ⟨Unit, inferInstance, fun C => ⟨diagonal _ Unit, C fun _ => none, ?_⟩⟩
+      refine ⟨Unit, inferInstance, fun C => ⟨diagonal _ Unit, C fun _ => none, ?_⟩⟩
       rintro (_ | ⟨a⟩)
       · rfl
       · exact (h ⟨a⟩).elim

1126441d

chore: scope open Classical (#11199)

We remove all but one open Classicals, instead preferring to use open scoped Classical. The only real side-effect this led to is moving a couple declarations to use Exists.choose instead of Classical.choose.

The first few commits are explicitly labelled regex replaces for ease of review.

c747be0a

Diff

@@ -60,7 +60,7 @@ combinatorial line, Ramsey theory, arithmetic progression
 -/
 
 
-open Classical
+open scoped Classical
 
 open BigOperators

1126441d

doc: Mark named theorems (#8749)

a3708498

Diff

@@ -214,8 +214,9 @@ theorem diagonal_apply {α ι} [Nonempty ι] (x : α) : Line.diagonal α ι x =
   simp_rw [Line.diagonal, Option.getD_none]
 #align combinatorics.line.diagonal_apply Combinatorics.Line.diagonal_apply
 
-/-- The Hales-Jewett theorem. This version has a restriction on universe levels which is necessary
-for the proof. See `exists_mono_in_high_dimension` for a fully universe-polymorphic version. -/
+/-- The **Hales-Jewett theorem**. This version has a restriction on universe levels which is
+necessary for the proof. See `exists_mono_in_high_dimension` for a fully universe-polymorphic
+version. -/
 private theorem exists_mono_in_high_dimension' :
     ∀ (α : Type u) [Finite α] (κ : Type max v u) [Finite κ],
       ∃ (ι : Type) (_ : Fintype ι), ∀ C : (ι → α) → κ, ∃ l : Line α ι, l.IsMono C :=

1126441d

chore: cleanup some spaces (#7484)

Purely cosmetic PR.

c93575a3

Diff

@@ -343,7 +343,7 @@ theorem exists_mono_homothetic_copy {M κ : Type*} [AddCommMonoid M] (S : Finset
   obtain ⟨ι, _inst, hι⟩ := Line.exists_mono_in_high_dimension S κ
   specialize hι fun v => C <| ∑ i, v i
   obtain ⟨l, c, hl⟩ := hι
-  set s : Finset ι := Finset.univ.filter (fun i => l.idxFun i = none ) with hs
+  set s : Finset ι := Finset.univ.filter (fun i => l.idxFun i = none) with hs
   refine'
     ⟨s.card, Finset.card_pos.mpr ⟨l.proper.choose, _⟩, ∑ i in sᶜ, ((l.idxFun i).map _).getD 0,
       c, _⟩

1126441d

chore: avoid lean3 style have/suffices (#6964)

Many proofs use the "stream of consciousness" style from Lean 3, rather than have ... := or suffices ... from/by.

This PR updates a fraction of these to the preferred Lean 4 style.

I think a good goal would be to delete the "deferred" versions of have, suffices, and let at the bottom of Mathlib.Tactic.Have

(Anyone who would like to contribute more cleanup is welcome to push directly to this branch.)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

bdc47f68

Diff

@@ -254,10 +254,10 @@ private theorem exists_mono_in_high_dimension' :
       ∀ r : ℕ,
         ∃ (ι : Type) (_ : Fintype ι),
           ∀ C : (ι → Option α) → κ,
-            (∃ s : ColorFocused C, Multiset.card s.lines = r) ∨ ∃ l, IsMono C l
-    -- Given the key claim, we simply take `r = |κ| + 1`. We cannot have this many distinct colors
-    -- so we must be in the second case, where there is a monochromatic line.
-    · obtain ⟨ι, _inst, hι⟩ := key (Fintype.card κ + 1)
+            (∃ s : ColorFocused C, Multiset.card s.lines = r) ∨ ∃ l, IsMono C l by
+      -- Given the key claim, we simply take `r = |κ| + 1`. We cannot have this many distinct colors
+      -- so we must be in the second case, where there is a monochromatic line.
+      obtain ⟨ι, _inst, hι⟩ := key (Fintype.card κ + 1)
       refine' ⟨ι, _inst, fun C => (hι C).resolve_left _⟩
       rintro ⟨s, sr⟩
       apply Nat.not_succ_le_self (Fintype.card κ)

1126441d

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -16,7 +16,7 @@ import Mathlib.Algebra.BigOperators.Basic
 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
+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
@@ -78,7 +78,7 @@ Formally, a line is represented by a word `l.idxFun : ι → Option α` which sa
 `l.idxFun i = some y`).
 
 When `α` has size `1` there can be many elements of `Line α ι` defining the same function. -/
-structure Line (α ι : Type _) where
+structure Line (α ι : Type*) where
   /-- The word representing a combinatorial line. `l.idxfun i = none` means that
   `l x i = x` for all `x` and `l.idxfun i = some y` means that `l x i = y`. -/
   idxFun : ι → Option α
@@ -108,7 +108,7 @@ instance (α ι) [Nonempty ι] : Inhabited (Line α ι) :=
   ⟨diagonal α ι⟩
 
 /-- The type of lines that are only one color except possibly at their endpoints. -/
-structure AlmostMono {α ι κ : Type _} (C : (ι → Option α) → κ) where
+structure AlmostMono {α ι κ : Type*} (C : (ι → Option α) → κ) where
   /-- The underlying line of an almost monochromatic line, where the coordinate dimension `α` is
   extended by an additional symbol `none`, thought to be marking the endpoint of the line. -/
   line : Line (Option α) ι
@@ -119,7 +119,7 @@ structure AlmostMono {α ι κ : Type _} (C : (ι → Option α) → κ) where
   has_color : ∀ x : α, C (line (some x)) = color
 #align combinatorics.line.almost_mono Combinatorics.Line.AlmostMono
 
-instance {α ι κ : Type _} [Nonempty ι] [Inhabited κ] :
+instance {α ι κ : Type*} [Nonempty ι] [Inhabited κ] :
     Inhabited (AlmostMono fun _ : ι → Option α => (default : κ)) :=
   ⟨{  line := default
       color := default
@@ -130,7 +130,7 @@ instance {α ι κ : Type _} [Nonempty ι] [Inhabited κ] :
 - the lines all have the same endpoint
 - the colors of the lines are distinct.
 Used in the proof `exists_mono_in_high_dimension`. -/
-structure ColorFocused {α ι κ : Type _} (C : (ι → Option α) → κ) where
+structure ColorFocused {α ι κ : Type*} (C : (ι → Option α) → κ) where
   /-- The underlying multiset of almost monochromatic lines of a color-focused collection. -/
   lines : Multiset (AlmostMono C)
   /-- The common endpoint of the lines in the color-focused collection. -/
@@ -338,7 +338,7 @@ end Line
 
 /-- 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`. -/
-theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finset M) [Finite κ]
+theorem exists_mono_homothetic_copy {M κ : Type*} [AddCommMonoid M] (S : Finset M) [Finite κ]
     (C : M → κ) : ∃ a > 0, ∃ (b : M) (c : κ), ∀ s ∈ S, C (a • s + b) = c := by
   obtain ⟨ι, _inst, hι⟩ := Line.exists_mono_in_high_dimension S κ
   specialize hι fun v => C <| ∑ i, v i

1126441d

chore: tidy various files (#6274)

6b9326b4

Diff

@@ -16,7 +16,7 @@ import Mathlib.Algebra.BigOperators.Basic
 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
+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
@@ -99,8 +99,7 @@ def IsMono {α ι κ} (C : (ι → α) → κ) (l : Line α ι) : Prop :=
 #align combinatorics.line.is_mono Combinatorics.Line.IsMono
 
 /-- The diagonal line. It is the identity at every coordinate. -/
-def diagonal (α ι) [Nonempty ι] : Line α ι
-    where
+def diagonal (α ι) [Nonempty ι] : Line α ι where
   idxFun _ := none
   proper := ⟨Classical.arbitrary ι, rfl⟩
 #align combinatorics.line.diagonal Combinatorics.Line.diagonal
@@ -148,29 +147,25 @@ instance {α ι κ} (C : (ι → Option α) → κ) : Inhabited (ColorFocused C)
 
 /-- 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`. -/
-def map {α α' ι} (f : α → α') (l : Line α ι) : Line α' ι
-    where
+def map {α α' ι} (f : α → α') (l : Line α ι) : Line α' ι where
   idxFun i := (l.idxFun i).map f
   proper := ⟨l.proper.choose, by simp only [l.proper.choose_spec, Option.map_none']⟩
 #align combinatorics.line.map Combinatorics.Line.map
 
 /-- A point in `ι → α` and a line in `ι' → α` determine a line in `ι ⊕ ι' → α`. -/
-def vertical {α ι ι'} (v : ι → α) (l : Line α ι') : Line α (Sum ι ι')
-    where
+def vertical {α ι ι'} (v : ι → α) (l : Line α ι') : Line α (Sum ι ι') where
   idxFun := Sum.elim (some ∘ v) l.idxFun
   proper := ⟨Sum.inr l.proper.choose, l.proper.choose_spec⟩
 #align combinatorics.line.vertical Combinatorics.Line.vertical
 
 /-- A line in `ι → α` and a point in `ι' → α` determine a line in `ι ⊕ ι' → α`. -/
-def horizontal {α ι ι'} (l : Line α ι) (v : ι' → α) : Line α (Sum ι ι')
-    where
+def horizontal {α ι ι'} (l : Line α ι) (v : ι' → α) : Line α (Sum ι ι') where
   idxFun := Sum.elim l.idxFun (some ∘ v)
   proper := ⟨Sum.inl l.proper.choose, l.proper.choose_spec⟩
 #align combinatorics.line.horizontal Combinatorics.Line.horizontal
 
 /-- One line in `ι → α` and one in `ι' → α` together determine a line in `ι ⊕ ι' → α`. -/
-def prod {α ι ι'} (l : Line α ι) (l' : Line α ι') : Line α (Sum ι ι')
-    where
+def prod {α ι ι'} (l : Line α ι) (l' : Line α ι') : Line α (Sum ι ι') where
   idxFun := Sum.elim l.idxFun l'.idxFun
   proper := ⟨Sum.inl l.proper.choose, l.proper.choose_spec⟩
 #align combinatorics.line.prod Combinatorics.Line.prod
@@ -227,7 +222,7 @@ private theorem exists_mono_in_high_dimension' :
 -- The proof proceeds by induction on `α`.
   Finite.induction_empty_option
   (-- We have to show that the theorem is invariant under `α ≃ α'` for the induction to work.
-  @fun α α' e =>
+  fun {α α'} e =>
     forall_imp fun κ =>
       forall_imp fun _ =>
         Exists.imp fun ι =>
@@ -248,7 +243,7 @@ private theorem exists_mono_in_high_dimension' :
     -- empty.
     -- Then `Option α` has only one element, so any line is monochromatic.
     by_cases h : Nonempty α
-    on_goal 2 =>
+    case neg =>
       refine' ⟨Unit, inferInstance, fun C => ⟨diagonal _ Unit, C fun _ => none, ?_⟩⟩
       rintro (_ | ⟨a⟩)
       · rfl
@@ -346,7 +341,6 @@ monoid, and `S` is a finite subset, then there exists a monochromatic homothetic
 theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finset M) [Finite κ]
     (C : M → κ) : ∃ a > 0, ∃ (b : M) (c : κ), ∀ s ∈ S, C (a • s + b) = c := by
   obtain ⟨ι, _inst, hι⟩ := Line.exists_mono_in_high_dimension S κ
-  skip
   specialize hι fun v => C <| ∑ i, v i
   obtain ⟨l, c, hl⟩ := hι
   set s : Finset ι := Finset.univ.filter (fun i => l.idxFun i = none ) with hs

1126441d

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2021 David Wärn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
-
-! This file was ported from Lean 3 source module combinatorics.hales_jewett
-! leanprover-community/mathlib commit 1126441d6bccf98c81214a0780c73d499f6721fe
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Fintype.Option
 import Mathlib.Data.Fintype.Pi
 import Mathlib.Data.Fintype.Sum
 import Mathlib.Algebra.BigOperators.Basic
 
+#align_import combinatorics.hales_jewett from "leanprover-community/mathlib"@"1126441d6bccf98c81214a0780c73d499f6721fe"
+
 /-!
 # The Hales-Jewett theorem

1126441d

chore: cleanup whitespace (#5988)

Grepping for [^ .:{-] [^ :] and reviewing the results. Once I started I couldn't stop. :-)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

12343aa5

Diff

@@ -352,7 +352,7 @@ theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finse
   skip
   specialize hι fun v => C <| ∑ i, v i
   obtain ⟨l, c, hl⟩ := hι
-  set s : Finset ι :=  Finset.univ.filter (fun i => l.idxFun i = none ) with hs
+  set s : Finset ι := Finset.univ.filter (fun i => l.idxFun i = none ) with hs
   refine'
     ⟨s.card, Finset.card_pos.mpr ⟨l.proper.choose, _⟩, ∑ i in sᶜ, ((l.idxFun i).map _).getD 0,
       c, _⟩

1126441d

chore: formatting issues (#4947)

Co-authored-by: Scott Morrison <scott.morrison@anu.edu.au> Co-authored-by: Parcly Taxel <reddeloostw@gmail.com>

5068808d

Diff

@@ -260,7 +260,7 @@ private theorem exists_mono_in_high_dimension' :
     -- `r` color focused lines or a monochromatic line.
     suffices key :
       ∀ r : ℕ,
-        ∃ (ι : Type)(_ : Fintype ι),
+        ∃ (ι : Type) (_ : Fintype ι),
           ∀ C : (ι → Option α) → κ,
             (∃ s : ColorFocused C, Multiset.card s.lines = r) ∨ ∃ l, IsMono C l
     -- Given the key claim, we simply take `r = |κ| + 1`. We cannot have this many distinct colors
@@ -347,7 +347,7 @@ end Line
 /-- 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`. -/
 theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finset M) [Finite κ]
-    (C : M → κ) : ∃ a > 0, ∃ (b : M)(c : κ), ∀ s ∈ S, C (a • s + b) = c := by
+    (C : M → κ) : ∃ a > 0, ∃ (b : M) (c : κ), ∀ s ∈ S, C (a • s + b) = c := by
   obtain ⟨ι, _inst, hι⟩ := Line.exists_mono_in_high_dimension S κ
   skip
   specialize hι fun v => C <| ∑ i, v i

1126441d

chore: fix many typos (#4967)

These are all doc fixes

6f9e51c3

Diff

@@ -54,7 +54,7 @@ coordinates needed.
 
 ## Tags
 
-combinatorial line, Ramsey theory, arithmetic progession
+combinatorial line, Ramsey theory, arithmetic progression
 
 ### References

1126441d

feat: implement intermediate state for simp_rw (#3738)

closes #3680, see https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Stepping.20through.20simp_rw/near/326712986

ff334843

Diff

@@ -219,7 +219,7 @@ theorem prod_apply {α ι ι'} (l : Line α ι) (l' : Line α ι') (x : α) :
 
 @[simp]
 theorem diagonal_apply {α ι} [Nonempty ι] (x : α) : Line.diagonal α ι x = fun _ => x := by
-  simp_rw [Line.apply, Line.diagonal, Option.getD_none]
+  simp_rw [Line.diagonal, Option.getD_none]
 #align combinatorics.line.diagonal_apply Combinatorics.Line.diagonal_apply
 
 /-- The Hales-Jewett theorem. This version has a restriction on universe levels which is necessary
@@ -373,7 +373,7 @@ theorem exists_mono_homothetic_copy {M κ : Type _} [AddCommMonoid M] (S : Finse
     intro i hi
     rw [hs, Finset.compl_filter, Finset.mem_filter] at hi
     obtain ⟨y, hy⟩ := Option.ne_none_iff_exists.mp hi.right
-    simp_rw [Line.apply, ← hy, Option.map_some', Option.getD]
+    simp_rw [← hy, Option.map_some', Option.getD]
 #align combinatorics.exists_mono_homothetic_copy Combinatorics.exists_mono_homothetic_copy
 
 end Combinatorics

1126441d

chore: fix #align lines (#3640)

This PR fixes two things:

Most align statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align). This is often seen in the mathport output after ending calc blocks.
All remaining more-than-one-line #align statements. (This was needed for a script I wrote for #3630.)

2b42dc7c

Diff

@@ -194,7 +194,6 @@ theorem apply_of_ne_none {α ι} (l : Line α ι) (x : α) (i : ι) (h : l.idxFu
 theorem map_apply {α α' ι} (f : α → α') (l : Line α ι) (x : α) : l.map f (f x) = f ∘ l x := by
   simp only [Line.apply, Line.map, Option.getD_map]
   rfl
-
 #align combinatorics.line.map_apply Combinatorics.Line.map_apply
 
 @[simp]
@@ -341,9 +340,7 @@ theorem exists_mono_in_high_dimension (α : Type u) [Finite α] (κ : Type v) [F
   ⟨ι, ιfin, fun C =>
     let ⟨l, c, hc⟩ := hι (ULift.up ∘ C)
     ⟨l, c.down, fun x => by rw [← hc x, Function.comp_apply]⟩⟩
-#align
-  combinatorics.line.exists_mono_in_high_dimension
-  Combinatorics.Line.exists_mono_in_high_dimension
+#align combinatorics.line.exists_mono_in_high_dimension Combinatorics.Line.exists_mono_in_high_dimension
 
 end Line

1126441d

feat: port Combinatorics.HalesJewett (#1704)

Co-authored-by: Moritz Firsching <firsching@google.com> Co-authored-by: Lukas Miaskiwskyi <lukas.mias@gmail.com> Co-authored-by: David Wärn <codwarn@gmail.com> Co-authored-by: Johan Commelin <johan@commelin.net>

f2e18b20

`combinatorics.hales_jewett` ⟷ `Mathlib.Combinatorics.HalesJewett`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3 + 201

combinatorics.hales_jewett ⟷ Mathlib.Combinatorics.HalesJewett

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3 + 201

`combinatorics.hales_jewett` ⟷ `Mathlib.Combinatorics.HalesJewett`