op_258_capacity_floor_ge
For any natural l ≥ 3 and real x ≥ 1 / 2^{l - 1}, 2^{2l - 2} * x ≤ floor(x * C(2^l, 2)).
Statement
theorem op_258_capacity_floor_ge (l : ℕ) (hl : 3 ≤ l) (x : ℝ) (hx : 1 / (2 : ℝ)^(l - 1) ≤ x) :
(2 : ℝ)^(2 * l - 2) * x ≤ ((Nat.floor (x * (((2^l).choose 2 : ℕ) : ℝ)) : ℕ) : ℝ)- Source
- step towards op_258_exists_divergent_capacity_covering
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op_258_choose_two_sub_powFor any natural l ≥ 3, 2^{l-1} ≤ C(2^l, 2) - 2^{2l - 2}.
- 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 proof establishes 2^{2l - 2} * x ≤ ⌊x * C(2^l, 2)⌋ by bounding 2^{2l - 2} * x below x * C(2^l, 2) - 1, which in turn is strictly less than ⌊x * C(2^l, 2)⌋ by the definition of the floor function. The intermediate bound follows by multiplying the algebraic gap C(2^l, 2) - 2^{2l - 2} ≥ 2^{l - 1} by the hypothesis x ≥ 1 / 2^{l - 1}, yielding x * (C(2^l, 2) - 2^{2l - 2}) ≥ x * 2^{l - 1} ≥ 1.
2^{l - 1} ≤ C(2^l, 2) - 2^{2l - 2}
Apply the known lemma op_258_choose_two_sub_pow to the hypothesis l ≥ 3 to lower-bound the gap between C(2^l, 2) and 2^{2l - 2}.
uses
op_258_choose_two_sub_powhave h1 : (2 : ℝ) ^ (l - 1) ≤ (((2^l).choose 2 : ℕ) : ℝ) - (2 : ℝ) ^ (2 * l - 2) := op_258_choose_two_sub_pow l hl1 ≤ x * 2^{l - 1}
Since 2^{l - 1} is strictly positive, clearing the denominator in 1 / 2^{l - 1} ≤ x via div_le_iff₀ yields 1 ≤ x * 2^{l - 1}.
uses
div_le_iff₀have hpos : (0 : ℝ) < (2 : ℝ) ^ (l - 1) := by positivity have hxA : 1 ≤ x * (2 : ℝ) ^ (l - 1) := by have := (div_le_iff₀ hpos).mp hx linarith
2^{2l - 2} * x ≤ x * C(2^l, 2) - 1
Multiplying the gap C(2^l, 2) - 2^{2l - 2} ≥ 2^{l - 1} by x ≥ 0 gives x * C(2^l, 2) - 2^{2l - 2} * x ≥ x * 2^{l - 1} ≥ 1, which rearranges to the desired inequality. The nlinarith tactic automates this non-linear deduction.
have h2 : (2 : ℝ) ^ (2 * l - 2) * x ≤ x * (((2^l).choose 2 : ℕ) : ℝ) - 1 := by nlinarith
x * C(2^l, 2) - 1 < ⌊x * C(2^l, 2)⌋
This is the standard lower bound for the integer floor: for any real number y, y - 1 < ⌊y⌋, here applied with y = x * C(2^l, 2).
uses
Nat.sub_one_lt_floorhave h3 : x * (((2^l).choose 2 : ℕ) : ℝ) - 1 < ((Nat.floor (x * (((2^l).choose 2 : ℕ) : ℝ)) : ℕ) : ℝ) := Nat.sub_one_lt_floor _2^{2l - 2} * x ≤ ⌊x * C(2^l, 2)⌋
Combine 2^{2l - 2} * x ≤ x * C(2^l, 2) - 1 and x * C(2^l, 2) - 1 < ⌊x * C(2^l, 2)⌋ by transitivity (lt_of_le_of_lt), then weaken the strict inequality to a non-strict one (le_of_lt).
uses
le_of_lt,lt_of_le_of_ltexact le_of_lt (lt_of_le_of_lt h2 h3)
op_258_choose_two_sub_pow- For any natural l ≥ 3, the difference C(2^l, 2) - 2^{2l - 2} is at least 2^{l - 1}.
div_le_iff₀- For c > 0, b / c ≤ a if and only if b ≤ a * c.
Nat.sub_one_lt_floor- For any real number a, a - 1 < ⌊a⌋.
lt_of_le_of_lt- If a ≤ b and b < c, then a < c.
le_of_lt- If a < b, then a ≤ b.
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.
/-- For l ≥ 3 and x ≥ 1/2^{l-1}, the integer floor capacity floor(x * C(2^l, 2)) is at least 2^{2l - 2} * x. -/theorem op_258_capacity_floor_ge (l : ℕ) (hl : 3 ≤ l) (x : ℝ) (hx : 1 / (2 : ℝ)^(l - 1) ≤ x) : (2 : ℝ)^(2 * l - 2) * x ≤ ((Nat.floor (x * (((2^l).choose 2 : ℕ) : ℝ)) : ℕ) : ℝ) := by have h1 : (2 : ℝ) ^ (l - 1) ≤ (((2^l).choose 2 : ℕ) : ℝ) - (2 : ℝ) ^ (2 * l - 2) := op_258_choose_two_sub_pow l hl have hpos : (0 : ℝ) < (2 : ℝ) ^ (l - 1) := by positivity have hxA : 1 ≤ x * (2 : ℝ) ^ (l - 1) := by have := (div_le_iff₀ hpos).mp hx linarith have h2 : (2 : ℝ) ^ (2 * l - 2) * x ≤ x * (((2^l).choose 2 : ℕ) : ℝ) - 1 := by nlinarith have h3 : x * (((2^l).choose 2 : ℕ) : ℝ) - 1 < ((Nat.floor (x * (((2^l).choose 2 : ℕ) : ℝ)) : ℕ) : ℝ) := Nat.sub_one_lt_floor _ exact le_of_lt (lt_of_le_of_lt h2 h3)