op_258_exists_divergent_block_indices
For any positive antitone sequence a : ℕ+ → ℝ with divergent sum and any n₀, there exist l ≥ 3 with 2^l ≥ n₀ and strictly increasing r : Fin (l+1) → ℕ+ such that a(r(l)) ≥ 1 / 2^{l-1} and the sum of a on each interval (r(j), r(j+1)] is at least 1 / 2^j.
Statement
theorem op_258_exists_divergent_block_indices (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a) (hsum : (∑' i : ℕ+, ENNReal.ofReal (a i)) = ⊤) (n₀ : ℕ) : ∃ (l : ℕ) (hl : 3 ≤ l) (r : Fin (l + 1) → ℕ+), n₀ ≤ 2^l ∧ (StrictMono r) ∧ (1 / (2 : ℝ)^(l - 1) ≤ a (r ⟨l, by omega⟩)) ∧ (∀ j : Fin l, 1 / (2 : ℝ)^(j : ℕ) ≤ ∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), a i)
- Source
- step towards op_258_exists_divergent_capacity_covering
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- op_258_exists_divergent_capacity_coveringIf a positive antitone profile a has infinite sum in ENNReal, then for any threshold n₀, there exists l ≥ 1 with 2^l ≥ n₀, pairwise…
The proof, explained
The sequence a on ℕ+ is pulled back to ℕ, where its divergence implies unbounded tail sums. A sequence of block endpoints r is constructed greedily starting at r(0) = 1, with each r(j+1) chosen minimal so that the sum of the block is at least 1 / 2^j. If the endpoint condition a(r(l)) ≥ 1 / 2^(l-1) failed for all l ≥ max 3 n₀, the block sums would overshoot by so little that the tail would sum to at most 4, contradicting divergence. Thus an index l ≥ max 3 n₀ exists, which gives 2^l ≥ n₀ and block endpoints satisfying all conditions.
The sum of a on (x, y] in ℕ+ equals the sum of a ∘ toPNat' on (x, y] in ℕ.
By `Finset.sum_nbij'`, the interval (x, y] in ℕ+ maps bijectively to the interval (x, y] in ℕ under coercion to ℕ, with inverse given by `toPNat'`. Because x ≥ 1, every element in the natural interval is strictly positive, ensuring that the maps are mutual bijections and the summands match.
uses
Finset.sum_nbij',Finset.mem_Ioc,PNat.coe_lt_coe,PNat.coe_le_coe,lt_of_le_of_lt,Nat.zero_le,PNat.toPNat'_coe,PNat.coe_toPNat'refine Finset.sum_nbij' (fun i => (i : ℕ)) (fun n => n.toPNat') ?_ ?_ ?_ ?_ ?_ · intro i hi rw [Finset.mem_Ioc] at hi ⊢ exact ⟨PNat.coe_lt_coe _ _ |>.mpr hi.1, PNat.coe_le_coe _ _ |>.mpr hi.2⟩ · intro n hn rw [Finset.mem_Ioc] at hn ⊢ have hn0 : 0 < n := lt_of_le_of_lt (Nat.zero_le _) hn.1 refine ⟨?_, ?_⟩ · rw [← PNat.coe_lt_coe, PNat.toPNat'_coe hn0]; exact hn.1 · rw [← PNat.coe_le_coe, PNat.toPNat'_coe hn0]; exact hn.2 · intro i _ exact PNat.coe_toPNat' i · intro n hn rw [Finset.mem_Ioc] at hn exact PNat.toPNat'_coe (lt_of_le_of_lt (Nat.zero_le _) hn.1) · intro i _ rw [PNat.coe_toPNat']
There exists a sequence of indices r with r(0) = 1 such that the sum of b on each block (r(j), r(j+1)] is at least 1 / 2^j.
Because all tail sums of b are unbounded, for any starting index and target there is a finite interval whose sum meets the target. We set r(0) = 1 and define r(j+1) recursively using `Nat.find` as the least integer such that the sum of b on (r(j), r(j+1)] is at least 1 / 2^j.
uses
Nat.rec,Nat.find,Nat.find_specclassical have hex : ∀ m j : ℕ, ∃ k, 1 / (2 : ℝ) ^ j ≤ ∑ n ∈ Finset.Ioc m k, b n := fun m j => hunb m _ let r : ℕ → ℕ := fun j => Nat.rec 1 (fun j rj => Nat.find (hex rj j)) j have hr0 : r 0 = 1 := rfl have hrs : ∀ j, r (j + 1) = Nat.find (hex (r j) j) := fun j => rfl have hspec : ∀ j, 1 / (2 : ℝ) ^ j ≤ ∑ n ∈ Finset.Ioc (r j) (r (j + 1)), b n := by intro j; rw [hrs]; exact Nat.find_spec (hex (r j) j)
The index sequence r is strictly increasing.
If r(j+1) ≤ r(j) for some j, the interval (r(j), r(j+1)] would be empty and its sum would be 0, which contradicts that the sum is at least 1 / 2^j > 0. Hence r(j) < r(j+1) everywhere, so r is strictly increasing.
uses
not_lt,Finset.Ioc_eq_empty,Finset.sum_empty,strictMono_nat_of_lt_succhave hlt : ∀ j, r j < r (j + 1) := by intro j by_contra hc rw [not_lt] at hc have := hspec j rw [Finset.Ioc_eq_empty (by omega), Finset.sum_empty] at this have : (0 : ℝ) < 1 / 2 ^ j := by positivity linarith have hmono : StrictMono r := strictMono_nat_of_lt_succ hlt
Each block sum overshoots its target 1 / 2^j by strictly less than b(r(j+1)).
By the minimality of r(j+1) in `Nat.find`, the sum over the subinterval up to r(j+1) - 1 is strictly less than 1 / 2^j. Adding the final element b(r(j+1)) shows that the full block sum is strictly less than 1 / 2^j + b(r(j+1)).
uses
Nat.find_min,Finset.sum_Ioc_succ_tophave hover : ∀ j, ∑ n ∈ Finset.Ioc (r j) (r (j + 1)), b n < 1 / (2 : ℝ) ^ j + b (r (j + 1)) := by intro j obtain ⟨k, hk⟩ : ∃ k, r (j + 1) = k + 1 := ⟨r (j + 1) - 1, by have := hlt j; omega⟩ have hjk : r j ≤ k := by have := hlt j; omega have hmin : ¬ (1 / (2 : ℝ) ^ j ≤ ∑ n ∈ Finset.Ioc (r j) k, b n) := by have := Nat.find_min (hex (r j) j) (m := k) (by rw [← hrs]; omega) exact this rw [hk, Finset.sum_Ioc_succ_top hjk] linarith [not_le.mp hmin]
It suffices to find an index l ≥ L₀ with b(r(l)) ≥ 1 / 2^(l-1), and we assume for contradiction that no such l exists.
If such an l exists, the sequence r already satisfies all the required block conditions. To derive a contradiction, we assume that b(r(l)) < 1 / 2^(l-1) for every l ≥ L₀.
suffices hl : ∃ l, L₀ ≤ l ∧ 1 / (2 : ℝ) ^ (l - 1) ≤ b (r l) by obtain ⟨l, hl, hb⟩ := hl exact ⟨l, hl, r, hr0, hmono, hb, fun j _ => hspec j⟩ by_contra hcon push_neg at hcon
For every i ≥ 0, the (L₀ + i)-th block sum is at most 2 / 2^i.
By the overshoot bound, the block sum on (r(L₀+i), r(L₀+i+1)] is strictly less than 1 / 2^(L₀+i) + b(r(L₀+i+1)). Under the contradiction hypothesis, b(r(L₀+i+1)) < 1 / 2^(L₀+i). Since L₀ ≥ 0, 1 / 2^(L₀+i) ≤ 1 / 2^i, giving a bound of 1 / 2^i + 1 / 2^i = 2 / 2^i.
uses
one_div_le_one_div_of_le,pow_le_pow_right₀have hsmall : ∀ i, ∑ n ∈ Finset.Ioc (r (L₀ + i)) (r (L₀ + i + 1)), b n ≤ 2 / (2 : ℝ) ^ i := by intro i have h1 := hover (L₀ + i) have h2 := hcon (L₀ + i + 1) (by omega) rw [show L₀ + i + 1 - 1 = L₀ + i by omega] at h2 have h3 : 1 / (2 : ℝ) ^ (L₀ + i) ≤ 1 / 2 ^ i := by apply one_div_le_one_div_of_le (by positivity) exact pow_le_pow_right₀ (by norm_num) (by omega) have h4 : 2 / (2 : ℝ) ^ i = 1 / 2 ^ i + 1 / 2 ^ i := by ring linarith
For every k, the sum of b on (r(L₀), r(L₀+k)] is bounded above by 4 - 4 / 2^k.
We induct on k. The base case k = 0 is empty and trivial. In the induction step, splitting the interval into (r(L₀), r(L₀+k)] and (r(L₀+k), r(L₀+k+1)] and adding the bound 2 / 2^k from the previous step yields (4 - 4 / 2^k) + 2 / 2^k = 4 - 4 / 2^(k+1).
uses
Finset.sum_Ioc_consecutive,Nat.le_add_right,pow_succhave htot : ∀ k, ∑ n ∈ Finset.Ioc (r L₀) (r (L₀ + k)), b n ≤ 4 - 4 / (2 : ℝ) ^ k := by intro k induction k with | zero => simp | succ k ih => rw [← Finset.sum_Ioc_consecutive _ (hmono.monotone (Nat.le_add_right L₀ k)) (hmono.monotone (by omega : L₀ + k ≤ L₀ + (k + 1)))] have := hsmall k rw [show L₀ + k + 1 = L₀ + (k + 1) by omega] at this have h5 : 4 - 4 / (2 : ℝ) ^ (k + 1) = 4 - 4 / 2 ^ k + 2 / 2 ^ k := by rw [pow_succ]; field_simp; ring linarith
Contradiction, establishing op258b_greedy.
Since tail sums of b starting from r(L₀) are unbounded, there is some k whose sum reaches at least 5. Because r is strictly increasing, k ≤ r(L₀+k), so this sum is bounded by the sum up to r(L₀+k), which is at most 4 - 4 / 2^k < 4, a contradiction.
uses
Finset.sum_le_sum_of_subset_of_nonneg,Finset.Ioc_subset_Ioc_rightobtain ⟨k, hk⟩ := hunb (r L₀) 5 have hkle : k ≤ r (L₀ + k) := by have := hmono.id_le (L₀ + k); simp only [id] at this; omega have hsub : ∑ n ∈ Finset.Ioc (r L₀) k, b n ≤ ∑ n ∈ Finset.Ioc (r L₀) (r (L₀ + k)), b n := Finset.sum_le_sum_of_subset_of_nonneg (Finset.Ioc_subset_Ioc_right hkle) (fun n _ _ => (hpos n).le) have h6 := htot k have h7 : 0 < 4 / (2 : ℝ) ^ k := by positivity linarith
The bounds on Fin indices in the statement hold by linear arithmetic, the sequence b(n) = a(n.toPNat') is positive, and the sequence a is not summable.
The index bounds in the theorem statement are discharged by `omega`. Since a is positive on ℕ+, b is positive on ℕ. If a were summable, its extended real sum would equal the coercion of its real sum and would therefore be finite, contradicting the assumption that the sum is ⊤.
uses
ENNReal.ofReal_tsum_of_nonneg,ENNReal.ofReal_ne_top(1 / (2 : ℝ)^(l - 1) ≤ a (r ⟨l, by omega⟩)) ∧ (∀ j : Fin l, 1 / (2 : ℝ)^(j : ℕ) ≤ ∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), a i) := by classical set b : ℕ → ℝ := fun n => a n.toPNat' with hb have hbpos : ∀ n, 0 < b n := fun n => hpos _ have hns : ¬ Summable a := by intro hs rw [← ENNReal.ofReal_tsum_of_nonneg (fun i => (hpos i).le) hs] at hsum exact ENNReal.ofReal_ne_top hsum
Every tail sum of b is unbounded.
If some tail sum of b from m were bounded by C, then for every finite subset u ⊆ ℕ+, the sum of a over u would be bounded by the sum over (0, m] plus C. By `summable_of_sum_le`, this would make a summable, contradicting that a is not summable.
uses
summable_of_sum_le,PNat.coe_injective,Finset.sum_map,Finset.sum_congr,PNat.coe_toPNat',Finset.mem_Ioc,le_trans,Finset.le_sup,le_max_right,Finset.sum_le_sum_of_subset_of_nonneg,Finset.sum_Ioc_consecutive,Nat.zero_le,le_max_lefthave hunb : ∀ m : ℕ, ∀ C : ℝ, ∃ k, C ≤ ∑ n ∈ Finset.Ioc m k, b n := by intro m C by_contra hcon push_neg at hcon apply hns refine summable_of_sum_le (c := ∑ n ∈ Finset.Ioc 0 m, b n + C) (fun i => (hpos i).le) ?_ intro u set e : ℕ+ ↪ ℕ := ⟨fun i => (i : ℕ), PNat.coe_injective⟩ set K := max m (u.sup fun i => (i : ℕ)) have h1 : ∑ i ∈ u, a i = ∑ n ∈ u.map e, b n := by rw [Finset.sum_map] exact Finset.sum_congr rfl (fun i _ => by simp [hb, e, PNat.coe_toPNat']) have h2 : u.map e ⊆ Finset.Ioc 0 K := by intro n hn obtain ⟨i, hi, rfl⟩ := Finset.mem_map.mp hn simp only [Finset.mem_Ioc, e, Function.Embedding.coeFn_mk] exact ⟨i.pos, le_trans (Finset.le_sup (f := fun i : ℕ+ => (i : ℕ)) hi) (le_max_right _ _)⟩ have h3 : ∑ n ∈ u.map e, b n ≤ ∑ n ∈ Finset.Ioc 0 K, b n := Finset.sum_le_sum_of_subset_of_nonneg h2 (fun n _ _ => (hbpos n).le) rw [← Finset.sum_Ioc_consecutive _ (Nat.zero_le m) (le_max_left m _)] at h3 have h4 := hcon K linarith
Applying the greedy lemma yields l ≥ 3 with 2^l ≥ n₀ and strictly positive endpoints r.
We invoke `op258b_greedy` on b with threshold L₀ = max 3 n₀. Since r(0) = 1 and r is strictly increasing, r(j) ≥ 1 for all j, so each r(j) is a valid positive integer. Furthermore, l ≥ max 3 n₀ implies l ≥ 3 and n₀ ≤ l < 2^l.
uses
op258b_greedy,lt_of_lt_of_le,Nat.zero_le,le_trans,le_max_left,le_max_right,Nat.lt_two_pow_selfobtain ⟨l, hl, r, hr0, hmono, hend, hblk⟩ := op258b_greedy b hbpos hunb (max 3 n₀) have hrpos : ∀ j, 0 < r j := fun j => lt_of_lt_of_le (by omega) (hr0 ▸ hmono.monotone (Nat.zero_le j)) refine ⟨l, le_trans (le_max_left _ _) hl, fun j => ⟨r j, hrpos j⟩, ?_, ?_, ?_, ?_⟩ · exact le_trans (le_trans (le_max_right _ _) hl) (Nat.lt_two_pow_self).le
The restricted sequence r satisfies strict monotonicity, the endpoint bound, and the block sum inequalities.
Strict monotonicity of r on Fin (l + 1) is inherited from ℕ. The value condition a(r(l)) ≥ 1 / 2^(l-1) holds because b(r(l)) = a(r(l)). Finally, each block sum over (r(j), r(j+1)] in ℕ+ equals the sum in ℕ by `op258b_sum_Ioc_pnat`, which is at least 1 / 2^j by the greedy construction.
uses
PNat.eq,PNat.toPNat'_coe,op258b_sum_Ioc_pnat,PNat.mk_coe,le_of_le_of_eq· intro x y hxy show r x < r y exact hmono hxy · show 1 / (2 : ℝ) ^ (l - 1) ≤ a ⟨r l, hrpos l⟩ have : b (r l) = a ⟨r l, hrpos l⟩ := by simp only [hb]; congr 1; exact PNat.eq (PNat.toPNat'_coe (hrpos l)) rw [← this]; exact hend · intro j have h := op258b_sum_Ioc_pnat a ⟨r j, hrpos j⟩ ⟨r (j + 1), hrpos _⟩ have h2 := hblk j.1 j.2 rw [← PNat.mk_coe (r j) (hrpos j), ← PNat.mk_coe (r (j + 1)) (hrpos _)] at h2 exact le_of_le_of_eq h2 h.symm
Finset.sum_nbij'- Two sums over finite sets are equal if there is a bijection between their index sets that preserves the summands.
Finset.mem_Ioc- An element x is in the half-open interval (a, b] if and only if a < x and x ≤ b.
PNat.coe_lt_coe- The coercion from positive integers to natural numbers preserves and reflects strict inequality.
PNat.coe_le_coe- The coercion from positive integers to natural numbers preserves and reflects non-strict inequality.
lt_of_le_of_lt- If a ≤ b and b < c, then a < c.
Nat.zero_le- Every natural number is greater than or equal to 0.
PNat.toPNat'_coe- Coercing `n.toPNat'` to ℕ gives back n when n > 0.
PNat.coe_toPNat'- Converting a positive integer to ℕ and then back via `toPNat'` returns the original positive integer.
Nat.rec- Definition by primitive recursion on the natural numbers.
Nat.find- Returns the smallest natural number satisfying a predicate, given that at least one exists.
Nat.find_spec- The number returned by `Nat.find` satisfies the predicate.
not_lt- For linear orders, not strictly less is equivalent to greater than or equal.
Finset.Ioc_eq_empty- The half-open interval (a, b] is empty if not a < b.
Finset.sum_empty- The sum of any function over the empty set is 0.
strictMono_nat_of_lt_succ- A sequence on ℕ is strictly increasing if each term is strictly less than its successor.
Nat.find_min- Any natural number strictly smaller than `Nat.find` fails the predicate.
Finset.sum_Ioc_succ_top- The sum over (a, b + 1] equals the sum over (a, b] plus the term at b + 1.
one_div_le_one_div_of_le- For positive real numbers, a ≤ b implies 1 / b ≤ 1 / a.
pow_le_pow_right₀- If a ≥ 1 and m ≤ n, then a^m ≤ a^n.
Finset.sum_Ioc_consecutive- The sum over (m, k] splits into the sum over (m, n] plus the sum over (n, k] when m ≤ n ≤ k.
Nat.le_add_right- For natural numbers, n ≤ n + k.
pow_succ- a^(n + 1) = a^n * a.
Finset.sum_le_sum_of_subset_of_nonneg- If s ⊆ t and f is non-negative on t \ s, the sum over s is at most the sum over t.
Finset.Ioc_subset_Ioc_right- If b₁ ≤ b₂, then (a, b₁] ⊆ (a, b₂].
ENNReal.ofReal_tsum_of_nonneg- For a summable non-negative sequence, the extended real sum equals the coercion of the real sum.
ENNReal.ofReal_ne_top- The coercion of any real number to extended non-negative reals is finite (not ⊤).
summable_of_sum_le- A non-negative sequence whose finite partial sums are uniformly bounded is summable.
PNat.coe_injective- Coercion from ℕ+ to ℕ is an injective map.
Finset.sum_map- Summing over the image of an embedding equals summing over the domain.
Finset.sum_congr- If two finite sets are equal and functions agree pointwise on them, their sums are equal.
Finset.le_sup- The value of a function at any element in a finite set is bounded above by the supremum over that set.
le_max_right- b ≤ max a b.
le_max_left- a ≤ max a b.
le_trans- If a ≤ b and b ≤ c, then a ≤ c.
op258b_greedy- For any positive sequence with unbounded tail sums and threshold L₀, there exist l ≥ L₀ and strictly increasing indices r starting at 1 with block sums at least 1 / 2^j and b(r(l)) ≥ 1 / 2^(l-1).
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
Nat.lt_two_pow_self- For any natural number n, n < 2^n.
PNat.eq- Two positive integers are equal if their underlying natural numbers are equal.
op258b_sum_Ioc_pnat- The sum of a on (x, y] in ℕ+ equals the sum of a ∘ toPNat' on (x, y] in ℕ.
PNat.mk_coe- Coercing ⟨n, h⟩ back to ℕ yields n.
le_of_le_of_eq- If a ≤ b and b = c, then a ≤ c.
- The sequence is re-indexed from ℕ+ to ℕ via `Nat.toPNat'` in order to perform the greedy induction with standard 0-indexed natural numbers, and then pulled back to ℕ+ at the end using `op258b_sum_Ioc_pnat`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A sum over an interval of `ℕ+` is the sum over the interval of `ℕ` of `a ∘ toPNat'`. -/theorem op258b_sum_Ioc_pnat (a : ℕ+ → ℝ) (x y : ℕ+) : ∑ i ∈ Finset.Ioc x y, a i = ∑ n ∈ Finset.Ioc (x : ℕ) (y : ℕ), a n.toPNat' := by refine Finset.sum_nbij' (fun i => (i : ℕ)) (fun n => n.toPNat') ?_ ?_ ?_ ?_ ?_ · intro i hi rw [Finset.mem_Ioc] at hi ⊢ exact ⟨PNat.coe_lt_coe _ _ |>.mpr hi.1, PNat.coe_le_coe _ _ |>.mpr hi.2⟩ · intro n hn rw [Finset.mem_Ioc] at hn ⊢ have hn0 : 0 < n := lt_of_le_of_lt (Nat.zero_le _) hn.1 refine ⟨?_, ?_⟩ · rw [← PNat.coe_lt_coe, PNat.toPNat'_coe hn0]; exact hn.1 · rw [← PNat.coe_le_coe, PNat.toPNat'_coe hn0]; exact hn.2 · intro i _ exact PNat.coe_toPNat' i · intro n hn rw [Finset.mem_Ioc] at hn exact PNat.toPNat'_coe (lt_of_le_of_lt (Nat.zero_le _) hn.1) · intro i _ rw [PNat.coe_toPNat']/-- Greedy blocks over `ℕ`: if all tail sums of a positive sequence are unbounded, then forevery `L₀` there are `l ≥ L₀` and strictly increasing `r` with `r 0 = 1`, block sums at least`1 / 2^j` and `1 / 2^(l-1) ≤ b (r l)`. -/theorem op258b_greedy (b : ℕ → ℝ) (hpos : ∀ n, 0 < b n) (hunb : ∀ m : ℕ, ∀ C : ℝ, ∃ k, C ≤ ∑ n ∈ Finset.Ioc m k, b n) (L₀ : ℕ) : ∃ l, L₀ ≤ l ∧ ∃ r : ℕ → ℕ, r 0 = 1 ∧ StrictMono r ∧ 1 / (2 : ℝ) ^ (l - 1) ≤ b (r l) ∧ ∀ j, j < l → 1 / (2 : ℝ) ^ j ≤ ∑ n ∈ Finset.Ioc (r j) (r (j + 1)), b n := by classical have hex : ∀ m j : ℕ, ∃ k, 1 / (2 : ℝ) ^ j ≤ ∑ n ∈ Finset.Ioc m k, b n := fun m j => hunb m _ let r : ℕ → ℕ := fun j => Nat.rec 1 (fun j rj => Nat.find (hex rj j)) j have hr0 : r 0 = 1 := rfl have hrs : ∀ j, r (j + 1) = Nat.find (hex (r j) j) := fun j => rfl have hspec : ∀ j, 1 / (2 : ℝ) ^ j ≤ ∑ n ∈ Finset.Ioc (r j) (r (j + 1)), b n := by intro j; rw [hrs]; exact Nat.find_spec (hex (r j) j) have hlt : ∀ j, r j < r (j + 1) := by intro j by_contra hc rw [not_lt] at hc have := hspec j rw [Finset.Ioc_eq_empty (by omega), Finset.sum_empty] at this have : (0 : ℝ) < 1 / 2 ^ j := by positivity linarith have hmono : StrictMono r := strictMono_nat_of_lt_succ hlt -- the block sum overshoots by at most its last term have hover : ∀ j, ∑ n ∈ Finset.Ioc (r j) (r (j + 1)), b n < 1 / (2 : ℝ) ^ j + b (r (j + 1)) := by intro j obtain ⟨k, hk⟩ : ∃ k, r (j + 1) = k + 1 := ⟨r (j + 1) - 1, by have := hlt j; omega⟩ have hjk : r j ≤ k := by have := hlt j; omega have hmin : ¬ (1 / (2 : ℝ) ^ j ≤ ∑ n ∈ Finset.Ioc (r j) k, b n) := by have := Nat.find_min (hex (r j) j) (m := k) (by rw [← hrs]; omega) exact this rw [hk, Finset.sum_Ioc_succ_top hjk] linarith [not_le.mp hmin] suffices hl : ∃ l, L₀ ≤ l ∧ 1 / (2 : ℝ) ^ (l - 1) ≤ b (r l) by obtain ⟨l, hl, hb⟩ := hl exact ⟨l, hl, r, hr0, hmono, hb, fun j _ => hspec j⟩ by_contra hcon push_neg at hcon -- every block from `L₀` on is small have hsmall : ∀ i, ∑ n ∈ Finset.Ioc (r (L₀ + i)) (r (L₀ + i + 1)), b n ≤ 2 / (2 : ℝ) ^ i := by intro i have h1 := hover (L₀ + i) have h2 := hcon (L₀ + i + 1) (by omega) rw [show L₀ + i + 1 - 1 = L₀ + i by omega] at h2 have h3 : 1 / (2 : ℝ) ^ (L₀ + i) ≤ 1 / 2 ^ i := by apply one_div_le_one_div_of_le (by positivity) exact pow_le_pow_right₀ (by norm_num) (by omega) have h4 : 2 / (2 : ℝ) ^ i = 1 / 2 ^ i + 1 / 2 ^ i := by ring linarith have htot : ∀ k, ∑ n ∈ Finset.Ioc (r L₀) (r (L₀ + k)), b n ≤ 4 - 4 / (2 : ℝ) ^ k := by intro k induction k with | zero => simp | succ k ih => rw [← Finset.sum_Ioc_consecutive _ (hmono.monotone (Nat.le_add_right L₀ k)) (hmono.monotone (by omega : L₀ + k ≤ L₀ + (k + 1)))] have := hsmall k rw [show L₀ + k + 1 = L₀ + (k + 1) by omega] at this have h5 : 4 - 4 / (2 : ℝ) ^ (k + 1) = 4 - 4 / 2 ^ k + 2 / 2 ^ k := by rw [pow_succ]; field_simp; ring linarith obtain ⟨k, hk⟩ := hunb (r L₀) 5 have hkle : k ≤ r (L₀ + k) := by have := hmono.id_le (L₀ + k); simp only [id] at this; omega have hsub : ∑ n ∈ Finset.Ioc (r L₀) k, b n ≤ ∑ n ∈ Finset.Ioc (r L₀) (r (L₀ + k)), b n := Finset.sum_le_sum_of_subset_of_nonneg (Finset.Ioc_subset_Ioc_right hkle) (fun n _ _ => (hpos n).le) have h6 := htot k have h7 : 0 < 4 / (2 : ℝ) ^ k := by positivity linarith/-- For any positive antitone sequence with divergent ENNReal sum and threshold n_0, there exists l >= 3 with 2^l >= n_0 and strictly increasing block endpoints r : Fin (l+1) -> PNat such that a(r(l)) >= 1 / 2^{l-1} and each block has sum >= 1 / 2^j. -/theorem op_258_exists_divergent_block_indices (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a) (hsum : (∑' i : ℕ+, ENNReal.ofReal (a i)) = ⊤) (n₀ : ℕ) : ∃ (l : ℕ) (hl : 3 ≤ l) (r : Fin (l + 1) → ℕ+), n₀ ≤ 2^l ∧ (StrictMono r) ∧ (1 / (2 : ℝ)^(l - 1) ≤ a (r ⟨l, by omega⟩)) ∧ (∀ j : Fin l, 1 / (2 : ℝ)^(j : ℕ) ≤ ∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), a i) := by classical set b : ℕ → ℝ := fun n => a n.toPNat' with hb have hbpos : ∀ n, 0 < b n := fun n => hpos _ have hns : ¬ Summable a := by intro hs rw [← ENNReal.ofReal_tsum_of_nonneg (fun i => (hpos i).le) hs] at hsum exact ENNReal.ofReal_ne_top hsum have hunb : ∀ m : ℕ, ∀ C : ℝ, ∃ k, C ≤ ∑ n ∈ Finset.Ioc m k, b n := by intro m C by_contra hcon push_neg at hcon apply hns refine summable_of_sum_le (c := ∑ n ∈ Finset.Ioc 0 m, b n + C) (fun i => (hpos i).le) ?_ intro u set e : ℕ+ ↪ ℕ := ⟨fun i => (i : ℕ), PNat.coe_injective⟩ set K := max m (u.sup fun i => (i : ℕ)) have h1 : ∑ i ∈ u, a i = ∑ n ∈ u.map e, b n := by rw [Finset.sum_map] exact Finset.sum_congr rfl (fun i _ => by simp [hb, e, PNat.coe_toPNat']) have h2 : u.map e ⊆ Finset.Ioc 0 K := by intro n hn obtain ⟨i, hi, rfl⟩ := Finset.mem_map.mp hn simp only [Finset.mem_Ioc, e, Function.Embedding.coeFn_mk] exact ⟨i.pos, le_trans (Finset.le_sup (f := fun i : ℕ+ => (i : ℕ)) hi) (le_max_right _ _)⟩ have h3 : ∑ n ∈ u.map e, b n ≤ ∑ n ∈ Finset.Ioc 0 K, b n := Finset.sum_le_sum_of_subset_of_nonneg h2 (fun n _ _ => (hbpos n).le) rw [← Finset.sum_Ioc_consecutive _ (Nat.zero_le m) (le_max_left m _)] at h3 have h4 := hcon K linarith obtain ⟨l, hl, r, hr0, hmono, hend, hblk⟩ := op258b_greedy b hbpos hunb (max 3 n₀) have hrpos : ∀ j, 0 < r j := fun j => lt_of_lt_of_le (by omega) (hr0 ▸ hmono.monotone (Nat.zero_le j)) refine ⟨l, le_trans (le_max_left _ _) hl, fun j => ⟨r j, hrpos j⟩, ?_, ?_, ?_, ?_⟩ · exact le_trans (le_trans (le_max_right _ _) hl) (Nat.lt_two_pow_self).le · intro x y hxy show r x < r y exact hmono hxy · show 1 / (2 : ℝ) ^ (l - 1) ≤ a ⟨r l, hrpos l⟩ have : b (r l) = a ⟨r l, hrpos l⟩ := by simp only [hb]; congr 1; exact PNat.eq (PNat.toPNat'_coe (hrpos l)) rw [← this]; exact hend · intro j have h := op258b_sum_Ioc_pnat a ⟨r j, hrpos j⟩ ⟨r (j + 1), hrpos _⟩ have h2 := hblk j.1 j.2 rw [← PNat.mk_coe (r j) (hrpos j), ← PNat.mk_coe (r (j + 1)) (hrpos _)] at h2 exact le_of_le_of_eq h2 h.symm