-- Mathlib/Computability/AkraBazzi/AkraBazzi.lean
/-- The main proof of the lower bound part of the Akra-Bazzi theorem. The factor
`1 + ε n` does not change the asymptotic order, but is needed for the induction step to go
through. -/
lemma smoothingFn_mul_asympBound_isBigO_T :
    (fun (n : ℕ) => (1 + ε n) * asympBound g a b n) =O[atTop] T

Proof state:
case h
α : Type u_1
inst✝¹ : Fintype α
T : ℕ → ℝ
g : ℝ → ℝ
a b : α → ℝ
r : α → ℕ → ℕ
inst✝ : Nonempty α
R : AkraBazziRecurrence T g a b r
b' : ℝ := b (min_bi b) / 2
hb_pos : 0 < b'
c₁ : ℝ
hc₁ : c₁ > 0
h_sumTransform_aux : ∀ᶠ (n : ℕ) in atTop, ∀ (i : α), sumTransform (p a b) g (r i n) n ≤ c₁ * g ↑n
n₀ : ℕ
n₀_ge_Rn₀ : R.n₀ ≤ n₀
h_b_floor : 0 < ⌊b' * ↑n₀⌋₊
h_smoothing_pos : ∀ (y : ℕ), n₀ ≤ y → 0 < 1 + ε ↑y
h_smoothing_pos' : ∀ (y : ℕ), ⌊b' * ↑n₀⌋₊ ≤ y → 0 < 1 + ε ↑y
h_asympBound_pos : ∀ (y : ℕ), n₀ ≤ y → 0 < asympBound g a b y
h_asympBound_r_pos : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), 0 < asympBound g a b (r i y)
h_asympBound_floor : ∀ (y : ℕ), ⌊b' * ↑n₀⌋₊ ≤ y → 0 < asympBound g a b y
n₀_pos : 0 < n₀
h_smoothing_r_pos : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), 0 < 1 + ε ↑(r i y)
bound2 : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), b i ^ p a b * ↑y ^ p a b * (1 + ε ↑y) ≤ ↑(r i y) ^ p a b * (1 + ε ↑(r i y))
h_smoothingFn_floor : ∀ (y : ℕ), ⌊b' * ↑n₀⌋₊ ≤ y → 0 < 1 + ε ↑y
h_sumTransform : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), sumTransform (p a b) g (r i y) y ≤ c₁ * g ↑y
h_bi_le_r : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), b (min_bi b) / 2 * ↑y ≤ ↑(r i y)
h_exp : ∀ (y : ℕ), n₀ ≤ y → ⌈rexp 1⌉₊ ≤ y
h_base_nonempty : (Ico ⌊b (min_bi b) / 2 * ↑n₀⌋₊ n₀).Nonempty
base_min : ℝ := (Ico ⌊b' * ↑n₀⌋₊ n₀).inf' h_base_nonempty fun n => T n / ((1 + ε ↑n) * asympBound g a b n)
base_min_def : base_min = (Ico ⌊b' * ↑n₀⌋₊ n₀).inf' h_base_nonempty fun n => T n / ((1 + ε ↑n) * asympBound g a b n)
C : ℝ := (2 * c₁)⁻¹ ⊓ base_min
⊢ ∃ c > 0, ∀ n ≥ n₀, c * ‖(1 + ε ↑n) * asympBound g a b n‖ ≤ ‖T n‖

Tactic:
have hC_pos : 0 < C := by
  refine lt_min (by positivity) ?_
  obtain ⟨m, hm_mem, hm⟩ :=
    Finset.exists_mem_eq_inf' h_base_nonempty (fun n => T n / ((1 + ε n) * asympBound g a b n))
  calc 0 < T m / ((1 + ε m) * asympBound g a b m) := by
            have H₁ : 0 < T m := by exact R.T_pos _
            have H₂ : 0 < 1 + ε m := by rw [Finset.mem_Ico] at hm_mem
                                        exact h_smoothing_pos' m hm_mem.1
            have H₃ : 0 < asympBound g a b m := by
              refine R.asympBound_pos m ?_
              calc 0 < ⌊b' * n₀⌋₊ := by exact h_b_floor
                   _ ≤ m := by rw [Finset.mem_Ico] at hm_mem; exact hm_mem.1
            positivity
       _ = base_min := by rw [base_min_def, hm]

Result:
case h
α : Type u_1
inst✝¹ : Fintype α
T : ℕ → ℝ
g : ℝ → ℝ
a b : α → ℝ
r : α → ℕ → ℕ
inst✝ : Nonempty α
R : AkraBazziRecurrence T g a b r
b' : ℝ := b (min_bi b) / 2
hb_pos : 0 < b'
c₁ : ℝ
hc₁ : c₁ > 0
h_sumTransform_aux : ∀ᶠ (n : ℕ) in atTop, ∀ (i : α), sumTransform (p a b) g (r i n) n ≤ c₁ * g ↑n
n₀ : ℕ
n₀_ge_Rn₀ : R.n₀ ≤ n₀
h_b_floor : 0 < ⌊b' * ↑n₀⌋₊
h_smoothing_pos : ∀ (y : ℕ), n₀ ≤ y → 0 < 1 + ε ↑y
h_smoothing_pos' : ∀ (y : ℕ), ⌊b' * ↑n₀⌋₊ ≤ y → 0 < 1 + ε ↑y
h_asympBound_pos : ∀ (y : ℕ), n₀ ≤ y → 0 < asympBound g a b y
h_asympBound_r_pos : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), 0 < asympBound g a b (r i y)
h_asympBound_floor : ∀ (y : ℕ), ⌊b' * ↑n₀⌋₊ ≤ y → 0 < asympBound g a b y
n₀_pos : 0 < n₀
h_smoothing_r_pos : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), 0 < 1 + ε ↑(r i y)
bound2 : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), b i ^ p a b * ↑y ^ p a b * (1 + ε ↑y) ≤ ↑(r i y) ^ p a b * (1 + ε ↑(r i y))
h_smoothingFn_floor : ∀ (y : ℕ), ⌊b' * ↑n₀⌋₊ ≤ y → 0 < 1 + ε ↑y
h_sumTransform : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), sumTransform (p a b) g (r i y) y ≤ c₁ * g ↑y
h_bi_le_r : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), b (min_bi b) / 2 * ↑y ≤ ↑(r i y)
h_exp : ∀ (y : ℕ), n₀ ≤ y → ⌈rexp 1⌉₊ ≤ y
h_base_nonempty : (Ico ⌊b (min_bi b) / 2 * ↑n₀⌋₊ n₀).Nonempty
base_min : ℝ := (Ico ⌊b' * ↑n₀⌋₊ n₀).inf' h_base_nonempty fun n => T n / ((1 + ε ↑n) * asympBound g a b n)
base_min_def : base_min = (Ico ⌊b' * ↑n₀⌋₊ n₀).inf' h_base_nonempty fun n => T n / ((1 + ε ↑n) * asympBound g a b n)
C : ℝ := (2 * c₁)⁻¹ ⊓ base_min
hC_pos : 0 < C
⊢ ∃ c > 0, ∀ n ≥ n₀, c * ‖(1 + ε ↑n) * asympBound g a b n‖ ≤ ‖T n‖

Proof state:
case bc
α : Type u_1
inst✝¹ : Fintype α
T : ℕ → ℝ
g : ℝ → ℝ
a b : α → ℝ
r : α → ℕ → ℕ
inst✝ : Nonempty α
R : AkraBazziRecurrence T g a b r
b' : ℝ := b (min_bi b) / 2
hb_pos : 0 < b'
c₁ : ℝ
hc₁ : c₁ > 0
h_sumTransform_aux : ∀ᶠ (n : ℕ) in atTop, ∀ (i : α), sumTransform (p a b) g (r i n) n ≤ c₁ * g ↑n
n₀ : ℕ
n₀_ge_Rn₀ : R.n₀ ≤ n₀
h_b_floor : 0 < ⌊b' * ↑n₀⌋₊
h_smoothing_pos : ∀ (y : ℕ), n₀ ≤ y → 0 < 1 + ε ↑y
h_smoothing_pos' : ∀ (y : ℕ), ⌊b' * ↑n₀⌋₊ ≤ y → 0 < 1 + ε ↑y
h_asympBound_pos : ∀ (y : ℕ), n₀ ≤ y → 0 < asympBound g a b y
h_asympBound_r_pos : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), 0 < asympBound g a b (r i y)
h_asympBound_floor : ∀ (y : ℕ), ⌊b' * ↑n₀⌋₊ ≤ y → 0 < asympBound g a b y
n₀_pos : 0 < n₀
h_smoothing_r_pos : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), 0 < 1 + ε ↑(r i y)
bound2 : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), b i ^ p a b * ↑y ^ p a b * (1 + ε ↑y) ≤ ↑(r i y) ^ p a b * (1 + ε ↑(r i y))
h_smoothingFn_floor : ∀ (y : ℕ), ⌊b' * ↑n₀⌋₊ ≤ y → 0 < 1 + ε ↑y
h_sumTransform : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), sumTransform (p a b) g (r i y) y ≤ c₁ * g ↑y
h_bi_le_r : ∀ (y : ℕ), n₀ ≤ y → ∀ (i : α), b (min_bi b) / 2 * ↑y ≤ ↑(r i y)
h_exp : ∀ (y : ℕ), n₀ ≤ y → ⌈rexp 1⌉₊ ≤ y
h_base_nonempty : (Ico ⌊b (min_bi b) / 2 * ↑n₀⌋₊ n₀).Nonempty
base_min : ℝ := (Ico ⌊b' * ↑n₀⌋₊ n₀).inf' h_base_nonempty fun n => T n / ((1 + ε ↑n) * asympBound g a b n)
base_min_def : base_min = (Ico ⌊b' * ↑n₀⌋₊ n₀).inf' h_base_nonempty fun n => T n / ((1 + ε ↑n) * asympBound g a b n)
C : ℝ := (2 * c₁)⁻¹ ⊓ base_min
hC_pos : 0 < C
h_base : ∀ n ∈ Ico ⌊b' * ↑n₀⌋₊ n₀, C * ((1 + ε ↑n) * asympBound g a b n) ≤ T n
n : ℕ
h_ind : ∀ m < n, m ≥ n₀ → 0 < asympBound g a b m → 0 < 1 + ε ↑m → C * ((1 + ε ↑m) * asympBound g a b m) ≤ T m
hn : n ≥ n₀
h_asympBound_pos' : 0 < asympBound g a b n
h_one_sub_smoothingFn_pos' : 0 < 1 + ε ↑n
b_mul_n₀_le_ri : ∀ (i : α), ⌊b' * ↑n₀⌋₊ ≤ r i n
g_pos : 0 ≤ g ↑n
⊢ C * c₁ * (1 + ε ↑n) ≤ 1

Tactic:
calc C * c₁ * (1 + ε n) ≤ C * c₁ * 2 := by
          gcongr
          refine one_add_smoothingFn_le_two ?_
          calc exp 1 ≤ ⌈exp 1⌉₊ := by exact Nat.le_ceil _
                   _ ≤ n := by exact_mod_cast h_exp n hn
      _ = C * (2 * c₁) := by ring
      _ ≤ (2 * c₁)⁻¹ * (2 * c₁) := by gcongr; exact min_le_left _ _
      _ = c₁⁻¹ * c₁ := by ring
      _ = 1 := inv_mul_cancel₀ (by positivity)

Result:
no goals