imo.imo1998_q2 ⟷ Archive.Imo.Imo1998Q2

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

@@ -5,7 +5,7 @@ Authors: Oliver Nash
 -/
 import Data.Fintype.Prod
 import Data.Int.Parity
-import Algebra.BigOperators.Order
+import Algebra.Order.BigOperators.Group.Finset
 import Tactic.Ring
 import Tactic.NoncommRing
 

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

@@ -157,7 +157,7 @@ theorem a_card_upper_bound {k : ℕ}
   rw [← Finset.offDiag_card]
   apply Finset.card_le_mul_card_image_of_maps_to (A_maps_to_off_diag_judge_pair r)
   intro p hp
-  have hp' : p.distinct := by simp [Finset.mem_offDiag] at hp ; exact hp
+  have hp' : p.distinct := by simp [Finset.mem_offDiag] at hp; exact hp
   rw [← A_fibre_over_judge_pair_card r hp']; apply hk; exact hp'
 #align imo1998_q2.A_card_upper_bound Imo1998Q2.a_card_upper_bound
 
@@ -207,7 +207,7 @@ theorem distinct_judge_pairs_card_lower_bound {z : ℕ} (hJ : Fintype.card J = 2
     · suffices p.judge₁ = p.judge₂ by simp [this]; finish
   have hst' : (s \ t).card = 2 * z + 1 := by rw [hst, Finset.diag_card, ← hJ]; rfl
   rw [Finset.filter_and, ← Finset.sdiff_sdiff_self_left s t, Finset.card_sdiff]
-  · rw [hst']; rw [add_assoc] at hs ; apply le_tsub_of_add_le_right hs
+  · rw [hst']; rw [add_assoc] at hs; apply le_tsub_of_add_le_right hs
   · apply Finset.sdiff_subset
 #align imo1998_q2.distinct_judge_pairs_card_lower_bound Imo1998Q2.distinct_judge_pairs_card_lower_bound
 
@@ -238,14 +238,14 @@ theorem imo1998_q2 [Fintype J] [Fintype C] (a b k : ℕ) (hC : Fintype.card C =
     (b - 1 : ℚ) / (2 * b) ≤ k / a :=
   by
   rw [clear_denominators ha hb.pos]
-  obtain ⟨z, hz⟩ := hb; rw [hz] at hJ ; rw [hz]
+  obtain ⟨z, hz⟩ := hb; rw [hz] at hJ; rw [hz]
   have h := le_trans (A_card_lower_bound r hJ) (A_card_upper_bound r hk)
-  rw [hC, hJ] at h 
+  rw [hC, hJ] at h
   -- We are now essentially done; we just need to bash `h` into exactly the right shape.
   have hl : k * ((2 * z + 1) * (2 * z + 1) - (2 * z + 1)) = k * (2 * (2 * z + 1)) * z := by
     simp only [add_mul, two_mul, mul_comm, mul_assoc]; finish
   have hr : 2 * z * z * a = 2 * z * a * z := by ring
-  rw [hl, hr] at h 
+  rw [hl, hr] at h
   cases z
   · simp
   · exact le_of_mul_le_mul_right h z.succ_pos

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

@@ -3,11 +3,11 @@ Copyright (c) 2020 Oliver Nash. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Oliver Nash
 -/
-import Mathbin.Data.Fintype.Prod
-import Mathbin.Data.Int.Parity
-import Mathbin.Algebra.BigOperators.Order
-import Mathbin.Tactic.Ring
-import Mathbin.Tactic.NoncommRing
+import Data.Fintype.Prod
+import Data.Int.Parity
+import Algebra.BigOperators.Order
+import Tactic.Ring
+import Tactic.NoncommRing
 
 #align_import imo.imo1998_q2 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
 

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

@@ -2,11 +2,6 @@
 Copyright (c) 2020 Oliver Nash. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Oliver Nash
-
-! This file was ported from Lean 3 source module imo.imo1998_q2
-! leanprover-community/mathlib commit 08b081ea92d80e3a41f899eea36ef6d56e0f1db0
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Fintype.Prod
 import Mathbin.Data.Int.Parity
@@ -14,6 +9,8 @@ import Mathbin.Algebra.BigOperators.Order
 import Mathbin.Tactic.Ring
 import Mathbin.Tactic.NoncommRing
 
+#align_import imo.imo1998_q2 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
+
 /-!
 # IMO 1998 Q2
 

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

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Oliver Nash
 
 ! This file was ported from Lean 3 source module imo.imo1998_q2
-! leanprover-community/mathlib commit 308826471968962c6b59c7ff82a22757386603e3
+! leanprover-community/mathlib commit 08b081ea92d80e3a41f899eea36ef6d56e0f1db0
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -16,6 +16,9 @@ import Mathbin.Tactic.NoncommRing
 
 /-!
 # IMO 1998 Q2
+
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
 In a competition, there are `a` contestants and `b` judges, where `b ≥ 3` is an odd integer. Each
 judge rates each contestant as either "pass" or "fail". Suppose `k` is a number such that, for any
 two judges, their ratings coincide for at most `k` contestants. Prove that `k / a ≥ (b - 1) / (2b)`.

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

Take the content of

• some of Algebra.BigOperators.List.Basic
• some of Algebra.BigOperators.List.Lemmas
• some of Algebra.BigOperators.Multiset.Basic
• some of Algebra.BigOperators.Multiset.Lemmas
• Algebra.BigOperators.Multiset.Order
• Algebra.BigOperators.Order

and sort it into six files:

• Algebra.Order.BigOperators.Group.List. I credit Yakov for https://github.com/leanprover-community/mathlib/pull/8543.
• Algebra.Order.BigOperators.Group.Multiset. Copyright inherited from Algebra.BigOperators.Multiset.Order.
• Algebra.Order.BigOperators.Group.Finset. Copyright inherited from Algebra.BigOperators.Order.
• Algebra.Order.BigOperators.Ring.List. I credit Stuart for https://github.com/leanprover-community/mathlib/pull/10184.
• Algebra.Order.BigOperators.Ring.Multiset. I credit Ruben for https://github.com/leanprover-community/mathlib/pull/8787.
• Algebra.Order.BigOperators.Ring.Finset. I credit Floris for https://github.com/leanprover-community/mathlib/pull/1294.

Here are the design decisions at play:

• Pure algebra and big operators algebra shouldn't import (algebraic) order theory. This PR makes that better, but not perfect because we still import Data.Nat.Order.Basic in a few List files.
• It's Algebra.Order.BigOperators instead of Algebra.BigOperators.Order because algebraic order theory is more of a theory than big operators algebra. Another reason is that algebraic order theory is the only way to mix pure order and pure algebra, while there are more ways to mix pure finiteness and pure algebra than just big operators.
• There are separate files for group/monoid lemmas vs ring lemmas. Groups/monoids are the natural setup for big operators, so their lemmas shouldn't be mixed with ring lemmas that involves both addition and multiplication. As a result, everything under Algebra.Order.BigOperators.Group should be additivisable (except a few Nat- or Int-specific lemmas). In contrast, things under Algebra.Order.BigOperators.Ring are more prone to having heavy imports.
• Lemmas are separated according to List vs Multiset vs Finset. This is not strictly necessary, and can be relaxed in cases where there aren't that many lemmas to be had. As an example, I could split out the AbsoluteValue lemmas from Algebra.Order.BigOperators.Ring.Finset to a file Algebra.Order.BigOperators.Ring.AbsoluteValue and it could stay this way until too many lemmas are in this file (or a split is needed for import reasons), in which case we would need files Algebra.Order.BigOperators.Ring.AbsoluteValue.Finset, Algebra.Order.BigOperators.Ring.AbsoluteValue.Multiset, etc...
• Finsupp big operator and finprod/finsum order lemmas also belong in Algebra.Order.BigOperators. I haven't done so in this PR because the diff is big enough like that.

@@ -3,12 +3,12 @@ Copyright (c) 2020 Oliver Nash. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Oliver Nash
 -/
-import Mathlib.Algebra.BigOperators.Order
+import Mathlib.Algebra.Order.BigOperators.Group.Finset
 import Mathlib.Algebra.Order.Field.Basic
-import Mathlib.Data.Fintype.Prod
 import Mathlib.Data.Int.Parity
 import Mathlib.GroupTheory.GroupAction.Ring
 import Mathlib.Tactic.NoncommRing
+import Mathlib.Tactic.Ring
 
 #align_import imo.imo1998_q2 from "leanprover-community/mathlib"@"308826471968962c6b59c7ff82a22757386603e3"
 

Let κ : kernel α (γ × β) and ν : kernel α γ be two finite kernels with kernel.fst κ ≤ ν, where γ has a countably generated σ-algebra (true in particular for standard Borel spaces). We build a function f : α → γ → Set β → ℝ jointly measurable in the first two arguments such that for all a : α and all measurable sets s : Set β and A : Set γ, ∫ x in A, f a x s ∂(ν a) = (κ a (A ×ˢ s)).toReal.

Co-authored-by: Rémy Degenne <remydegenne@gmail.com>

@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Oliver Nash
 -/
 import Mathlib.Algebra.BigOperators.Order
+import Mathlib.Algebra.Order.Field.Basic
 import Mathlib.Data.Fintype.Prod
 import Mathlib.Data.Int.Parity
 import Mathlib.GroupTheory.GroupAction.Ring

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

• converts "--porting note" into "-- Porting note";
• converts "porting note" into "Porting note".

@@ -40,7 +40,7 @@ Rearranging gives the result.
 -/
 
 
--- porting note: `A` already upper case
+-- Porting note: `A` already upper case
 set_option linter.uppercaseLean3 false
 
 open scoped Classical
@@ -140,7 +140,7 @@ theorem A_fibre_over_judgePair {p : JudgePair J} (h : p.Distinct) :
     AgreedTriple.contestant := by
   dsimp only [A, agreedContestants]; ext c; constructor <;> intro h
   · rw [Finset.mem_image]; refine' ⟨⟨c, p⟩, _⟩; aesop
-  -- porting note: this used to be `finish`
+  -- Porting note: this used to be `finish`
   · simp only [Finset.mem_filter, Finset.mem_image, Prod.exists] at h
     rcases h with ⟨_, ⟨_, ⟨_, ⟨h, _⟩⟩⟩⟩
     cases h; aesop
@@ -230,7 +230,7 @@ end
 theorem clear_denominators {a b k : ℕ} (ha : 0 < a) (hb : 0 < b) :
     (b - 1 : ℚ) / (2 * b) ≤ k / a ↔ ((b : ℕ) - 1) * a ≤ k * (2 * b) := by
   rw [div_le_div_iff]
-  -- porting note: proof used to finish with `<;> norm_cast <;> simp [ha, hb]`
+  -- Porting note: proof used to finish with `<;> norm_cast <;> simp [ha, hb]`
   · convert Nat.cast_le (α := ℚ)
     · aesop
     · norm_cast

Classifies by adding issue number (#10936) to porting notes claiming anything semantically equivalent to:

• "used to be tidy"
• "was tidy "

@@ -131,7 +131,7 @@ theorem A_fibre_over_contestant_card (c : C) :
       ((A r).filter fun a : AgreedTriple C J => a.contestant = c).card := by
   rw [A_fibre_over_contestant r]
   apply Finset.card_image_of_injOn
-  -- porting note: used to be `tidy`. TODO: remove `ext` after `extCore` to `aesop`.
+  -- Porting note (#10936): used to be `tidy`. TODO: remove `ext` after `extCore` to `aesop`.
   unfold Set.InjOn; intros; ext; all_goals aesop
 #align imo1998_q2.A_fibre_over_contestant_card Imo1998Q2.A_fibre_over_contestant_card
 
@@ -151,7 +151,7 @@ theorem A_fibre_over_judgePair_card {p : JudgePair J} (h : p.Distinct) :
       ((A r).filter fun a : AgreedTriple C J => a.judgePair = p).card := by
   rw [A_fibre_over_judgePair r h]
   apply Finset.card_image_of_injOn
-  -- porting note: used to be `tidy`
+  -- Porting note (#10936): used to be `tidy`
   unfold Set.InjOn; intros; ext; all_goals aesop
 #align imo1998_q2.A_fibre_over_judge_pair_card Imo1998Q2.A_fibre_over_judgePair_card
 

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

@@ -191,7 +191,7 @@ theorem judge_pairs_card_lower_bound {z : ℕ} (hJ : Fintype.card J = 2 * z + 1)
   let x := (Finset.univ.filter fun j => r c j).card
   let y := (Finset.univ.filter fun j => ¬r c j).card
   have h : (Finset.univ.filter fun p : JudgePair J => p.Agree r c).card = x * x + y * y := by
-    simp [← Finset.filter_product_card]
+    simp [x, y, ← Finset.filter_product_card]
   rw [h]; apply Int.le_of_ofNat_le_ofNat; simp only [Int.ofNat_add, Int.ofNat_mul]
   apply norm_bound_of_odd_sum
   suffices x + y = 2 * z + 1 by simp [← Int.ofNat_add, this]
@@ -204,9 +204,11 @@ theorem distinct_judge_pairs_card_lower_bound {z : ℕ} (hJ : Fintype.card J = 2
   let t := Finset.univ.filter fun p : JudgePair J => p.Distinct
   have hs : 2 * z * z + 2 * z + 1 ≤ s.card := judge_pairs_card_lower_bound r hJ c
   have hst : s \ t = Finset.univ.diag := by
-    ext p; constructor <;> intros
-    · aesop
-    · suffices p.judge₁ = p.judge₂ by simp [this]
+    ext p; constructor <;> intros hp
+    · unfold_let s t at hp
+      aesop
+    · unfold_let s t
+      suffices p.judge₁ = p.judge₂ by simp [this]
       aesop
   have hst' : (s \ t).card = 2 * z + 1 := by rw [hst, Finset.diag_card, ← hJ]; rfl
   rw [Finset.filter_and, ← Finset.sdiff_sdiff_self_left s t, Finset.card_sdiff]

These lemmas can be proved much earlier with little to no change to their proofs.

Part of #9411

@@ -3,10 +3,10 @@ Copyright (c) 2020 Oliver Nash. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Oliver Nash
 -/
+import Mathlib.Algebra.BigOperators.Order
 import Mathlib.Data.Fintype.Prod
 import Mathlib.Data.Int.Parity
-import Mathlib.Algebra.BigOperators.Order
-import Mathlib.Tactic.Ring
+import Mathlib.GroupTheory.GroupAction.Ring
 import Mathlib.Tactic.NoncommRing
 
 #align_import imo.imo1998_q2 from "leanprover-community/mathlib"@"308826471968962c6b59c7ff82a22757386603e3"

cliqueFree_of_replaceVertex_cliqueFree is still quite long.

@@ -45,19 +45,19 @@ set_option linter.uppercaseLean3 false
 
 open scoped Classical
 
-variable {C J : Type _} (r : C → J → Prop)
+variable {C J : Type*} (r : C → J → Prop)
 
 namespace Imo1998Q2
 
 noncomputable section
 
 /-- An ordered pair of judges. -/
-abbrev JudgePair (J : Type _) :=
+abbrev JudgePair (J : Type*) :=
   J × J
 #align imo1998_q2.judge_pair Imo1998Q2.JudgePair
 
 /-- A triple consisting of contestant together with an ordered pair of judges. -/
-abbrev AgreedTriple (C J : Type _) :=
+abbrev AgreedTriple (C J : Type*) :=
   C × JudgePair J
 #align imo1998_q2.agreed_triple Imo1998Q2.AgreedTriple
 
@@ -168,7 +168,7 @@ theorem A_card_upper_bound {k : ℕ}
 
 end
 
-theorem add_sq_add_sq_sub {α : Type _} [Ring α] (x y : α) :
+theorem add_sq_add_sq_sub {α : Type*} [Ring α] (x y : α) :
     (x + y) * (x + y) + (x - y) * (x - y) = 2 * x * x + 2 * y * y := by noncomm_ring
 #align imo1998_q2.add_sq_add_sq_sub Imo1998Q2.add_sq_add_sq_sub
 

This generalizes some Nat.cast lemmas from OrderedSemiring α to the conjunction of AddCommMonoidWithOne α, PartialOrder α, CovariantClass α α (· + ·) (· ≤ ·), ZeroLEOneClass α; collectively, these make up an OrderedAddCommMonoidWithOne, but that type class doesn't actually exist.

This generalization is not without purpose, the new lemmas will apply to StarOrderedRings, as well as the selfAdjoint part thereof, as well as the subtype {x : α // 0 ≤ x} of positive elements in a StarOrderedRing. These can be seen in #4871.

Because we are generalizing some fundamental simp lemmas from a single bundled type class to a bag of several classes, Lean had trouble in a few places. So, we opt to keep the OrderedSemiring versions of these simp lemmas as a special case, and we mark the more general versions with @[simp low]. This also avoids needing to update the positivity extension for Nat.cast to the more general setting for the time being.

@@ -229,7 +229,7 @@ theorem clear_denominators {a b k : ℕ} (ha : 0 < a) (hb : 0 < b) :
     (b - 1 : ℚ) / (2 * b) ≤ k / a ↔ ((b : ℕ) - 1) * a ≤ k * (2 * b) := by
   rw [div_le_div_iff]
   -- porting note: proof used to finish with `<;> norm_cast <;> simp [ha, hb]`
-  · convert @Nat.cast_le ℚ _ _ _ _
+  · convert Nat.cast_le (α := ℚ)
     · aesop
     · norm_cast
   all_goals simp [ha, hb]

• depends on: #5966

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

@@ -2,11 +2,6 @@
 Copyright (c) 2020 Oliver Nash. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Oliver Nash
-
-! This file was ported from Lean 3 source module imo.imo1998_q2
-! leanprover-community/mathlib commit 308826471968962c6b59c7ff82a22757386603e3
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Fintype.Prod
 import Mathlib.Data.Int.Parity
@@ -14,6 +9,8 @@ import Mathlib.Algebra.BigOperators.Order
 import Mathlib.Tactic.Ring
 import Mathlib.Tactic.NoncommRing
 
+#align_import imo.imo1998_q2 from "leanprover-community/mathlib"@"308826471968962c6b59c7ff82a22757386603e3"
+
 /-!
 # IMO 1998 Q2
 In a competition, there are `a` contestants and `b` judges, where `b ≥ 3` is an odd integer. Each

This is the second half of the changes originally in #5699, removing all occurrences of ; after a space and implementing a linter rule to enforce it.

In most cases this 2-character substring has a space after it, so the following command was run first:

find . -type f -name "*.lean" -exec sed -i -E 's/ ; /; /g' {} \;

The remaining cases were few enough in number that they were done manually.

@@ -165,7 +165,7 @@ theorem A_card_upper_bound {k : ℕ}
   rw [← Finset.offDiag_card]
   apply Finset.card_le_mul_card_image_of_maps_to (A_maps_to_offDiag_judgePair r)
   intro p hp
-  have hp' : p.Distinct := by simp [Finset.mem_offDiag] at hp ; exact hp
+  have hp' : p.Distinct := by simp [Finset.mem_offDiag] at hp; exact hp
   rw [← A_fibre_over_judgePair_card r hp']; apply hk; exact hp'
 #align imo1998_q2.A_card_upper_bound Imo1998Q2.A_card_upper_bound
 
@@ -213,7 +213,7 @@ theorem distinct_judge_pairs_card_lower_bound {z : ℕ} (hJ : Fintype.card J = 2
       aesop
   have hst' : (s \ t).card = 2 * z + 1 := by rw [hst, Finset.diag_card, ← hJ]; rfl
   rw [Finset.filter_and, ← Finset.sdiff_sdiff_self_left s t, Finset.card_sdiff]
-  · rw [hst']; rw [add_assoc] at hs ; apply le_tsub_of_add_le_right hs
+  · rw [hst']; rw [add_assoc] at hs; apply le_tsub_of_add_le_right hs
   · apply Finset.sdiff_subset
 #align imo1998_q2.distinct_judge_pairs_card_lower_bound Imo1998Q2.distinct_judge_pairs_card_lower_bound
 
@@ -249,7 +249,7 @@ theorem imo1998_q2 [Fintype J] [Fintype C] (a b k : ℕ) (hC : Fintype.card C =
     (hk : ∀ p : JudgePair J, p.Distinct → (agreedContestants r p).card ≤ k) :
     (b - 1 : ℚ) / (2 * b) ≤ k / a := by
   rw [clear_denominators ha hb.pos]
-  obtain ⟨z, hz⟩ := hb; rw [hz] at hJ ; rw [hz]
+  obtain ⟨z, hz⟩ := hb; rw [hz] at hJ; rw [hz]
   have h := le_trans (A_card_lower_bound r hJ) (A_card_upper_bound r hk)
   rw [hC, hJ] at h
   -- We are now essentially done; we just need to bash `h` into exactly the right shape.

Make sure in particular one can import Mathlib.Tactic for teaching without getting category theory notations in scope. Note that only two files needed an extra open.