oxford_invariants.2021summer.week3_p1 ⟷ Archive.OxfordInvariants.Summer2021.Week3P1

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

@@ -3,7 +3,7 @@ Copyright (c) 2021 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
 -/
-import Algebra.BigOperators.Order
+import Algebra.Order.BigOperators.Group.Finset
 import Algebra.BigOperators.Ring
 import Algebra.CharZero.Lemmas
 import Data.Rat.Cast.Defs

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

@@ -6,7 +6,7 @@ Authors: Yaël Dillies, Bhavik Mehta
 import Algebra.BigOperators.Order
 import Algebra.BigOperators.Ring
 import Algebra.CharZero.Lemmas
-import Data.Rat.Cast
+import Data.Rat.Cast.Defs
 
 #align_import oxford_invariants.«2021summer».week3_p1 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
 
@@ -143,7 +143,7 @@ theorem OxfordInvariants.week3_p1 (n : ℕ) (a : ℕ → ℕ) (a_pos : ∀ i ≤
         rw [Finset.sum_range_succ, hb, Finset.mul_sum]
         congr; ext i
         rw [← mul_div_assoc, ← mul_div_right_comm, mul_div_assoc,
-          mul_div_cancel _ (a_pos _ <| Nat.le_succ _).ne', mul_comm]
+          mul_div_cancel_right₀ _ (a_pos _ <| Nat.le_succ _).ne', mul_comm]
   -- Check the divisibility condition
   · rw [mul_tsub, ← mul_assoc, Nat.mul_div_cancel' ha, add_mul, Nat.mul_div_cancel' han,
       add_tsub_tsub_cancel ha₀, add_tsub_cancel_right]

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

@@ -95,7 +95,7 @@ theorem OxfordInvariants.week3_p1 (n : ℕ) (a : ℕ → ℕ) (a_pos : ∀ i ≤
       (b : α) = ∑ i in Finset.range (n + 1), a 0 * a (n + 1) / (a i * a (i + 1)) ∧
         a (n + 1) ∣ a n * b - a 0
   · exact ⟨b, hb⟩
-  simp_rw [← @Nat.cast_pos α] at a_pos 
+  simp_rw [← @Nat.cast_pos α] at a_pos
   /- Declare the induction
     `ih` will be the induction hypothesis -/
   induction' n with n ih

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

@@ -3,10 +3,10 @@ Copyright (c) 2021 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
 -/
-import Mathbin.Algebra.BigOperators.Order
-import Mathbin.Algebra.BigOperators.Ring
-import Mathbin.Algebra.CharZero.Lemmas
-import Mathbin.Data.Rat.Cast
+import Algebra.BigOperators.Order
+import Algebra.BigOperators.Ring
+import Algebra.CharZero.Lemmas
+import Data.Rat.Cast
 
 #align_import oxford_invariants.«2021summer».week3_p1 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
 

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

@@ -2,17 +2,14 @@
 Copyright (c) 2021 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
-
-! This file was ported from Lean 3 source module oxford_invariants.«2021summer».week3_p1
-! 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.Algebra.BigOperators.Order
 import Mathbin.Algebra.BigOperators.Ring
 import Mathbin.Algebra.CharZero.Lemmas
 import Mathbin.Data.Rat.Cast
 
+#align_import oxford_invariants.«2021summer».week3_p1 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
+
 /-!
 # The Oxford Invariants Puzzle Challenges - Summer 2021, Week 3, Problem 1
 

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: Yaël Dillies, Bhavik Mehta
 
 ! This file was ported from Lean 3 source module oxford_invariants.«2021summer».week3_p1
-! leanprover-community/mathlib commit 328375597f2c0dd00522d9c2e5a33b6a6128feeb
+! 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.Data.Rat.Cast
 /-!
 # The Oxford Invariants Puzzle Challenges - Summer 2021, Week 3, Problem 1
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 ## Original statement
 
 Let `n ≥ 3`, `a₁, ..., aₙ` be strictly positive integers such that `aᵢ ∣ aᵢ₋₁ + aᵢ₊₁` for

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

@@ -92,7 +92,7 @@ theorem OxfordInvariants.week3_p1 (n : ℕ) (a : ℕ → ℕ) (a_pos : ∀ i ≤
     Set up the stronger induction hypothesis -/
   rsuffices ⟨b, hb, -⟩ :
     ∃ b : ℕ,
-      ((b : α) = ∑ i in Finset.range (n + 1), a 0 * a (n + 1) / (a i * a (i + 1))) ∧
+      (b : α) = ∑ i in Finset.range (n + 1), a 0 * a (n + 1) / (a i * a (i + 1)) ∧
         a (n + 1) ∣ a n * b - a 0
   · exact ⟨b, hb⟩
   simp_rw [← @Nat.cast_pos α] at a_pos 

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

@@ -144,7 +144,6 @@ theorem OxfordInvariants.week3_p1 (n : ℕ) (a : ℕ → ℕ) (a_pos : ∀ i ≤
         congr; ext i
         rw [← mul_div_assoc, ← mul_div_right_comm, mul_div_assoc,
           mul_div_cancel _ (a_pos _ <| Nat.le_succ _).ne', mul_comm]
-      
   -- Check the divisibility condition
   · rw [mul_tsub, ← mul_assoc, Nat.mul_div_cancel' ha, add_mul, Nat.mul_div_cancel' han,
       add_tsub_tsub_cancel ha₀, add_tsub_cancel_right]

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,9 +3,9 @@ Copyright (c) 2021 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
 -/
-import Mathlib.Algebra.BigOperators.Order
 import Mathlib.Algebra.BigOperators.Ring
-import Mathlib.Algebra.CharZero.Lemmas
+import Mathlib.Algebra.Order.BigOperators.Group.Finset
+import Mathlib.Data.Nat.Cast.Field
 
 #align_import oxford_invariants.«2021summer».week3_p1 from "leanprover-community/mathlib"@"328375597f2c0dd00522d9c2e5a33b6a6128feeb"
 

List.mem_split duplicates List.append_of_mem from Std: https://github.com/leanprover/std4/blob/a756b7d643ae5dcd7bf314e99f8e493e5d81b9ed/Std/Data/List/Lemmas.lean#L94-L96

This PR makes it an alias.

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

@@ -137,7 +137,7 @@ theorem OxfordInvariants.Week3P1 (n : ℕ) (a : ℕ → ℕ) (a_pos : ∀ i ≤
         rw [Finset.sum_range_succ, hb, Finset.mul_sum]
         congr; ext i
         rw [← mul_div_assoc, ← mul_div_right_comm, mul_div_assoc,
-          mul_div_cancel _ (a_pos _ <| Nat.le_succ _).ne', mul_comm]
+          mul_div_cancel_right₀ _ (a_pos _ <| Nat.le_succ _).ne', mul_comm]
   -- Check the divisibility condition
   · rw [mul_tsub, ← mul_assoc, Nat.mul_div_cancel' ha, add_mul, Nat.mul_div_cancel' han,
       add_tsub_tsub_cancel ha₀, add_tsub_cancel_right]

No changes to tactic file, it's just boring fixes throughout the library.

This follows on from #6964.

Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

@@ -115,9 +115,9 @@ theorem OxfordInvariants.Week3P1 (n : ℕ) (a : ℕ → ℕ) (a_pos : ∀ i ≤
     rw [← @Nat.cast_le α, Nat.cast_mul, hb, ←
       div_le_iff' (a_pos _ <| n.le_succ.trans <| Nat.le_succ _), ←
       mul_div_mul_right _ _ (a_pos _ <| Nat.le_succ _).ne']
-    suffices h : ∀ i, i ∈ Finset.range (n + 1) → 0 ≤ (a 0 : α) * a (n + 1) / (a i * a (i + 1))
-    · exact Finset.single_le_sum h (Finset.self_mem_range_succ n)
-    refine' fun i _ => div_nonneg _ _ <;> refine' mul_nonneg _ _ <;> exact Nat.cast_nonneg _
+    suffices h : ∀ i, i ∈ Finset.range (n + 1) → 0 ≤ (a 0 : α) * a (n + 1) / (a i * a (i + 1)) from
+      Finset.single_le_sum h (Finset.self_mem_range_succ n)
+    refine fun i _ ↦ div_nonneg ?_ ?_ <;> refine mul_nonneg ?_ ?_ <;> exact Nat.cast_nonneg _
   -- Claim that the sum equals `(aₙ + aₙ₊₂)/aₙ₊₁ * b - (aₙ * b - a₀)/aₙ₊₁`
   refine' ⟨(a n + a (n + 2)) / a (n + 1) * b - (a n * b - a 0) / a (n + 1), _, _⟩
   -- Check that this indeed equals the sum

cliqueFree_of_replaceVertex_cliqueFree is still quite long.

@@ -71,7 +71,7 @@ natural.
 
 open scoped BigOperators
 
-variable {α : Type _} [LinearOrderedField α]
+variable {α : Type*} [LinearOrderedField α]
 
 theorem OxfordInvariants.Week3P1 (n : ℕ) (a : ℕ → ℕ) (a_pos : ∀ i ≤ n, 0 < a i)
     (ha : ∀ i, i + 2 ≤ n → a (i + 1) ∣ a i + a (i + 2)) :

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

@@ -6,7 +6,6 @@ Authors: Yaël Dillies, Bhavik Mehta
 import Mathlib.Algebra.BigOperators.Order
 import Mathlib.Algebra.BigOperators.Ring
 import Mathlib.Algebra.CharZero.Lemmas
-import Mathlib.Data.Rat.Cast
 
 #align_import oxford_invariants.«2021summer».week3_p1 from "leanprover-community/mathlib"@"328375597f2c0dd00522d9c2e5a33b6a6128feeb"
 

• depends on: #5966

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

@@ -2,17 +2,14 @@
 Copyright (c) 2021 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
-
-! This file was ported from Lean 3 source module oxford_invariants.2021summer.week3_p1
-! leanprover-community/mathlib commit 328375597f2c0dd00522d9c2e5a33b6a6128feeb
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Algebra.BigOperators.Order
 import Mathlib.Algebra.BigOperators.Ring
 import Mathlib.Algebra.CharZero.Lemmas
 import Mathlib.Data.Rat.Cast
 
+#align_import oxford_invariants.«2021summer».week3_p1 from "leanprover-community/mathlib"@"328375597f2c0dd00522d9c2e5a33b6a6128feeb"
+
 /-!
 # The Oxford Invariants Puzzle Challenges - Summer 2021, Week 3, Problem 1
 

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