import Mathlib /-! # `∑_{i=j₀}^{j} 2^i/i^K = (2 + o(1)) 2^j/j^K`, and the (P) ⟺ (P') consumer equivalence Job #25 (formalize). `research/consumer-comparison.md` §2 item 3 and `research/TWIN-REDUCTION.md` §2 use this lemma to pass between two OPEN sufficient conditions. Proving it proves neither condition: it is a statement about real sequences. * `w K i = 2^i / i^K` for `i ≥ 1` and a fixed real `K ≥ 0`. The value at `i = 0` is never used: every statement below either starts its sums at `j₀ ≥ 1` or only uses `w` at large indices. * (a) `sum_div_w_tendsto`: for every `j₀ ≥ 1`, `(∑_{i ∈ [j₀, j]} w K i) / w K j → 2` as `j → ∞`. * (b) `consumer_equiv`: for `a i ≥ 0`, `(∃ c > 0, ∃ᶠ j, c·w K j ≤ a j) ↔ (∃ c > 0, ∃ᶠ j, c·w K j ≤ ∑_{i ≤ j} a i)`. Forward uses the same `c`. Backward: (P') with `c'` gives (P) with `c = c'/4`. -/ open Filter Topology Finset namespace ConsumerGrowth /-- `w K i = 2^i / i^K`. -/ noncomputable def w (K : ℝ) (i : ℕ) : ℝ := (2 : ℝ) ^ i / (i : ℝ) ^ K lemma w_pos (K : ℝ) {i : ℕ} (hi : 1 ≤ i) : 0 < w K i := by have h : (0 : ℝ) < (i : ℝ) := by exact_mod_cast hi exact div_pos (pow_pos two_pos i) (Real.rpow_pos_of_pos h K) /-- The ratio of a shifted term to the last one. -/ lemma w_ratio (K : ℝ) {j m : ℕ} (h : m + 1 ≤ j) : w K (j - m) / w K j = (1 / 2 : ℝ) ^ m * ((j : ℝ) / ((j - m : ℕ) : ℝ)) ^ K := by obtain ⟨a, rfl⟩ : ∃ a, j = a + m := ⟨j - m, by omega⟩ have ha : (0 : ℝ) < (a : ℝ) := by exact_mod_cast (by omega : 0 < a) have hj : (0 : ℝ) < ((a + m : ℕ) : ℝ) := by exact_mod_cast (by omega : 0 < a + m) have hsub : a + m - m = a := by omega rw [hsub] unfold w rw [Real.div_rpow hj.le ha.le] have h1 : (0 : ℝ) < (a : ℝ) ^ K := Real.rpow_pos_of_pos ha K have h2 : (0 : ℝ) < ((a + m : ℕ) : ℝ) ^ K := Real.rpow_pos_of_pos hj K rw [pow_add] field_simp rw [← mul_pow] norm_num /-- Reflect the window sum so that the last term comes first. -/ lemma sum_reflect (K : ℝ) {j₀ j : ℕ} (h : j₀ ≤ j) : ∑ i ∈ Icc j₀ j, w K i = ∑ m ∈ range (j - j₀ + 1), w K (j - m) := by refine Finset.sum_nbij' (fun i => j - i) (fun m => j - m) ?_ ?_ ?_ ?_ ?_ · intro i hi simp only [Finset.mem_Icc, Finset.mem_range] at hi ⊢ omega · intro m hm simp only [Finset.mem_Icc, Finset.mem_range] at hm ⊢ omega · intro i hi simp only [Finset.mem_Icc] at hi omega · intro m hm simp only [Finset.mem_range] at hm omega · intro i hi simp only [Finset.mem_Icc] at hi congr 1 omega /-- `(m+1)^n ≤ 2^n (m^n + 1)` for natural `m`, `n`. -/ lemma succ_pow_le (m n : ℕ) : ((m : ℝ) + 1) ^ n ≤ 2 ^ n * ((m : ℝ) ^ n + 1) := by rcases Nat.eq_zero_or_pos m with rfl | hm · simp only [Nat.cast_zero, zero_add, one_pow] have : (1 : ℝ) ≤ 2 ^ n := one_le_pow₀ (by norm_num) rcases Nat.eq_zero_or_pos n with rfl | hn · norm_num · rw [zero_pow (by omega)]; linarith · have hm1 : (1 : ℝ) ≤ (m : ℝ) := by exact_mod_cast hm calc ((m : ℝ) + 1) ^ n ≤ (2 * (m : ℝ)) ^ n := by gcongr; linarith _ = 2 ^ n * (m : ℝ) ^ n := by rw [mul_pow] _ ≤ 2 ^ n * ((m : ℝ) ^ n + 1) := by have : (0 : ℝ) ≤ 2 ^ n := by positivity nlinarith /-- (a): the window sum is `(2 + o(1))` times its last term. -/ theorem sum_div_w_tendsto (K : ℝ) (hK : 0 ≤ K) (j₀ : ℕ) (hj₀ : 1 ≤ j₀) : Tendsto (fun j => (∑ i ∈ Icc j₀ j, w K i) / w K j) atTop (𝓝 2) := by set n := ⌈K⌉₊ let f : ℕ → ℕ → ℝ := fun j m => if m + j₀ ≤ j then (1 / 2 : ℝ) ^ m * ((j : ℝ) / ((j - m : ℕ) : ℝ)) ^ K else 0 let bound : ℕ → ℝ := fun m => 2 ^ n * ((m : ℝ) ^ n * (1 / 2 : ℝ) ^ m + (1 / 2 : ℝ) ^ m) have h_sum : Summable bound := ((summable_pow_mul_geometric_of_norm_lt_one n (by norm_num : ‖(1 / 2 : ℝ)‖ < 1)).add summable_geometric_two).mul_left _ have hab : ∀ m : ℕ, Tendsto (fun j => f j m) atTop (𝓝 ((1 / 2 : ℝ) ^ m)) := by intro m have hq : Tendsto (fun j : ℕ => (m : ℝ) / ((j - m : ℕ) : ℝ)) atTop (𝓝 0) := (tendsto_const_div_atTop_nhds_zero_nat (m : ℝ)).comp (tendsto_sub_atTop_nat m) have hr : Tendsto (fun j : ℕ => (j : ℝ) / ((j - m : ℕ) : ℝ)) atTop (𝓝 1) := by have h1 : Tendsto (fun j : ℕ => 1 + (m : ℝ) / ((j - m : ℕ) : ℝ)) atTop (𝓝 1) := by simpa using tendsto_const_nhds.add hq refine h1.congr' ?_ filter_upwards [eventually_ge_atTop (m + 1)] with j hj have hpos : (0 : ℝ) < ((j - m : ℕ) : ℝ) := by exact_mod_cast (by omega : 0 < j - m) have hcast : ((j - m : ℕ) : ℝ) = (j : ℝ) - m := by rw [Nat.cast_sub (by omega : m ≤ j)] field_simp rw [hcast] ring have hrK : Tendsto (fun j : ℕ => ((j : ℝ) / ((j - m : ℕ) : ℝ)) ^ K) atTop (𝓝 1) := by have := (Real.continuousAt_rpow_const 1 K (Or.inl one_ne_zero)).tendsto.comp hr rw [Real.one_rpow] at this exact this have hlim : Tendsto (fun j : ℕ => (1 / 2 : ℝ) ^ m * ((j : ℝ) / ((j - m : ℕ) : ℝ)) ^ K) atTop (𝓝 ((1 / 2 : ℝ) ^ m)) := by simpa using tendsto_const_nhds.mul hrK refine hlim.congr' ?_ filter_upwards [eventually_ge_atTop (m + j₀)] with j hj simp only [f, if_pos hj] have h_bound : ∀ᶠ j in atTop, ∀ m, ‖f j m‖ ≤ bound m := by refine Eventually.of_forall fun j m => ?_ simp only [f] split_ifs with hmj · have hjm : 1 ≤ j - m := by omega have ha : (0 : ℝ) < ((j - m : ℕ) : ℝ) := by exact_mod_cast (by omega : 0 < j - m) have hx0 : (0 : ℝ) ≤ (j : ℝ) / ((j - m : ℕ) : ℝ) := by positivity have hxle : (j : ℝ) / ((j - m : ℕ) : ℝ) ≤ (m : ℝ) + 1 := by rw [div_le_iff₀ ha] have hcast : ((j - m : ℕ) : ℝ) = (j : ℝ) - m := by rw [Nat.cast_sub (by omega : m ≤ j)] have h1 : (1 : ℝ) ≤ ((j - m : ℕ) : ℝ) := by exact_mod_cast hjm rw [hcast] at h1 ⊢ nlinarith have hK1 : ((j : ℝ) / ((j - m : ℕ) : ℝ)) ^ K ≤ ((m : ℝ) + 1) ^ K := Real.rpow_le_rpow hx0 hxle hK have hK2 : ((m : ℝ) + 1) ^ K ≤ ((m : ℝ) + 1) ^ (n : ℝ) := Real.rpow_le_rpow_of_exponent_le (by linarith [(Nat.cast_nonneg m : (0 : ℝ) ≤ m)]) (Nat.le_ceil K) rw [Real.rpow_natCast] at hK2 have hK3 := succ_pow_le m n have hg : (0 : ℝ) ≤ (1 / 2 : ℝ) ^ m := by positivity have hnonneg : 0 ≤ (1 / 2 : ℝ) ^ m * ((j : ℝ) / ((j - m : ℕ) : ℝ)) ^ K := by positivity rw [Real.norm_of_nonneg hnonneg] calc (1 / 2 : ℝ) ^ m * ((j : ℝ) / ((j - m : ℕ) : ℝ)) ^ K ≤ (1 / 2 : ℝ) ^ m * (2 ^ n * ((m : ℝ) ^ n + 1)) := by apply mul_le_mul_of_nonneg_left _ hg linarith _ = bound m := by simp only [bound]; ring · simp only [norm_zero, bound] positivity have hT := tendsto_tsum_of_dominated_convergence h_sum hab h_bound rw [tsum_geometric_two] at hT refine hT.congr' ?_ filter_upwards [eventually_ge_atTop j₀] with j hj have hwj : 0 < w K j := w_pos K (le_trans hj₀ hj) rw [tsum_eq_sum (s := range (j - j₀ + 1))] · rw [sum_reflect K hj, Finset.sum_div] apply Finset.sum_congr rfl intro m hm rw [Finset.mem_range] at hm simp only [f, if_pos (by omega : m + j₀ ≤ j)] rw [w_ratio K (by omega : m + 1 ≤ j)] · intro m hm rw [Finset.mem_range] at hm simp only [f, if_neg (by omega : ¬ (m + j₀ ≤ j))] /-- `w K j → ∞`. -/ lemma w_tendsto_atTop (K : ℝ) : Tendsto (w K) atTop atTop := by set n := ⌈K⌉₊ have h0 : Tendsto (fun i : ℕ => (i : ℝ) ^ n / (2 : ℝ) ^ i) atTop (𝓝[>] 0) := by rw [tendsto_nhdsWithin_iff] refine ⟨tendsto_pow_const_div_const_pow_of_one_lt n one_lt_two, ?_⟩ filter_upwards [eventually_ge_atTop 1] with i hi have : (0 : ℝ) < (i : ℝ) := by exact_mod_cast hi exact Set.mem_Ioi.mpr (by positivity) have hinv := h0.inv_tendsto_nhdsGT_zero refine tendsto_atTop_mono' atTop ?_ hinv filter_upwards [eventually_ge_atTop 1] with i hi have hi' : (1 : ℝ) ≤ (i : ℝ) := by exact_mod_cast hi have hipos : (0 : ℝ) < (i : ℝ) := by linarith simp only [Pi.inv_apply, inv_div] unfold w have hle : (i : ℝ) ^ K ≤ (i : ℝ) ^ (n : ℝ) := Real.rpow_le_rpow_of_exponent_le hi' (Nat.le_ceil K) rw [Real.rpow_natCast] at hle exact div_le_div_of_nonneg_left (by positivity) (Real.rpow_pos_of_pos hipos K) hle /-- (b): the (P) ⟺ (P') consumer equivalence. Forward keeps `c`; backward (P') with `c'` gives (P) with `c'/4`. -/ theorem consumer_equiv (K : ℝ) (hK : 0 ≤ K) (a : ℕ → ℝ) (ha : ∀ i, 0 ≤ a i) : (∃ c > 0, ∃ᶠ j in atTop, c * w K j ≤ a j) ↔ (∃ c > 0, ∃ᶠ j in atTop, c * w K j ≤ ∑ i ∈ range (j + 1), a i) := by constructor · rintro ⟨c, hc, hfreq⟩ refine ⟨c, hc, hfreq.mono fun j hj => hj.trans ?_⟩ exact Finset.single_le_sum (fun i _ => ha i) (Finset.self_mem_range_succ j) · rintro ⟨c, hc, hfreq⟩ refine ⟨c / 4, by positivity, ?_⟩ by_contra hnot rw [Filter.not_frequently] at hnot obtain ⟨N, hN⟩ := Filter.eventually_atTop.mp hnot set N₁ := max N 1 with hN₁ have hsum := sum_div_w_tendsto K hK N₁ (le_max_right _ _) have h3 : ∀ᶠ j in atTop, (∑ i ∈ Icc N₁ j, w K i) / w K j < 3 := hsum.eventually (gt_mem_nhds (by norm_num)) set A := ∑ i ∈ range N₁, a i have hbig : ∀ᶠ j in atTop, 4 * A / c < w K j := (w_tendsto_atTop K).eventually_gt_atTop _ have hev : ∀ᶠ j in atTop, ∑ i ∈ range (j + 1), a i < c * w K j := by filter_upwards [h3, hbig, eventually_ge_atTop N₁] with j hj3 hjb hjN have hwpos : 0 < w K j := w_pos K (le_trans (le_max_right N 1) hjN) have hsplit : ∑ i ∈ range (j + 1), a i = A + ∑ i ∈ Icc N₁ j, a i := by rw [← Finset.sum_range_add_sum_Ico _ (by omega : N₁ ≤ j + 1)] have hI : Finset.Ico N₁ (j + 1) = Finset.Icc N₁ j := by ext i simp only [Finset.mem_Ico, Finset.mem_Icc] omega rw [hI] have htail : ∑ i ∈ Icc N₁ j, a i ≤ ∑ i ∈ Icc N₁ j, c / 4 * w K i := by apply Finset.sum_le_sum intro i hi have hiN : N ≤ i := le_trans (le_max_left N 1) (Finset.mem_Icc.mp hi).1 exact (not_le.mp (hN i hiN)).le rw [← Finset.mul_sum] at htail have hS : ∑ i ∈ Icc N₁ j, w K i < 3 * w K j := by rwa [div_lt_iff₀ hwpos] at hj3 have hA : A < c / 4 * w K j := by rw [div_lt_iff₀ hc] at hjb linarith have hmul : c / 4 * ∑ i ∈ Icc N₁ j, w K i < c / 4 * (3 * w K j) := mul_lt_mul_of_pos_left hS (by positivity) rw [hsplit] linarith obtain ⟨j, h1, h2⟩ := (hfreq.and_eventually hev).exists exact absurd h1 (not_le.mpr h2) end ConsumerGrowth