op_258_exists_divergent_capacity_covering
If a positive antitone profile a has infinite sum in ENNReal, then for any threshold n₀, there exists l ≥ 1 with 2^l ≥ n₀, pairwise disjoint sets of colours I_j for each hypercube layer j < l, and integer capacities cap(i) ≤ a_i * C(2^l, 2) whose sum on each layer j is at least 2^{2l - 2 - j}.
Statement
theorem op_258_exists_divergent_capacity_covering
(a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a)
(hsum : (∑' i : ℕ+, ENNReal.ofReal (a i)) = ⊤) (n₀ : ℕ) :
∃ (l : ℕ) (hl : 1 ≤ l) (I : Fin l → Finset ℕ+) (cap : ℕ+ → ℕ),
n₀ ≤ 2^l ∧
(∀ j₁ j₂ : Fin l, j₁ ≠ j₂ → Disjoint (I j₁) (I j₂)) ∧
(∀ j : Fin l, ∀ i ∈ I j, (cap i : ℝ) ≤ a i * ((2^l).choose 2 : ℝ)) ∧
(∀ j : Fin l, 2^(2 * l - 2 - (j : ℕ)) ≤ ∑ i ∈ I j, cap i)- Source
- step towards op_258_sum_ne_top_of_forces_three
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- op_258_choose_two_sub_powFor any natural l ≥ 3, 2^{l-1} ≤ C(2^l, 2) - 2^{2l - 2}.
- op_258_capacity_floor_geFor any natural l ≥ 3 and real x ≥ 1 / 2^{l - 1}, 2^{2l - 2} * x ≤ floor(x * C(2^l, 2)).
- op_258_exists_divergent_block_indicesFor any positive antitone sequence a : ℕ+ → ℝ with divergent sum and any n₀, there exist l ≥ 3 with 2^l ≥ n₀ and strictly increasing r :…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- op_258_sum_ne_top_of_forces_threeIf a positive antitone profile a forces a monochromatic triangle K_3 on sufficiently large complete graphs, then the infinite sum of a_i…
The proof, explained
The proof uses a block-partitioning lemma (`op_258_exists_divergent_block_indices`) to obtain a hypercube dimension l ≥ 3 and strictly increasing indices r₀ < r₁ < … < r_l such that 2^l ≥ n₀, a(r_l) ≥ 1/2^(l-1), and each block I_j = (r_j, r_{j+1}] has profile sum at least 1/2^j. The layer sets are chosen as these blocks I_j, which are pairwise disjoint by the monotonicity of r, and the capacities are set to cap(i) = ⌊a_i * C(2^l, 2)⌋₊. Because a is antitone, every i ∈ I_j satisfies a_i ≥ a(r_l) ≥ 1/2^(l-1), which by `op_258_capacity_floor_ge` guarantees cap(i) ≥ 2^(2l - 2) * a_i; summing this over I_j produces the required layer capacity lower bound 2^(2l - 2 - j).
There exist a dimension l ≥ 3 with 2^l ≥ n₀ and strictly increasing indices r₀ < r₁ < … < r_l partitioning an initial segment into blocks of sufficient weight.
We invoke the lemma `op_258_exists_divergent_block_indices`. Using the infinite sum and antitonicity of a, it produces l ≥ 3 with 2^l ≥ n₀ and a strictly increasing sequence of indices r : Fin (l + 1) → ℕ+ such that a(r_l) ≥ 1/2^(l-1) and the sum of a over each block (r_j, r_{j+1}] is at least 1/2^j.
uses
op_258_exists_divergent_block_indicesclassical obtain ⟨l, hl3, r, hn0, hmono, hend, hblk⟩ := op_258_exists_divergent_block_indices a hpos hanti hsum n₀Provide candidate witnesses: the dimension l, the layer sets I_j = (r_j, r_{j+1}], and the capacities cap(i) = ⌊a_i * C(2^l, 2)⌋₊.
We instantiate the existential quantifier with l (where 1 ≤ l follows from 3 ≤ l), sets I_j defined as the half-open intervals (r_j, r_{j+1}], and capacities given by the floor of a_i * C(2^l, 2). The condition n₀ ≤ 2^l holds directly from the previous step, leaving the disjointness of the blocks, the capacity upper bound, and the layer capacity lower bound to be verified.
refine ⟨l, by omega, fun j : Fin l => Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), fun i => ⌊a i * ((2^l).choose 2 : ℝ)⌋₊, hn0, ?_, ?_, ?_⟩
The sets I_{j₁} and I_{j₂} are pairwise disjoint whenever j₁ ≠ j₂.
Assume without loss of generality that j₁ < j₂ (the case j₂ < j₁ is symmetric). Then j₁ + 1 ≤ j₂, so strict monotonicity of r implies r_{j₁+1} ≤ r_{j₂}. If an element x belonged to both I_{j₁} and I_{j₂}, we would have x ≤ r_{j₁+1} ≤ r_{j₂} from x ∈ I_{j₁}, but also r_{j₂} < x from x ∈ I_{j₂}, a contradiction.
uses
Finset.disjoint_left,Finset.mem_Ioc,lt_or_gt_of_ne,Fin.le_def,Nat.succ_le_of_lt,not_le.mpr,le_trans· intro j₁ j₂ hne rw [Finset.disjoint_left] intro x hx1 hx2 rw [Finset.mem_Ioc] at hx1 hx2 rcases lt_or_gt_of_ne hne with hlt | hgt · have hlt' : j₁.1 < j₂.1 := hlt have hle : (⟨j₁.1+1, by omega⟩ : Fin (l+1)) ≤ ⟨j₂.1, by omega⟩ := by rw [Fin.le_def]; exact Nat.succ_le_of_lt hlt' have h1 : r ⟨j₁.1 + 1, by omega⟩ ≤ r ⟨j₂.1, by omega⟩ := hmono.monotone hle exact (not_le.mpr hx2.1) (le_trans hx1.2 h1) · have hlt' : j₂.1 < j₁.1 := hgt have hle : (⟨j₂.1+1, by omega⟩ : Fin (l+1)) ≤ ⟨j₁.1, by omega⟩ := by rw [Fin.le_def]; exact Nat.succ_le_of_lt hlt' have h1 : r ⟨j₂.1 + 1, by omega⟩ ≤ r ⟨j₁.1, by omega⟩ := hmono.monotone hle exact (not_le.mpr hx1.1) (le_trans hx2.2 h1)
For every layer j and element i ∈ I_j, cap(i) ≤ a_i * C(2^l, 2).
Since a_i > 0 and the binomial coefficient C(2^l, 2) is non-negative, their product is non-negative. The inequality follows directly from the property of the floor function that ⌊x⌋₊ ≤ x for non-negative real numbers.
uses
Nat.floor_le,mul_nonneg,le_of_lt· intro j i hi exact Nat.floor_le (mul_nonneg (le_of_lt (hpos i)) (by positivity))
For each element i ∈ I_j, the capacity satisfies the pointwise lower bound 2^(2l - 2) * a_i ≤ cap(i).
For any i ∈ I_j = (r_j, r_{j+1}], we have i ≤ r_{j+1} ≤ r_l because j + 1 ≤ l. Since a is antitone, a_i ≥ a(r_l) ≥ 1/2^(l-1). Applying `op_258_capacity_floor_ge` with this lower bound on a_i yields 2^(2l - 2) * a_i ≤ ⌊a_i * C(2^l, 2)⌋₊ = cap(i).
uses
Finset.mem_Ioc,Fin.le_def,Nat.succ_le_of_lt,le_trans,op_258_capacity_floor_ge· intro j have hle : ∀ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), (2:ℝ)^(2*l-2) * a i ≤ ((⌊a i * ((2^l).choose 2 : ℝ)⌋₊ : ℕ) : ℝ) := by intro i hi rw [Finset.mem_Ioc] at hi have hi_le : i ≤ r ⟨l, by omega⟩ := by have h1 : r ⟨j.1 + 1, by omega⟩ ≤ r ⟨l, by omega⟩ := by apply hmono.monotone rw [Fin.le_def]; exact Nat.succ_le_of_lt j.2 exact le_trans hi.2 h1 have hai : 1 / (2:ℝ)^(l-1) ≤ a i := le_trans hend (hanti hi_le) exact op_258_capacity_floor_ge l hl3 (a i) hai
For each layer j, the sum of capacities over I_j is at least 2^(2l - 2 - j).
Summing the pointwise lower bound over all i ∈ I_j gives 2^(2l - 2) * ∑_{i ∈ I_j} a_i ≤ ∑_{i ∈ I_j} cap(i). Since ∑_{i ∈ I_j} a_i ≥ 1/2^j by the block construction, multiplying by 2^(2l - 2) yields 2^(2l - 2) * (1/2^j) ≤ ∑_{i ∈ I_j} cap(i). Simplifying 2^(2l - 2) * 2^(-j) = 2^(2l - 2 - j) and casting the inequality to natural numbers completes the proof.
uses
Finset.sum_le_sum,Finset.mul_sum,mul_le_mul_of_nonneg_left,le_trans,one_div,pow_sub₀have hsum_le := Finset.sum_le_sum hle rw [← Finset.mul_sum] at hsum_le have key : (2:ℝ)^(2*l-2) * (1/(2:ℝ)^(j:ℕ)) ≤ (2:ℝ)^(2*l-2) * (∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), a i) := mul_le_mul_of_nonneg_left (hblk j) (by positivity) have hstep : (2:ℝ)^(2*l-2) * (1/(2:ℝ)^(j:ℕ)) ≤ ∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), ((⌊a i * ((2^l).choose 2 : ℝ)⌋₊ : ℕ) : ℝ) := le_trans key hsum_le rw [one_div, ← pow_sub₀ (2:ℝ) (by norm_num) (by omega)] at hstep exact_mod_cast hstep
op_258_exists_divergent_block_indices- For a positive antitone sequence with infinite sum and a threshold n₀, there exists l ≥ 3 with 2^l ≥ n₀ and strictly increasing indices r₀ < r₁ < … < r_l such that a(r_l) ≥ 1/2^(l-1) and the sum of a over each block (r_j, r_{j+1}] is at least 1/2^j.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_Ioc- An element x belongs to the half-open interval (a, b] if and only if a < x and x ≤ b.
lt_or_gt_of_ne- In a linear order, two unequal elements satisfy a < b or b < a.
Fin.le_def- In Fin n, an element a is at most b if and only if the underlying natural numbers satisfy a ≤ b.
Nat.succ_le_of_lt- For natural numbers, if n < m then n + 1 ≤ m.
not_le.mpr- If a < b, then it is not the case that b ≤ a.
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Nat.floor_le- For a non-negative real x, its floor ⌊x⌋₊ satisfies ⌊x⌋₊ ≤ x.
mul_nonneg- The product of two non-negative numbers is non-negative.
le_of_lt- A strict inequality a < b implies the weak inequality a ≤ b.
op_258_capacity_floor_ge- For l ≥ 3, if x ≥ 1/2^(l-1), then 2^(2l - 2) * x ≤ ⌊x * C(2^l, 2)⌋₊.
Finset.sum_le_sum- If f(i) ≤ g(i) for all i in a finite set s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ s} g(i).
Finset.mul_sum- Multiplication distributes over finite sums: a * ∑_{i ∈ s} f(i) = ∑_{i ∈ s} a * f(i).
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c by a non-negative scalar a preserves the inequality: a * b ≤ a * c.
one_div- Division by a equals multiplication by its inverse: 1 / a = a⁻¹.
pow_sub₀- For a nonzero base a and n ≤ m, a^(m - n) = a^m * (a^n)⁻¹.
- Index arithmetic and bounds checking for `Fin` instances are handled by `omega`, while non-negativity conditions are discharged by `positivity`.
- The final step uses `exact_mod_cast` to cast the lower bound inequality from real numbers to natural numbers.
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.
/-- Existence of divergent profile capacity coverings for hypercube layers. -/theorem op_258_exists_divergent_capacity_covering (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a) (hsum : (∑' i : ℕ+, ENNReal.ofReal (a i)) = ⊤) (n₀ : ℕ) : ∃ (l : ℕ) (hl : 1 ≤ l) (I : Fin l → Finset ℕ+) (cap : ℕ+ → ℕ), n₀ ≤ 2^l ∧ (∀ j₁ j₂ : Fin l, j₁ ≠ j₂ → Disjoint (I j₁) (I j₂)) ∧ (∀ j : Fin l, ∀ i ∈ I j, (cap i : ℝ) ≤ a i * ((2^l).choose 2 : ℝ)) ∧ (∀ j : Fin l, 2^(2 * l - 2 - (j : ℕ)) ≤ ∑ i ∈ I j, cap i) := by classical obtain ⟨l, hl3, r, hn0, hmono, hend, hblk⟩ := op_258_exists_divergent_block_indices a hpos hanti hsum n₀ refine ⟨l, by omega, fun j : Fin l => Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), fun i => ⌊a i * ((2^l).choose 2 : ℝ)⌋₊, hn0, ?_, ?_, ?_⟩ · intro j₁ j₂ hne rw [Finset.disjoint_left] intro x hx1 hx2 rw [Finset.mem_Ioc] at hx1 hx2 rcases lt_or_gt_of_ne hne with hlt | hgt · have hlt' : j₁.1 < j₂.1 := hlt have hle : (⟨j₁.1+1, by omega⟩ : Fin (l+1)) ≤ ⟨j₂.1, by omega⟩ := by rw [Fin.le_def]; exact Nat.succ_le_of_lt hlt' have h1 : r ⟨j₁.1 + 1, by omega⟩ ≤ r ⟨j₂.1, by omega⟩ := hmono.monotone hle exact (not_le.mpr hx2.1) (le_trans hx1.2 h1) · have hlt' : j₂.1 < j₁.1 := hgt have hle : (⟨j₂.1+1, by omega⟩ : Fin (l+1)) ≤ ⟨j₁.1, by omega⟩ := by rw [Fin.le_def]; exact Nat.succ_le_of_lt hlt' have h1 : r ⟨j₂.1 + 1, by omega⟩ ≤ r ⟨j₁.1, by omega⟩ := hmono.monotone hle exact (not_le.mpr hx1.1) (le_trans hx2.2 h1) · intro j i hi exact Nat.floor_le (mul_nonneg (le_of_lt (hpos i)) (by positivity)) · intro j have hle : ∀ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), (2:ℝ)^(2*l-2) * a i ≤ ((⌊a i * ((2^l).choose 2 : ℝ)⌋₊ : ℕ) : ℝ) := by intro i hi rw [Finset.mem_Ioc] at hi have hi_le : i ≤ r ⟨l, by omega⟩ := by have h1 : r ⟨j.1 + 1, by omega⟩ ≤ r ⟨l, by omega⟩ := by apply hmono.monotone rw [Fin.le_def]; exact Nat.succ_le_of_lt j.2 exact le_trans hi.2 h1 have hai : 1 / (2:ℝ)^(l-1) ≤ a i := le_trans hend (hanti hi_le) exact op_258_capacity_floor_ge l hl3 (a i) hai have hsum_le := Finset.sum_le_sum hle rw [← Finset.mul_sum] at hsum_le have key : (2:ℝ)^(2*l-2) * (1/(2:ℝ)^(j:ℕ)) ≤ (2:ℝ)^(2*l-2) * (∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), a i) := mul_le_mul_of_nonneg_left (hblk j) (by positivity) have hstep : (2:ℝ)^(2*l-2) * (1/(2:ℝ)^(j:ℕ)) ≤ ∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), ((⌊a i * ((2^l).choose 2 : ℝ)⌋₊ : ℕ) : ℝ) := le_trans key hsum_le rw [one_div, ← pow_sub₀ (2:ℝ) (by norm_num) (by omega)] at hstep exact_mod_cast hstep