AFTD Auto-Formalizing Theoretical Domains

op_258_capacity_floor_ge

theoremverified

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
Used by 1

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.

  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}.

    lines 4–5

    uses op_258_choose_two_sub_pow

      have h1 : (2 : ℝ) ^ (l - 1) ≤ (((2^l).choose 2 : ℕ) : ℝ) - (2 : ℝ) ^ (2 * l - 2) :=
        op_258_choose_two_sub_pow l hl
  2. 1 ≤ 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}.

    lines 6–9

    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
  3. 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.

    lines 10–11

      have h2 : (2 : ℝ) ^ (2 * l - 2) * x ≤ x * (((2^l).choose 2 : ℕ) : ℝ) - 1 := by
        nlinarith
  4. 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).

    lines 12–13

    uses Nat.sub_one_lt_floor

      have h3 : x * (((2^l).choose 2 : ℕ) : ℝ) - 1 < ((Nat.floor (x * (((2^l).choose 2 : ℕ) : ℝ)) : ℕ) : ℝ) :=
        Nat.sub_one_lt_floor _
  5. 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).

    line 14

    uses le_of_lt, lt_of_le_of_lt

      exact 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

/-- 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)
See it in the graphDiscuss this resultChallenge it