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

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn
 -/
 import Tactic.IntervalCases
-import Algebra.BigOperators.Order
+import Algebra.Order.BigOperators.Group.Finset
 import Data.Nat.Multiplicity
 
 #align_import imo.imo2019_q4 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"

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

@@ -60,7 +60,7 @@ theorem upper_bound {k n : ℕ} (hk : k > 0) (h : (k ! : ℤ) = ∏ i in range n
     · intros; apply sub_le_self; apply pow_nonneg; norm_num
   suffices 2 ^ (n * n) < (n * (n - 1) / 2)!
     by
-    rw [prod_const, card_range, ← pow_mul]; rw [← Int.ofNat_lt] at this 
+    rw [prod_const, card_range, ← pow_mul]; rw [← Int.ofNat_lt] at this
     clear h; convert this.trans _; norm_cast; rwa [Int.ofNat_lt, factorial_lt]
     refine' Nat.div_pos _ (by norm_num)
     refine' le_trans _ (mul_le_mul hn (pred_le_pred hn) (zero_le _) (zero_le _))
@@ -91,19 +91,19 @@ theorem imo2019_q4 {k n : ℕ} (hk : k > 0) (hn : n > 0) :
   constructor;
   swap
   ·
-    rintro (h | h) <;> simp [Prod.ext_iff] at h  <;> rcases h with ⟨rfl, rfl⟩ <;>
+    rintro (h | h) <;> simp [Prod.ext_iff] at h <;> rcases h with ⟨rfl, rfl⟩ <;>
       norm_num [prod_range_succ, succ_mul]
   intro h
   -- We know that n < 6.
   have := Imo2019Q4.upper_bound hk h
   interval_cases
   -- n = 1
-  · left; congr; norm_num at h ; rw [factorial_eq_one] at h ; apply antisymm h
+  · left; congr; norm_num at h; rw [factorial_eq_one] at h; apply antisymm h
     apply succ_le_of_lt hk
   -- n = 2
-  · right; congr; norm_num [prod_range_succ] at h ; norm_cast at h ; rw [← factorial_inj]
+  · right; congr; norm_num [prod_range_succ] at h; norm_cast at h; rw [← factorial_inj]
     exact h; rw [h]; norm_num
-  all_goals exfalso; norm_num [prod_range_succ] at h ; norm_cast at h 
+  all_goals exfalso; norm_num [prod_range_succ] at h; norm_cast at h
   -- n = 3
   · refine' monotone_factorial.ne_of_lt_of_lt_nat 5 _ _ _ h <;> norm_num
   -- n = 4

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

@@ -56,7 +56,7 @@ theorem upper_bound {k n : ℕ} (hk : k > 0) (h : (k ! : ℤ) = ∏ i in range n
   suffices (∏ i in range n, 2 ^ n : ℤ) < ↑k !
     by
     apply lt_of_le_of_lt _ this; apply prod_le_prod
-    · intros; rw [sub_nonneg]; apply pow_le_pow; norm_num; apply le_of_lt; rwa [← mem_range]
+    · intros; rw [sub_nonneg]; apply pow_le_pow_right; norm_num; apply le_of_lt; rwa [← mem_range]
     · intros; apply sub_le_self; apply pow_nonneg; norm_num
   suffices 2 ^ (n * n) < (n * (n - 1) / 2)!
     by
@@ -76,7 +76,7 @@ theorem upper_bound {k n : ℕ} (hk : k > 0) (h : (k ! : ℤ) = ∏ i in range n
   rw [triangle_succ]; apply lt_of_lt_of_le _ factorial_mul_pow_le_factorial
   refine'
     lt_of_le_of_lt _
-      (mul_lt_mul ih (Nat.pow_le_pow_of_le_left this _) (pow_pos (by norm_num) _) (zero_le _))
+      (mul_lt_mul ih (Nat.pow_le_pow_left this _) (pow_pos (by norm_num) _) (zero_le _))
   rw [← pow_mul, ← pow_add]; apply pow_le_pow_of_le_right; norm_num
   rw [add_mul 2 2]
   convert add_le_add_left (add_le_add_left h5 (2 * n')) (n' * n') using 1; ring

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

@@ -3,9 +3,9 @@ Copyright (c) 2020 Floris van Doorn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn
 -/
-import Mathbin.Tactic.IntervalCases
-import Mathbin.Algebra.BigOperators.Order
-import Mathbin.Data.Nat.Multiplicity
+import Tactic.IntervalCases
+import Algebra.BigOperators.Order
+import Data.Nat.Multiplicity
 
 #align_import imo.imo2019_q4 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
 

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

@@ -2,16 +2,13 @@
 Copyright (c) 2020 Floris van Doorn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn
-
-! This file was ported from Lean 3 source module imo.imo2019_q4
-! 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.Tactic.IntervalCases
 import Mathbin.Algebra.BigOperators.Order
 import Mathbin.Data.Nat.Multiplicity
 
+#align_import imo.imo2019_q4 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
+
 /-!
 # IMO 2019 Q4
 

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: Floris van Doorn
 
 ! This file was ported from Lean 3 source module imo.imo2019_q4
-! 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.
 -/
@@ -15,6 +15,9 @@ import Mathbin.Data.Nat.Multiplicity
 /-!
 # IMO 2019 Q4
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 Find all pairs `(k, n)` of positive integers such that
 ```
   k! = (2 ^ n - 1)(2 ^ n - 2)(2 ^ n - 4)···(2 ^ n - 2 ^ (n - 1))

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

@@ -37,7 +37,7 @@ open Nat hiding zero_le Prime
 
 namespace imo2019_q4
 
-theorem upper_bound {k n : ℕ} (hk : k > 0) (h : (k ! : ℤ) = ∏ i in range n, 2 ^ n - 2 ^ i) :
+theorem upper_bound {k n : ℕ} (hk : k > 0) (h : (k ! : ℤ) = ∏ i in range n, (2 ^ n - 2 ^ i)) :
     n < 6 := by
   have prime_2 : Prime (2 : ℤ) := prime_iff_prime_int.mp prime_two
   have h2 : n * (n - 1) / 2 < k :=
@@ -85,7 +85,7 @@ theorem upper_bound {k n : ℕ} (hk : k > 0) (h : (k ! : ℤ) = ∏ i in range n
 end imo2019_q4
 
 theorem imo2019_q4 {k n : ℕ} (hk : k > 0) (hn : n > 0) :
-    ((k ! : ℤ) = ∏ i in range n, 2 ^ n - 2 ^ i) ↔ (k, n) = (1, 1) ∨ (k, n) = (3, 2) :=
+    (k ! : ℤ) = ∏ i in range n, (2 ^ n - 2 ^ i) ↔ (k, n) = (1, 1) ∨ (k, n) = (3, 2) :=
   by
   -- The implication `←` holds.
   constructor;

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

This is less exhaustive than its sibling #11486 because edge cases are harder to classify. No fundamental difficulty, just me being a bit fast and lazy.

Reduce the diff of #11203

@@ -40,7 +40,7 @@ theorem upper_bound {k n : ℕ} (hk : k > 0)
   have h2 : ∑ i in range n, i < k := by
     suffices multiplicity 2 (k ! : ℤ) = ↑(∑ i in range n, i : ℕ) by
       rw [← PartENat.coe_lt_coe, ← this]; change multiplicity ((2 : ℕ) : ℤ) _ < _
-      simp_rw [Int.coe_nat_multiplicity, multiplicity_two_factorial_lt hk.lt.ne.symm]
+      simp_rw [Int.natCast_multiplicity, multiplicity_two_factorial_lt hk.lt.ne.symm]
     rw [h, multiplicity.Finset.prod Int.prime_two, Nat.cast_sum]
     apply sum_congr rfl; intro i hi
     rw [multiplicity_sub_of_gt, multiplicity_pow_self_of_prime Int.prime_two]

Make use of Nat-specific lemmas from Std rather than the general ones provided by mathlib.

The ultimate goal here is to carve out Data, Algebra and Order sublibraries.

@@ -3,9 +3,9 @@ Copyright (c) 2020 Floris van Doorn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn
 -/
-import Mathlib.Tactic.IntervalCases
-import Mathlib.Algebra.BigOperators.Order
+import Mathlib.Data.Nat.Factorial.BigOperators
 import Mathlib.Data.Nat.Multiplicity
+import Mathlib.Tactic.IntervalCases
 import Mathlib.Tactic.GCongr
 
 #align_import imo.imo2019_q4 from "leanprover-community/mathlib"@"308826471968962c6b59c7ff82a22757386603e3"

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>

@@ -37,8 +37,8 @@ namespace Imo2019Q4
 
 theorem upper_bound {k n : ℕ} (hk : k > 0)
     (h : (k ! : ℤ) = ∏ i in range n, ((2:ℤ) ^ n - (2:ℤ) ^ i)) : n < 6 := by
-  have h2 : ∑ i in range n, i < k
-  · suffices multiplicity 2 (k ! : ℤ) = ↑(∑ i in range n, i : ℕ) by
+  have h2 : ∑ i in range n, i < k := by
+    suffices multiplicity 2 (k ! : ℤ) = ↑(∑ i in range n, i : ℕ) by
       rw [← PartENat.coe_lt_coe, ← this]; change multiplicity ((2 : ℕ) : ℤ) _ < _
       simp_rw [Int.coe_nat_multiplicity, multiplicity_two_factorial_lt hk.lt.ne.symm]
     rw [h, multiplicity.Finset.prod Int.prime_two, Nat.cast_sum]
@@ -65,8 +65,8 @@ theorem upper_bound {k n : ℕ} (hk : k > 0)
   induction' n, hn using Nat.le_induction with n' hn' IH
   · decide
   let A := ∑ i in range n', i
-  have le_sum : ∑ i in range 6, i ≤ A
-  · apply sum_le_sum_of_subset
+  have le_sum : ∑ i in range 6, i ≤ A := by
+    apply sum_le_sum_of_subset
     simpa using hn'
   calc 2 ^ ((n' + 1) * (n' + 1))
       ≤ 2 ^ (n' * n' + 4 * n') := by gcongr <;> linarith

• Also remove some unimportant porting notes in Order.Concept.

@@ -91,11 +91,10 @@ theorem imo2019_q4 {k n : ℕ} (hk : k > 0) (hn : n > 0) :
   have := Imo2019Q4.upper_bound hk h
   interval_cases n
   -- n = 1
-  · left; congr; norm_num at h; rw [factorial_eq_one] at h; apply antisymm h
-    apply succ_le_of_lt hk
+  · norm_num at h; simp [le_antisymm h (succ_le_of_lt hk)]
   -- n = 2
-  · right; congr; norm_num [prod_range_succ] at h; norm_cast at h; rw [← factorial_inj]
-    exact h; rw [h]; norm_num
+  · right; congr; norm_num [prod_range_succ] at h; norm_cast at h; rwa [← factorial_inj']
+    norm_num
   all_goals exfalso; norm_num [prod_range_succ] at h; norm_cast at h
   -- n = 3
   · refine' monotone_factorial.ne_of_lt_of_lt_nat 5 _ _ _ h <;> decide

PR contents

This is the supremum of

• #8284
• #8056
• #8023
• #8332
• #8226 (already approved)
• #7834 (already approved)

along with some minor fixes from failures on nightly-testing as Mathlib master is merged into it.

Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.

I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0 branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.

Lean PRs involved in this bump

In particular this includes adjustments for the Lean PRs

• leanprover/lean4#2778
• leanprover/lean4#2790
• leanprover/lean4#2783
• leanprover/lean4#2825
• leanprover/lean4#2722

leanprover/lean4#2778

We can get rid of all the

local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)

macros across Mathlib (and in any projects that want to write natural number powers of reals).

leanprover/lean4#2722

Changes the default behaviour of simp to (config := {decide := false}). This makes simp (and consequentially norm_num) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp or norm_num to decide or rfl, or adding (config := {decide := true}).

leanprover/lean4#2783

This changed the behaviour of simp so that simp [f] will only unfold "fully applied" occurrences of f. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true }). We may in future add a syntax for this, e.g. simp [!f]; please provide feedback! In the meantime, we have made the following changes:

• switching to using explicit lemmas that have the intended level of application
• (config := { unfoldPartialApp := true }) in some places, to recover the old behaviour
• Using @[eqns] to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp and Function.flip.

This change in Lean may require further changes down the line (e.g. adding the !f syntax, and/or upstreaming the special treatment for Function.comp and Function.flip, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>

@@ -29,8 +29,6 @@ individually.
 
 open scoped Nat BigOperators
 
-local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue lean4#2220
-
 open Nat hiding zero_le Prime
 
 open Finset multiplicity
@@ -65,7 +63,7 @@ theorem upper_bound {k n : ℕ} (hk : k > 0)
     _ ≤ k ! := by gcongr
   clear h h2
   induction' n, hn using Nat.le_induction with n' hn' IH
-  · norm_num
+  · decide
   let A := ∑ i in range n', i
   have le_sum : ∑ i in range 6, i ≤ A
   · apply sum_le_sum_of_subset
@@ -87,8 +85,7 @@ theorem imo2019_q4 {k n : ℕ} (hk : k > 0) (hn : n > 0) :
   -- The implication `←` holds.
   constructor
   swap
-  · rintro (h | h) <;> simp [Prod.ext_iff] at h <;> rcases h with ⟨rfl, rfl⟩ <;>
-    norm_num [prod_range_succ, succ_mul]
+  · rintro (h | h) <;> simp [Prod.ext_iff] at h <;> rcases h with ⟨rfl, rfl⟩ <;> decide
   intro h
   -- We know that n < 6.
   have := Imo2019Q4.upper_bound hk h
@@ -101,9 +98,9 @@ theorem imo2019_q4 {k n : ℕ} (hk : k > 0) (hn : n > 0) :
     exact h; rw [h]; norm_num
   all_goals exfalso; norm_num [prod_range_succ] at h; norm_cast at h
   -- n = 3
-  · refine' monotone_factorial.ne_of_lt_of_lt_nat 5 _ _ _ h <;> norm_num
+  · refine' monotone_factorial.ne_of_lt_of_lt_nat 5 _ _ _ h <;> decide
   -- n = 4
-  · refine' monotone_factorial.ne_of_lt_of_lt_nat 7 _ _ _ h <;> norm_num
+  · refine' monotone_factorial.ne_of_lt_of_lt_nat 7 _ _ _ h <;> decide
   -- n = 5
-  · refine' monotone_factorial.ne_of_lt_of_lt_nat 10 _ _ _ h <;> norm_num
+  · refine' monotone_factorial.ne_of_lt_of_lt_nat 10 _ _ _ h <;> decide
 #align imo2019_q4 imo2019_q4

norm_num was passing the wrong syntax node to elabSimpArgs when elaborating, which essentially had the effect of ignoring all arguments it was passed, i.e. norm_num [add_comm] would not try to commute addition in the simp step. The fix itself is very simple (though not obvious to debug!), probably using TSyntax more would help avoid such issues in future.

Due to this bug many norm_num [blah] became rw [blah]; norm_num or similar, sometimes with porting notes, sometimes not, we fix these porting notes and other regressions during the port also.

Interestingly cancel_denoms uses norm_num [<- mul_assoc] internally, so cancel_denoms also got stronger with this change.

@@ -97,9 +97,9 @@ theorem imo2019_q4 {k n : ℕ} (hk : k > 0) (hn : n > 0) :
   · left; congr; norm_num at h; rw [factorial_eq_one] at h; apply antisymm h
     apply succ_le_of_lt hk
   -- n = 2
-  · right; congr; rw [prod_range_succ] at h; norm_num at h; norm_cast at h; rw [← factorial_inj]
+  · right; congr; norm_num [prod_range_succ] at h; norm_cast at h; rw [← factorial_inj]
     exact h; rw [h]; norm_num
-  all_goals exfalso; (repeat rw [prod_range_succ] at h); norm_num at h; norm_cast at h
+  all_goals exfalso; norm_num [prod_range_succ] at h; norm_cast at h
   -- n = 3
   · refine' monotone_factorial.ne_of_lt_of_lt_nat 5 _ _ _ h <;> norm_num
   -- n = 4

@@ -29,7 +29,7 @@ individually.
 
 open scoped Nat BigOperators
 
-local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue #2220
+local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue lean4#2220
 
 open Nat hiding zero_le Prime
 

• 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) 2020 Floris van Doorn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn
-
-! This file was ported from Lean 3 source module imo.imo2019_q4
-! 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.Tactic.IntervalCases
 import Mathlib.Algebra.BigOperators.Order
 import Mathlib.Data.Nat.Multiplicity
 import Mathlib.Tactic.GCongr
 
+#align_import imo.imo2019_q4 from "leanprover-community/mathlib"@"308826471968962c6b59c7ff82a22757386603e3"
+
 /-!
 # IMO 2019 Q4
 

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

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

@@ -90,7 +90,7 @@ theorem imo2019_q4 {k n : ℕ} (hk : k > 0) (hn : n > 0) :
   -- The implication `←` holds.
   constructor
   swap
-  · rintro (h | h) <;> simp [Prod.ext_iff] at h  <;> rcases h with ⟨rfl, rfl⟩ <;>
+  · rintro (h | h) <;> simp [Prod.ext_iff] at h <;> rcases h with ⟨rfl, rfl⟩ <;>
     norm_num [prod_range_succ, succ_mul]
   intro h
   -- We know that n < 6.

• Also remove most superfluous parentheses around big operators (∑, ∏ and variants).
• roughly the used regex: ([^a-zA-Zα-ωΑ-Ω'𝓝ℳ₀𝕂ₛ)]) \(([∑∏][^()∑∏]*,[^()∑∏:]*)\) ([⊂⊆=<≤]) replaced by $1 $2 $3

@@ -42,7 +42,7 @@ namespace Imo2019Q4
 
 theorem upper_bound {k n : ℕ} (hk : k > 0)
     (h : (k ! : ℤ) = ∏ i in range n, ((2:ℤ) ^ n - (2:ℤ) ^ i)) : n < 6 := by
-  have h2 : (∑ i in range n, i) < k
+  have h2 : ∑ i in range n, i < k
   · suffices multiplicity 2 (k ! : ℤ) = ↑(∑ i in range n, i : ℕ) by
       rw [← PartENat.coe_lt_coe, ← this]; change multiplicity ((2 : ℕ) : ℤ) _ < _
       simp_rw [Int.coe_nat_multiplicity, multiplicity_two_factorial_lt hk.lt.ne.symm]

@@ -53,7 +53,7 @@ theorem upper_bound {k n : ℕ} (hk : k > 0)
       PartENat.coe_lt_coe, ← mem_range]
   rw [← not_le]; intro hn
   apply _root_.ne_of_gt _ h
-  calc ∏ i in range n, ((2:ℤ) ^ n - (2:ℤ) ^ i) ≤ ∏ i in range n, (2:ℤ) ^ n := ?_
+  calc ∏ i in range n, ((2:ℤ) ^ n - (2:ℤ) ^ i) ≤ ∏ __ in range n, (2:ℤ) ^ n := ?_
     _ < ↑ k ! := ?_
   · gcongr
     · intro i hi
@@ -63,7 +63,7 @@ theorem upper_bound {k n : ℕ} (hk : k > 0)
     · apply sub_le_self
       positivity
   norm_cast
-  calc ∏ i in range n, 2 ^ n = 2 ^ (n * n) := by rw [prod_const, card_range, ← pow_mul]
+  calc ∏ __ in range n, 2 ^ n = 2 ^ (n * n) := by rw [prod_const, card_range, ← pow_mul]
     _ < (∑ i in range n, i)! := ?_
     _ ≤ k ! := by gcongr
   clear h h2

Rewrite the IMO 2019 q4 solution to make the "implicit" calc blocks (lots of lt_of_le_of_lt) explicit, then automate some proofs.

This is not a golf in the sense of decreasing the number of lines (maybe it is if you take into account the number of lines like

intros; rw [sub_nonneg]; apply pow_le_pow; norm_num; apply le_of_lt; rwa [← mem_range]

in the original). So, if desired, I can make this an additional proof rather than a replacement to the existing proof.

@@ -11,6 +11,7 @@ Authors: Floris van Doorn
 import Mathlib.Tactic.IntervalCases
 import Mathlib.Algebra.BigOperators.Order
 import Mathlib.Data.Nat.Multiplicity
+import Mathlib.Tactic.GCongr
 
 /-!
 # IMO 2019 Q4
@@ -41,41 +42,45 @@ namespace Imo2019Q4
 
 theorem upper_bound {k n : ℕ} (hk : k > 0)
     (h : (k ! : ℤ) = ∏ i in range n, ((2:ℤ) ^ n - (2:ℤ) ^ i)) : n < 6 := by
-  have h2 : n * (n - 1) / 2 < k := by
-    suffices multiplicity 2 (k ! : ℤ) = (n * (n - 1) / 2 : ℕ) by
+  have h2 : (∑ i in range n, i) < k
+  · suffices multiplicity 2 (k ! : ℤ) = ↑(∑ i in range n, i : ℕ) by
       rw [← PartENat.coe_lt_coe, ← this]; change multiplicity ((2 : ℕ) : ℤ) _ < _
       simp_rw [Int.coe_nat_multiplicity, multiplicity_two_factorial_lt hk.lt.ne.symm]
-    rw [h, multiplicity.Finset.prod Int.prime_two, ← sum_range_id, Nat.cast_sum]
+    rw [h, multiplicity.Finset.prod Int.prime_two, Nat.cast_sum]
     apply sum_congr rfl; intro i hi
     rw [multiplicity_sub_of_gt, multiplicity_pow_self_of_prime Int.prime_two]
     rwa [multiplicity_pow_self_of_prime Int.prime_two, multiplicity_pow_self_of_prime Int.prime_two,
       PartENat.coe_lt_coe, ← mem_range]
   rw [← not_le]; intro hn
-  apply _root_.ne_of_lt _ h.symm
-  suffices (∏ i in range n, ↑2 ^ n : ℤ) < ↑k ! by
-    apply lt_of_le_of_lt _ this; apply prod_le_prod
-    · intros; rw [sub_nonneg]; apply pow_le_pow; norm_num; apply le_of_lt; rwa [← mem_range]
-    · intros; apply sub_le_self; apply pow_nonneg; norm_num
-  suffices 2 ^ (n * n) < (n * (n - 1) / 2)! by
-    rw [prod_const, card_range, ← pow_mul]; rw [← Int.ofNat_lt] at this
-    clear h; convert this.trans _ using 1; norm_cast; rwa [Int.ofNat_lt, factorial_lt]
-    refine' Nat.div_pos _ (by norm_num)
-    refine' le_trans _ (mul_le_mul hn (pred_le_pred hn) (zero_le _) (zero_le _))
-    norm_num
-  refine' le_induction _ _ n hn; · norm_num
-  intro n' hn' ih
-  have h5 : 1 ≤ 2 * n' := by linarith
-  have : 2 ^ (2 + 2) ≤ (n' * (n' - 1) / 2).succ := by
-    change succ (6 * (6 - 1) / 2) ≤ _
-    apply succ_le_succ; apply Nat.div_le_div_right
-    exact mul_le_mul hn' (pred_le_pred hn') (zero_le _) (zero_le _)
-  rw [triangle_succ]; apply lt_of_lt_of_le _ factorial_mul_pow_le_factorial
-  refine'
-    lt_of_le_of_lt _
-      (mul_lt_mul ih (Nat.pow_le_pow_of_le_left this _) (pow_pos (by norm_num) _) (zero_le _))
-  rw [← pow_mul, ← pow_add]; apply pow_le_pow_of_le_right; norm_num
-  rw [add_mul 2 2]
-  convert add_le_add_left (add_le_add_left h5 (2 * n')) (n' * n') using 1; ring
+  apply _root_.ne_of_gt _ h
+  calc ∏ i in range n, ((2:ℤ) ^ n - (2:ℤ) ^ i) ≤ ∏ i in range n, (2:ℤ) ^ n := ?_
+    _ < ↑ k ! := ?_
+  · gcongr
+    · intro i hi
+      simp only [mem_range] at hi
+      have : (2:ℤ) ^ i ≤ (2:ℤ) ^ n := by gcongr; norm_num
+      linarith
+    · apply sub_le_self
+      positivity
+  norm_cast
+  calc ∏ i in range n, 2 ^ n = 2 ^ (n * n) := by rw [prod_const, card_range, ← pow_mul]
+    _ < (∑ i in range n, i)! := ?_
+    _ ≤ k ! := by gcongr
+  clear h h2
+  induction' n, hn using Nat.le_induction with n' hn' IH
+  · norm_num
+  let A := ∑ i in range n', i
+  have le_sum : ∑ i in range 6, i ≤ A
+  · apply sum_le_sum_of_subset
+    simpa using hn'
+  calc 2 ^ ((n' + 1) * (n' + 1))
+      ≤ 2 ^ (n' * n' + 4 * n') := by gcongr <;> linarith
+    _ = 2 ^ (n' * n') * (2 ^ 4) ^ n' := by rw [← pow_mul, ← pow_add]
+    _ < A ! * (2 ^ 4) ^ n' := by gcongr
+    _ = A ! * (15 + 1) ^ n' := rfl
+    _ ≤ A ! * (A + 1) ^ n' := by gcongr; exact le_sum
+    _ ≤ (A + n')! := factorial_mul_pow_le_factorial
+    _ = (∑ i in range (n' + 1), i)! := by rw [sum_range_succ]
 #align imo2019_q4.upper_bound Imo2019Q4.upper_bound
 
 end Imo2019Q4

@@ -41,15 +41,14 @@ namespace Imo2019Q4
 
 theorem upper_bound {k n : ℕ} (hk : k > 0)
     (h : (k ! : ℤ) = ∏ i in range n, ((2:ℤ) ^ n - (2:ℤ) ^ i)) : n < 6 := by
-  have prime_2 : Prime (2 : ℤ) := prime_iff_prime_int.mp prime_two
   have h2 : n * (n - 1) / 2 < k := by
     suffices multiplicity 2 (k ! : ℤ) = (n * (n - 1) / 2 : ℕ) by
       rw [← PartENat.coe_lt_coe, ← this]; change multiplicity ((2 : ℕ) : ℤ) _ < _
       simp_rw [Int.coe_nat_multiplicity, multiplicity_two_factorial_lt hk.lt.ne.symm]
-    rw [h, multiplicity.Finset.prod prime_2, ← sum_range_id, Nat.cast_sum]
+    rw [h, multiplicity.Finset.prod Int.prime_two, ← sum_range_id, Nat.cast_sum]
     apply sum_congr rfl; intro i hi
-    rw [multiplicity_sub_of_gt, multiplicity_pow_self_of_prime prime_2]
-    rwa [multiplicity_pow_self_of_prime prime_2, multiplicity_pow_self_of_prime prime_2,
+    rw [multiplicity_sub_of_gt, multiplicity_pow_self_of_prime Int.prime_two]
+    rwa [multiplicity_pow_self_of_prime Int.prime_two, multiplicity_pow_self_of_prime Int.prime_two,
       PartENat.coe_lt_coe, ← mem_range]
   rw [← not_le]; intro hn
   apply _root_.ne_of_lt _ h.symm