data.nat.choose.central
⟷
Mathlib.Data.Nat.Choose.Central
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.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,7 +3,7 @@ Copyright (c) 2021 Patrick Stevens. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Patrick Stevens, Thomas Browning
-/
-import Mathbin.Data.Nat.Choose.Basic
+import Data.Nat.Choose.Basic
import Mathbin.Tactic.Linarith.Default
#align_import data.nat.choose.central from "leanprover-community/mathlib"@"3e32bc908f617039c74c06ea9a897e30c30803c2"
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -158,7 +158,7 @@ theorem two_dvd_centralBinom_of_one_le {n : ℕ} (h : 0 < n) : 2 ∣ centralBino
`catalan n = n.central_binom / (n + 1)`. -/
theorem succ_dvd_centralBinom (n : ℕ) : n + 1 ∣ n.centralBinom :=
by
- have h_s : (n + 1).coprime (2 * n + 1) :=
+ have h_s : (n + 1).Coprime (2 * n + 1) :=
by
rw [two_mul, add_assoc, coprime_add_self_right, coprime_self_add_left]
exact coprime_one_left n
mathlib commit https://github.com/leanprover-community/mathlib/commit/63721b2c3eba6c325ecf8ae8cca27155a4f6306f
@@ -139,7 +139,7 @@ theorem four_pow_le_two_mul_self_mul_centralBinom :
#print Nat.two_dvd_centralBinom_succ /-
theorem two_dvd_centralBinom_succ (n : ℕ) : 2 ∣ centralBinom (n + 1) :=
by
- use (n + 1 + n).choose n
+ use(n + 1 + n).choose n
rw [central_binom_eq_two_mul_choose, two_mul, ← add_assoc, choose_succ_succ, choose_symm_add, ←
two_mul]
#align nat.two_dvd_central_binom_succ Nat.two_dvd_centralBinom_succ
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,15 +2,12 @@
Copyright (c) 2021 Patrick Stevens. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Patrick Stevens, Thomas Browning
-
-! This file was ported from Lean 3 source module data.nat.choose.central
-! leanprover-community/mathlib commit 3e32bc908f617039c74c06ea9a897e30c30803c2
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Data.Nat.Choose.Basic
import Mathbin.Tactic.Linarith.Default
+#align_import data.nat.choose.central from "leanprover-community/mathlib"@"3e32bc908f617039c74c06ea9a897e30c30803c2"
+
/-!
# Central binomial coefficients
mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0
@@ -73,7 +73,6 @@ theorem choose_le_centralBinom (r n : ℕ) : choose (2 * n) r ≤ centralBinom n
calc
(2 * n).choose r ≤ (2 * n).choose (2 * n / 2) := choose_le_middle r (2 * n)
_ = (2 * n).choose n := by rw [Nat.mul_div_cancel_left n zero_lt_two]
-
#align nat.choose_le_central_binom Nat.choose_le_centralBinom
-/
@@ -83,7 +82,6 @@ theorem two_le_centralBinom (n : ℕ) (n_pos : 0 < n) : 2 ≤ centralBinom n :=
2 ≤ 2 * n := le_mul_of_pos_right n_pos
_ = (2 * n).choose 1 := (choose_one_right (2 * n)).symm
_ ≤ centralBinom n := choose_le_centralBinom 1 n
-
#align nat.two_le_central_binom Nat.two_le_centralBinom
-/
@@ -100,7 +98,6 @@ theorem succ_mul_centralBinom_succ (n : ℕ) :
rw [two_mul n, add_assoc, Nat.add_sub_cancel_left]
_ = 2 * ((2 * n).choose n * (2 * n + 1)) := by rw [choose_mul_succ_eq]
_ = 2 * (2 * n + 1) * (2 * n).choose n := by rw [mul_assoc, mul_comm (2 * n + 1)]
-
#align nat.succ_mul_central_binom_succ Nat.succ_mul_centralBinom_succ
-/
@@ -121,7 +118,6 @@ theorem four_pow_lt_mul_centralBinom (n : ℕ) (n_big : 4 ≤ n) : 4 ^ n < n * c
(mul_lt_mul_left <| zero_lt_four' ℕ).mpr (IH n n.lt_succ_self (Nat.le_of_lt_succ hn))
_ ≤ 2 * (2 * n + 1) * central_binom n := by rw [← mul_assoc]; linarith
_ = (n + 1) * central_binom (n + 1) := (succ_mul_central_binom_succ n).symm
-
#align nat.four_pow_lt_mul_central_binom Nat.four_pow_lt_mul_centralBinom
-/
@@ -140,7 +136,6 @@ theorem four_pow_le_two_mul_self_mul_centralBinom :
calc
4 ^ n ≤ n * centralBinom n := (four_pow_lt_mul_centralBinom _ le_add_self).le
_ ≤ 2 * n * centralBinom n := by rw [mul_assoc]; refine' le_mul_of_pos_left zero_lt_two
-
#align nat.four_pow_le_two_mul_self_mul_central_binom Nat.four_pow_le_two_mul_self_mul_centralBinom
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -113,17 +113,13 @@ theorem four_pow_lt_mul_centralBinom (n : ℕ) (n_big : 4 ≤ n) : 4 ^ n < n * c
by
induction' n using Nat.strong_induction_on with n IH
rcases lt_trichotomy n 4 with (hn | rfl | hn)
- · clear IH
- decide!
+ · clear IH; decide!
· norm_num [central_binom, choose]
obtain ⟨n, rfl⟩ : ∃ m, n = m + 1 := Nat.exists_eq_succ_of_ne_zero (zero_lt_four.trans hn).ne'
calc
4 ^ (n + 1) < 4 * (n * central_binom n) :=
(mul_lt_mul_left <| zero_lt_four' ℕ).mpr (IH n n.lt_succ_self (Nat.le_of_lt_succ hn))
- _ ≤ 2 * (2 * n + 1) * central_binom n :=
- by
- rw [← mul_assoc]
- linarith
+ _ ≤ 2 * (2 * n + 1) * central_binom n := by rw [← mul_assoc]; linarith
_ = (n + 1) * central_binom (n + 1) := (succ_mul_central_binom_succ n).symm
#align nat.four_pow_lt_mul_central_binom Nat.four_pow_lt_mul_centralBinom
@@ -143,9 +139,7 @@ theorem four_pow_le_two_mul_self_mul_centralBinom :
| n@(m + 4), _ =>
calc
4 ^ n ≤ n * centralBinom n := (four_pow_lt_mul_centralBinom _ le_add_self).le
- _ ≤ 2 * n * centralBinom n := by
- rw [mul_assoc]
- refine' le_mul_of_pos_left zero_lt_two
+ _ ≤ 2 * n * centralBinom n := by rw [mul_assoc]; refine' le_mul_of_pos_left zero_lt_two
#align nat.four_pow_le_two_mul_self_mul_central_binom Nat.four_pow_le_two_mul_self_mul_centralBinom
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
@@ -40,7 +40,7 @@ theorem centralBinom_eq_two_mul_choose (n : ℕ) : centralBinom n = (2 * n).choo
#align nat.central_binom_eq_two_mul_choose Nat.centralBinom_eq_two_mul_choose
theorem centralBinom_pos (n : ℕ) : 0 < centralBinom n :=
- choose_pos (Nat.le_mul_of_pos_left zero_lt_two)
+ choose_pos (Nat.le_mul_of_pos_left _ zero_lt_two)
#align nat.central_binom_pos Nat.centralBinom_pos
theorem centralBinom_ne_zero (n : ℕ) : centralBinom n ≠ 0 :=
@@ -62,7 +62,7 @@ theorem choose_le_centralBinom (r n : ℕ) : choose (2 * n) r ≤ centralBinom n
theorem two_le_centralBinom (n : ℕ) (n_pos : 0 < n) : 2 ≤ centralBinom n :=
calc
- 2 ≤ 2 * n := le_mul_of_pos_right n_pos
+ 2 ≤ 2 * n := Nat.le_mul_of_pos_right _ n_pos
_ = (2 * n).choose 1 := (choose_one_right (2 * n)).symm
_ ≤ centralBinom n := choose_le_centralBinom 1 n
#align nat.two_le_central_binom Nat.two_le_centralBinom
@@ -112,7 +112,7 @@ theorem four_pow_le_two_mul_self_mul_centralBinom :
calc
4 ^ (n+4) ≤ (n+4) * centralBinom (n+4) := (four_pow_lt_mul_centralBinom _ le_add_self).le
_ ≤ 2 * (n+4) * centralBinom (n+4) := by
- rw [mul_assoc]; refine' le_mul_of_pos_left zero_lt_two
+ rw [mul_assoc]; refine' Nat.le_mul_of_pos_left _ zero_lt_two
#align nat.four_pow_le_two_mul_self_mul_central_binom Nat.four_pow_le_two_mul_self_mul_centralBinom
theorem two_dvd_centralBinom_succ (n : ℕ) : 2 ∣ centralBinom (n + 1) := by
$
with <|
(#9319)
See Zulip thread for the discussion.
@@ -92,7 +92,7 @@ theorem four_pow_lt_mul_centralBinom (n : ℕ) (n_big : 4 ≤ n) : 4 ^ n < n * c
· norm_num [centralBinom, choose]
obtain ⟨n, rfl⟩ : ∃ m, n = m + 1 := Nat.exists_eq_succ_of_ne_zero (Nat.not_eq_zero_of_lt hn)
calc
- 4 ^ (n + 1) < 4 * (n * centralBinom n) := lt_of_eq_of_lt pow_succ' $
+ 4 ^ (n + 1) < 4 * (n * centralBinom n) := lt_of_eq_of_lt pow_succ' <|
(mul_lt_mul_left <| zero_lt_four' ℕ).mpr (IH n n.lt_succ_self (Nat.le_of_lt_succ hn))
_ ≤ 2 * (2 * n + 1) * centralBinom n := by rw [← mul_assoc]; linarith
_ = (n + 1) * centralBinom (n + 1) := (succ_mul_centralBinom_succ n).symm
@@ -129,7 +129,7 @@ theorem two_dvd_centralBinom_of_one_le {n : ℕ} (h : 0 < n) : 2 ∣ centralBino
/-- A crucial lemma to ensure that Catalan numbers can be defined via their explicit formula
`catalan n = n.centralBinom / (n + 1)`. -/
theorem succ_dvd_centralBinom (n : ℕ) : n + 1 ∣ n.centralBinom := by
- have h_s : (n + 1).coprime (2 * n + 1) := by
+ have h_s : (n + 1).Coprime (2 * n + 1) := by
rw [two_mul, add_assoc, coprime_add_self_right, coprime_self_add_left]
exact coprime_one_left n
apply h_s.dvd_of_dvd_mul_left
@@ -129,7 +129,7 @@ theorem two_dvd_centralBinom_of_one_le {n : ℕ} (h : 0 < n) : 2 ∣ centralBino
/-- A crucial lemma to ensure that Catalan numbers can be defined via their explicit formula
`catalan n = n.centralBinom / (n + 1)`. -/
theorem succ_dvd_centralBinom (n : ℕ) : n + 1 ∣ n.centralBinom := by
- have h_s : (n + 1).Coprime (2 * n + 1) := by
+ have h_s : (n + 1).coprime (2 * n + 1) := by
rw [two_mul, add_assoc, coprime_add_self_right, coprime_self_add_left]
exact coprime_one_left n
apply h_s.dvd_of_dvd_mul_left
Some changes have already been review and delegated in #6910 and #7148.
The diff that needs looking at is https://github.com/leanprover-community/mathlib4/pull/7174/commits/64d6d07ee18163627c8f517eb31455411921c5ac
The std bump PR was insta-merged already!
Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -129,7 +129,7 @@ theorem two_dvd_centralBinom_of_one_le {n : ℕ} (h : 0 < n) : 2 ∣ centralBino
/-- A crucial lemma to ensure that Catalan numbers can be defined via their explicit formula
`catalan n = n.centralBinom / (n + 1)`. -/
theorem succ_dvd_centralBinom (n : ℕ) : n + 1 ∣ n.centralBinom := by
- have h_s : (n + 1).coprime (2 * n + 1) := by
+ have h_s : (n + 1).Coprime (2 * n + 1) := by
rw [two_mul, add_assoc, coprime_add_self_right, coprime_self_add_left]
exact coprime_one_left n
apply h_s.dvd_of_dvd_mul_left
@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Patrick Stevens, Thomas Browning
-/
import Mathlib.Data.Nat.Choose.Basic
+import Mathlib.Data.Nat.GCD.Basic
import Mathlib.Tactic.Ring
import Mathlib.Tactic.Linarith
I appreciate that this is "going backwards" in the sense of requiring more explicit imports of tactics (and making it more likely that users writing new files will need to import tactics rather than finding them already available).
However it's useful for me while I'm intensively working on refactoring and upstreaming tactics if I can minimise the dependencies between tactics. I'm very much aware that in the long run we don't want users to have to manage imports of tactics, and I am definitely going to tidy this all up again once I'm finished with this project!
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Patrick Stevens, Thomas Browning
-/
import Mathlib.Data.Nat.Choose.Basic
+import Mathlib.Tactic.Ring
import Mathlib.Tactic.Linarith
#align_import data.nat.choose.central from "leanprover-community/mathlib"@"0a0ec35061ed9960bf0e7ffb0335f44447b58977"
In the basic algebraic hierarchy, the Defs
files should ideally only depend on earlier Defs
files, importing as little theory as possible.
This PR makes some rearrangements so Ring.Defs
can depend on Group.Defs
rather than requiring Group.Basic
.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -90,7 +90,7 @@ theorem four_pow_lt_mul_centralBinom (n : ℕ) (n_big : 4 ≤ n) : 4 ^ n < n * c
· norm_num [centralBinom, choose]
obtain ⟨n, rfl⟩ : ∃ m, n = m + 1 := Nat.exists_eq_succ_of_ne_zero (Nat.not_eq_zero_of_lt hn)
calc
- 4 ^ (n + 1) < 4 * (n * centralBinom n) := lt_of_eq_of_lt (pow_succ'' n 4) $
+ 4 ^ (n + 1) < 4 * (n * centralBinom n) := lt_of_eq_of_lt pow_succ' $
(mul_lt_mul_left <| zero_lt_four' ℕ).mpr (IH n n.lt_succ_self (Nat.le_of_lt_succ hn))
_ ≤ 2 * (2 * n + 1) * centralBinom n := by rw [← mul_assoc]; linarith
_ = (n + 1) * centralBinom (n + 1) := (succ_mul_centralBinom_succ n).symm
Briefly during the port we were adding "Ported by" headers, but only ~60 / 3000 files ended up with such a header.
I propose deleting them.
We could consider adding these uniformly via a script, as part of the great history rewrite...?
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -2,7 +2,6 @@
Copyright (c) 2021 Patrick Stevens. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Patrick Stevens, Thomas Browning
-Ported by: Frédéric Dupuis
-/
import Mathlib.Data.Nat.Choose.Basic
import Mathlib.Tactic.Linarith
@@ -3,15 +3,12 @@ Copyright (c) 2021 Patrick Stevens. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Patrick Stevens, Thomas Browning
Ported by: Frédéric Dupuis
-
-! This file was ported from Lean 3 source module data.nat.choose.central
-! leanprover-community/mathlib commit 0a0ec35061ed9960bf0e7ffb0335f44447b58977
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Data.Nat.Choose.Basic
import Mathlib.Tactic.Linarith
+#align_import data.nat.choose.central from "leanprover-community/mathlib"@"0a0ec35061ed9960bf0e7ffb0335f44447b58977"
+
/-!
# Central binomial coefficients
Alongside any necessary spacing/flow changes to accommodate their removal.
@@ -113,8 +113,8 @@ theorem four_pow_le_two_mul_self_mul_centralBinom :
| n + 4, _ =>
calc
4 ^ (n+4) ≤ (n+4) * centralBinom (n+4) := (four_pow_lt_mul_centralBinom _ le_add_self).le
- _ ≤ 2 * (n+4) * centralBinom (n+4) := by rw [mul_assoc];
- refine' le_mul_of_pos_left zero_lt_two
+ _ ≤ 2 * (n+4) * centralBinom (n+4) := by
+ rw [mul_assoc]; refine' le_mul_of_pos_left zero_lt_two
#align nat.four_pow_le_two_mul_self_mul_central_binom Nat.four_pow_le_two_mul_self_mul_centralBinom
theorem two_dvd_centralBinom_succ (n : ℕ) : 2 ∣ centralBinom (n + 1) := by
fix-comments.py
on all files.@@ -15,7 +15,7 @@ import Mathlib.Tactic.Linarith
/-!
# Central binomial coefficients
-This file proves properties of the central binomial coefficients (that is, `nat.choose (2 * n) n`).
+This file proves properties of the central binomial coefficients (that is, `Nat.choose (2 * n) n`).
## Main definition and results
This PR fixes two things:
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.#align
statements. (This was needed for a script I wrote for #3630.)@@ -60,7 +60,6 @@ theorem choose_le_centralBinom (r n : ℕ) : choose (2 * n) r ≤ centralBinom n
calc
(2 * n).choose r ≤ (2 * n).choose (2 * n / 2) := choose_le_middle r (2 * n)
_ = (2 * n).choose n := by rw [Nat.mul_div_cancel_left n zero_lt_two]
-
#align nat.choose_le_central_binom Nat.choose_le_centralBinom
theorem two_le_centralBinom (n : ℕ) (n_pos : 0 < n) : 2 ≤ centralBinom n :=
@@ -68,7 +67,6 @@ theorem two_le_centralBinom (n : ℕ) (n_pos : 0 < n) : 2 ≤ centralBinom n :=
2 ≤ 2 * n := le_mul_of_pos_right n_pos
_ = (2 * n).choose 1 := (choose_one_right (2 * n)).symm
_ ≤ centralBinom n := choose_le_centralBinom 1 n
-
#align nat.two_le_central_binom Nat.two_le_centralBinom
/-- An inductive property of the central binomial coefficient.
@@ -83,7 +81,6 @@ theorem succ_mul_centralBinom_succ (n : ℕ) :
Nat.add_sub_cancel_left]
_ = 2 * ((2 * n).choose n * (2 * n + 1)) := by rw [choose_mul_succ_eq]
_ = 2 * (2 * n + 1) * (2 * n).choose n := by rw [mul_assoc, mul_comm (2 * n + 1)]
-
#align nat.succ_mul_central_binom_succ Nat.succ_mul_centralBinom_succ
/-- An exponential lower bound on the central binomial coefficient.
@@ -101,7 +98,6 @@ theorem four_pow_lt_mul_centralBinom (n : ℕ) (n_big : 4 ≤ n) : 4 ^ n < n * c
(mul_lt_mul_left <| zero_lt_four' ℕ).mpr (IH n n.lt_succ_self (Nat.le_of_lt_succ hn))
_ ≤ 2 * (2 * n + 1) * centralBinom n := by rw [← mul_assoc]; linarith
_ = (n + 1) * centralBinom (n + 1) := (succ_mul_centralBinom_succ n).symm
-
#align nat.four_pow_lt_mul_central_binom Nat.four_pow_lt_mul_centralBinom
/-- An exponential lower bound on the central binomial coefficient.
The unported dependencies are