imo.imo2013_q1 ⟷ Archive.Imo.Imo2013Q1

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

@@ -3,7 +3,7 @@ Copyright (c) 2021 David Renshaw. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Renshaw
 -/
-import Data.Pnat.Basic
+import Data.PNat.Basic
 import Data.Nat.Parity
 import Algebra.BigOperators.Pi
 import Tactic.Ring
@@ -81,7 +81,7 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
       exact ne_of_gt <| arith_lemma pk t
     calc
       (1 : ℚ) + (2 ^ pk.succ - 1) / ↑n = 1 + (2 * 2 ^ pk - 1) / (2 * (t + 1) : ℕ) := by
-        rw [coe_coe n, ht, pow_succ]
+        rw [coe_coe n, ht, pow_succ']
       _ = (1 + 1 / (2 * t + 2 * 2 ^ pk)) * (1 + (2 ^ pk - 1) / (↑t + 1)) :=
         by
         field_simp [t.cast_add_one_ne_zero]
@@ -100,7 +100,7 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
     have denom_ne_zero : 2 * (t : ℚ) + 1 ≠ 0 := by norm_cast; apply (2 * t).succ_ne_zero
     calc
       (1 : ℚ) + (2 ^ pk.succ - 1) / ↑n = 1 + (2 * 2 ^ pk - 1) / (2 * t + 1 : ℕ) := by
-        rw [coe_coe n, ht, pow_succ]
+        rw [coe_coe n, ht, pow_succ']
       _ = (1 + 1 / (2 * t + 1)) * (1 + (2 ^ pk - 1) / (t + 1)) :=
         by
         field_simp [t.cast_add_one_ne_zero]

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

@@ -66,10 +66,10 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
   intro n
   obtain ⟨t, ht : ↑n = t + t⟩ | ⟨t, ht : ↑n = 2 * t + 1⟩ := (n : ℕ).even_or_odd
   · -- even case
-    rw [← two_mul] at ht 
+    rw [← two_mul] at ht
     cases t
     -- Eliminate the zero case to simplify later calculations.
-    · exfalso; rw [MulZeroClass.mul_zero] at ht ; exact PNat.ne_zero n ht
+    · exfalso; rw [MulZeroClass.mul_zero] at ht; exact PNat.ne_zero n ht
     -- Now we have ht : ↑n = 2 * (t + 1).
     let t_succ : ℕ+ := ⟨t + 1, t.succ_pos⟩
     obtain ⟨pm, hpm⟩ := hpk t_succ

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

@@ -38,7 +38,7 @@ theorem arith_lemma (k n : ℕ) : 0 < 2 * n + 2 ^ k.succ :=
   calc
     0 < 2 := zero_lt_two
     _ = 2 ^ 1 := (pow_one 2).symm
-    _ ≤ 2 ^ k.succ := (Nat.pow_le_pow_of_le_right zero_lt_two (Nat.le_add_left 1 k))
+    _ ≤ 2 ^ k.succ := (Nat.pow_le_pow_right zero_lt_two (Nat.le_add_left 1 k))
     _ ≤ 2 * n + 2 ^ k.succ := Nat.le_add_left _ _
 #align imo2013_q1.arith_lemma Imo2013Q1.arith_lemma
 

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

@@ -3,11 +3,11 @@ Copyright (c) 2021 David Renshaw. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Renshaw
 -/
-import Mathbin.Data.Pnat.Basic
-import Mathbin.Data.Nat.Parity
-import Mathbin.Algebra.BigOperators.Pi
-import Mathbin.Tactic.Ring
-import Mathbin.Tactic.FieldSimp
+import Data.Pnat.Basic
+import Data.Nat.Parity
+import Algebra.BigOperators.Pi
+import Tactic.Ring
+import Tactic.FieldSimp
 
 #align_import imo.imo2013_q1 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
 

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

@@ -2,11 +2,6 @@
 Copyright (c) 2021 David Renshaw. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Renshaw
-
-! This file was ported from Lean 3 source module imo.imo2013_q1
-! 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.Pnat.Basic
 import Mathbin.Data.Nat.Parity
@@ -14,6 +9,8 @@ import Mathbin.Algebra.BigOperators.Pi
 import Mathbin.Tactic.Ring
 import Mathbin.Tactic.FieldSimp
 
+#align_import imo.imo2013_q1 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
+
 /-!
 # IMO 2013 Q1
 

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: David Renshaw
 
 ! This file was ported from Lean 3 source module imo.imo2013_q1
-! 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.
 -/
@@ -17,6 +17,9 @@ import Mathbin.Tactic.FieldSimp
 /-!
 # IMO 2013 Q1
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 Prove that for any pair of positive integers k and n, there exist k positive integers
 m₁, m₂, ..., mₖ (not necessarily different) such that
 

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

@@ -43,8 +43,8 @@ theorem arith_lemma (k n : ℕ) : 0 < 2 * n + 2 ^ k.succ :=
 #align imo2013_q1.arith_lemma Imo2013Q1.arith_lemma
 
 theorem prod_lemma (m : ℕ → ℕ+) (k : ℕ) (nm : ℕ+) :
-    (∏ i : ℕ in Finset.range k, (1 : ℚ) + 1 / ↑(if i < k then m i else nm)) =
-      ∏ i : ℕ in Finset.range k, 1 + 1 / m i :=
+    ∏ i : ℕ in Finset.range k, ((1 : ℚ) + 1 / ↑(if i < k then m i else nm)) =
+      ∏ i : ℕ in Finset.range k, (1 + 1 / m i) :=
   by
   suffices : ∀ i, i ∈ Finset.range k → (1 : ℚ) + 1 / ↑(if i < k then m i else nm) = 1 + 1 / m i
   exact Finset.prod_congr rfl this
@@ -57,7 +57,7 @@ end imo2013_q1
 open imo2013_q1
 
 theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
-    ∃ m : ℕ → ℕ+, (1 : ℚ) + (2 ^ k - 1) / n = ∏ i in Finset.range k, 1 + 1 / m i :=
+    ∃ m : ℕ → ℕ+, (1 : ℚ) + (2 ^ k - 1) / n = ∏ i in Finset.range k, (1 + 1 / m i) :=
   by
   revert n
   induction' k with pk hpk
@@ -87,9 +87,9 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
         field_simp [t.cast_add_one_ne_zero]
         ring
       _ = (1 + 1 / (2 * t + 2 ^ pk.succ)) * (1 + (2 ^ pk - 1) / t_succ) := by norm_cast
-      _ = (∏ i in Finset.range pk, 1 + 1 / m i) * (1 + 1 / m pk) := by
+      _ = (∏ i in Finset.range pk, (1 + 1 / m i)) * (1 + 1 / m pk) := by
         rw [prod_lemma, hpm, ← hmpk, mul_comm]
-      _ = ∏ i in Finset.range pk.succ, 1 + 1 / m i := by rw [← Finset.prod_range_succ _ pk]
+      _ = ∏ i in Finset.range pk.succ, (1 + 1 / m i) := by rw [← Finset.prod_range_succ _ pk]
   · -- odd case
     let t_succ : ℕ+ := ⟨t + 1, t.succ_pos⟩
     obtain ⟨pm, hpm⟩ := hpk t_succ
@@ -106,8 +106,8 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
         field_simp [t.cast_add_one_ne_zero]
         ring
       _ = (1 + 1 / (2 * t + 1)) * (1 + (2 ^ pk - 1) / t_succ) := by norm_cast
-      _ = (∏ i in Finset.range pk, 1 + 1 / m i) * (1 + 1 / ↑(m pk)) := by
+      _ = (∏ i in Finset.range pk, (1 + 1 / m i)) * (1 + 1 / ↑(m pk)) := by
         rw [prod_lemma, hpm, ← hmpk, mul_comm]
-      _ = ∏ i in Finset.range pk.succ, 1 + 1 / m i := by rw [← Finset.prod_range_succ _ pk]
+      _ = ∏ i in Finset.range pk.succ, (1 + 1 / m i) := by rw [← Finset.prod_range_succ _ pk]
 #align imo2013_q1 imo2013_q1
 

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

@@ -40,7 +40,6 @@ theorem arith_lemma (k n : ℕ) : 0 < 2 * n + 2 ^ k.succ :=
     _ = 2 ^ 1 := (pow_one 2).symm
     _ ≤ 2 ^ k.succ := (Nat.pow_le_pow_of_le_right zero_lt_two (Nat.le_add_left 1 k))
     _ ≤ 2 * n + 2 ^ k.succ := Nat.le_add_left _ _
-    
 #align imo2013_q1.arith_lemma Imo2013Q1.arith_lemma
 
 theorem prod_lemma (m : ℕ → ℕ+) (k : ℕ) (nm : ℕ+) :
@@ -91,7 +90,6 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
       _ = (∏ i in Finset.range pk, 1 + 1 / m i) * (1 + 1 / m pk) := by
         rw [prod_lemma, hpm, ← hmpk, mul_comm]
       _ = ∏ i in Finset.range pk.succ, 1 + 1 / m i := by rw [← Finset.prod_range_succ _ pk]
-      
   · -- odd case
     let t_succ : ℕ+ := ⟨t + 1, t.succ_pos⟩
     obtain ⟨pm, hpm⟩ := hpk t_succ
@@ -111,6 +109,5 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
       _ = (∏ i in Finset.range pk, 1 + 1 / m i) * (1 + 1 / ↑(m pk)) := by
         rw [prod_lemma, hpm, ← hmpk, mul_comm]
       _ = ∏ i in Finset.range pk.succ, 1 + 1 / m i := by rw [← Finset.prod_range_succ _ pk]
-      
 #align imo2013_q1 imo2013_q1
 

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

We change the following field in the definition of an additive commutative monoid:

 nsmul_succ : ∀ (n : ℕ) (x : G),
-  AddMonoid.nsmul (n + 1) x = x + AddMonoid.nsmul n x
+  AddMonoid.nsmul (n + 1) x = AddMonoid.nsmul n x + x

where the latter is more natural

We adjust the definitions of ^ in monoids, groups, etc. Originally there was a warning comment about why this natural order was preferred

use x * npowRec n x and not npowRec n x * x in the definition to make sure that definitional unfolding of npowRec is blocked, to avoid deep recursion issues.

but it seems to no longer apply.

Remarks on the PR :

• pow_succ and pow_succ' have switched their meanings.
• Most of the time, the proofs were adjusted by priming/unpriming one lemma, or exchanging left and right; a few proofs were more complicated to adjust.
• In particular, [Mathlib/NumberTheory/RamificationInertia.lean] used Ideal.IsPrime.mul_mem_pow which is defined in [Mathlib/RingTheory/DedekindDomain/Ideal.lean]. Changing the order of operation forced me to add the symmetric lemma Ideal.IsPrime.mem_pow_mul.
• the docstring for Cauchy condensation test in [Mathlib/Analysis/PSeries.lean] was mathematically incorrect, I added the mention that the function is antitone.

@@ -70,15 +70,13 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
       have : m pk = ⟨2 * t + 2 ^ pk.succ, _⟩ := if_neg (irrefl pk); simp [this]
     calc
       ((1 : ℚ) + (2 ^ pk.succ - 1) / (n : ℚ) : ℚ)= 1 + (2 * 2 ^ pk - 1) / (2 * (t + 1) : ℕ) := by
-        rw [ht, pow_succ]
+        rw [ht, pow_succ']
       _ = (1 + 1 / (2 * t + 2 * 2 ^ pk)) * (1 + (2 ^ pk - 1) / (↑t + 1)) := by
         field_simp
         ring
       _ = (1 + 1 / (2 * t + 2 ^ pk.succ)) * (1 + (2 ^ pk - 1) / t_succ) := by
         -- Porting note: used to work with `norm_cast`
-        simp only [t_succ, PNat.mk_coe, Nat.cast_add, Nat.cast_one, mul_eq_mul_right_iff]
-        left
-        rfl
+        simp only [t_succ, PNat.mk_coe, Nat.cast_add, Nat.cast_one, mul_eq_mul_right_iff, pow_succ']
       _ = (∏ i in Finset.range pk, (1 + 1 / (m i : ℚ))) * (1 + 1 / m pk) := by
         rw [prod_lemma, hpm, ← hmpk, mul_comm]
       _ = ∏ i in Finset.range pk.succ, (1 + 1 / (m i : ℚ)) := by rw [← Finset.prod_range_succ _ pk]
@@ -92,7 +90,7 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
       simp [this]
     calc
       ((1 : ℚ) + (2 ^ pk.succ - 1) / ↑n : ℚ) = 1 + (2 * 2 ^ pk - 1) / (2 * t + 1 : ℕ) := by
-        rw [ht, pow_succ]
+        rw [ht, pow_succ']
       _ = (1 + 1 / (2 * t + 1)) * (1 + (2 ^ pk - 1) / (t + 1)) := by
         field_simp
         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".

@@ -32,7 +32,7 @@ open scoped BigOperators
 
 namespace Imo2013Q1
 
--- porting note: simplified proof using `positivity`
+-- Porting note: simplified proof using `positivity`
 theorem arith_lemma (k n : ℕ) : 0 < 2 * n + 2 ^ k.succ := by positivity
 #align imo2013_q1.arith_lemma Imo2013Q1.arith_lemma
 
@@ -75,7 +75,7 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
         field_simp
         ring
       _ = (1 + 1 / (2 * t + 2 ^ pk.succ)) * (1 + (2 ^ pk - 1) / t_succ) := by
-        -- porting note: used to work with `norm_cast`
+        -- Porting note: used to work with `norm_cast`
         simp only [t_succ, PNat.mk_coe, Nat.cast_add, Nat.cast_one, mul_eq_mul_right_iff]
         left
         rfl

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

@@ -76,7 +76,7 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
         ring
       _ = (1 + 1 / (2 * t + 2 ^ pk.succ)) * (1 + (2 ^ pk - 1) / t_succ) := by
         -- porting note: used to work with `norm_cast`
-        simp only [PNat.mk_coe, Nat.cast_add, Nat.cast_one, mul_eq_mul_right_iff]
+        simp only [t_succ, PNat.mk_coe, Nat.cast_add, Nat.cast_one, mul_eq_mul_right_iff]
         left
         rfl
       _ = (∏ i in Finset.range pk, (1 + 1 / (m i : ℚ))) * (1 + 1 / m pk) := by

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>

@@ -39,8 +39,8 @@ theorem arith_lemma (k n : ℕ) : 0 < 2 * n + 2 ^ k.succ := by positivity
 theorem prod_lemma (m : ℕ → ℕ+) (k : ℕ) (nm : ℕ+) :
     ∏ i : ℕ in Finset.range k, ((1 : ℚ) + 1 / ↑(if i < k then m i else nm)) =
       ∏ i : ℕ in Finset.range k, (1 + 1 / (m i : ℚ)) := by
-  suffices : ∀ i, i ∈ Finset.range k → (1 : ℚ) + 1 / ↑(if i < k then m i else nm) = 1 + 1 / m i
-  exact Finset.prod_congr rfl this
+  suffices ∀ i, i ∈ Finset.range k → (1 : ℚ) + 1 / ↑(if i < k then m i else nm) = 1 + 1 / m i from
+    Finset.prod_congr rfl this
   intro i hi
   simp [Finset.mem_range.mp hi]
 #align imo2013_q1.prod_lemma Imo2013Q1.prod_lemma

Some of these are already transitively imported, others aren't used at all (but not handled by noshake in #9772).

Mostly I wanted to avoid needing all of algebra imported (but unused!) in FilteredColimitCommutesFiniteLimit; there are now some assert_not_exists to preserve this.

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

@@ -8,6 +8,7 @@ import Mathlib.Data.Nat.Parity
 import Mathlib.Algebra.BigOperators.Pi
 import Mathlib.Tactic.Ring
 import Mathlib.Tactic.FieldSimp
+import Mathlib.Tactic.Positivity.Basic
 
 #align_import imo.imo2013_q1 from "leanprover-community/mathlib"@"308826471968962c6b59c7ff82a22757386603e3"
 

The main reasons is that having h : 0 < denom in the context should suffice for field_simp to do its job, without the need to manually pass h.ne or similar.

Quite a few have := … ≠ 0 could be dropped, and some field_simp calls no longer need explicit arguments; this is promising.

This does break some proofs where field_simp was not used as a closing tactic, and it now shuffles terms around a bit different. These were fixed. Using field_simp in the middle of a proof seems rather fragile anyways.

As a drive-by contribution, positivity now knows about π > 0.

fixes: #4835

Co-authored-by: Matthew Ballard <matt@mrb.email>

@@ -67,12 +67,11 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
     use m
     have hmpk : (m pk : ℚ) = 2 * t + 2 ^ pk.succ := by
       have : m pk = ⟨2 * t + 2 ^ pk.succ, _⟩ := if_neg (irrefl pk); simp [this]
-    have denom_ne_zero : (2 * (t : ℚ) + 2 * 2 ^ pk) ≠ 0 := by positivity
     calc
       ((1 : ℚ) + (2 ^ pk.succ - 1) / (n : ℚ) : ℚ)= 1 + (2 * 2 ^ pk - 1) / (2 * (t + 1) : ℕ) := by
         rw [ht, pow_succ]
       _ = (1 + 1 / (2 * t + 2 * 2 ^ pk)) * (1 + (2 ^ pk - 1) / (↑t + 1)) := by
-        field_simp [t.cast_add_one_ne_zero]
+        field_simp
         ring
       _ = (1 + 1 / (2 * t + 2 ^ pk.succ)) * (1 + (2 ^ pk - 1) / t_succ) := by
         -- porting note: used to work with `norm_cast`
@@ -90,12 +89,11 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
     have hmpk : (m pk : ℚ) = 2 * t + 1 := by
       have : m pk = ⟨2 * t + 1, _⟩ := if_neg (irrefl pk)
       simp [this]
-    have denom_ne_zero : 2 * (t : ℚ) + 1 ≠ 0 := by norm_cast; apply (2 * t).succ_ne_zero
     calc
       ((1 : ℚ) + (2 ^ pk.succ - 1) / ↑n : ℚ) = 1 + (2 * 2 ^ pk - 1) / (2 * t + 1 : ℕ) := by
         rw [ht, pow_succ]
       _ = (1 + 1 / (2 * t + 1)) * (1 + (2 ^ pk - 1) / (t + 1)) := by
-        field_simp [t.cast_add_one_ne_zero]
+        field_simp
         ring
       _ = (1 + 1 / (2 * t + 1)) * (1 + (2 ^ pk - 1) / t_succ) := by norm_cast
       _ = (∏ i in Finset.range pk, (1 + 1 / (m i : ℚ))) * (1 + 1 / ↑(m pk)) := by

• 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) 2021 David Renshaw. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Renshaw
-
-! This file was ported from Lean 3 source module imo.imo2013_q1
-! 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.PNat.Basic
 import Mathlib.Data.Nat.Parity
@@ -14,6 +9,8 @@ import Mathlib.Algebra.BigOperators.Pi
 import Mathlib.Tactic.Ring
 import Mathlib.Tactic.FieldSimp
 
+#align_import imo.imo2013_q1 from "leanprover-community/mathlib"@"308826471968962c6b59c7ff82a22757386603e3"
+
 /-!
 # IMO 2013 Q1
 

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.

@@ -62,7 +62,7 @@ theorem imo2013_q1 (n : ℕ+) (k : ℕ) :
     rw [← two_mul] at ht
     cases' t with t
     -- Eliminate the zero case to simplify later calculations.
-    · exfalso; rw [Nat.mul_zero] at ht ; exact PNat.ne_zero n ht
+    · exfalso; rw [Nat.mul_zero] at ht; exact PNat.ne_zero n ht
     -- Now we have ht : ↑n = 2 * (t + 1).
     let t_succ : ℕ+ := ⟨t + 1, t.succ_pos⟩
     obtain ⟨pm, hpm⟩ := hpk t_succ