AFTD Auto-Formalizing Theoretical Domains

biased_bit_critical_cost_le_zero_shift

theoremverified

For any bias parameter p satisfying 1 / 2 < p and p < 1, the critical cost biased_bit_critical_cost p is at most ((1 - p) / p) / (1 - (1 - p) / p).

Statement

theorem biased_bit_critical_cost_le_zero_shift (p : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1) :
    biased_bit_critical_cost p ≤ ((1 - p) / p) / (1 - (1 - p) / p)
Source
arXiv:2611.16066 Thm 5.4
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • biased_bit_critical_costFor a bias parameter p : ℝ, biased_bit_critical_cost p is defined as the real infimum (sInf) of the set of values (l : ℝ) + a * (2 * a ^ l…

Read back from the Lean

For every real number $p$ such that $1/2 < p$ and $p < 1$, biased_bit_critical_cost p is less than or equal to $\frac{(1 - p)/p}{1 - (1 - p)/p}$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The critical cost biased_bit_critical_cost p is defined as the infimum over l ∈ ℕ of l + a * (2 * a ^ l - 1) / (1 - a), where a = (1 - p) / p. Since 1 / 2 < p < 1, the ratio a lies in (0, 1). The proof shows that the set of costs is bounded below by -a / (1 - a) and that evaluating at l = 0 yields exactly a / (1 - a). By the universal property of the infimum (csInf_le), the critical cost is at most this value.

  1. Unfold the definition of biased_bit_critical_cost and define the parameter a := (1 - p) / p.

    Unfolding biased_bit_critical_cost expresses the critical cost as the infimum over l ∈ ℕ of l + a * (2 * a ^ l - 1) / (1 - a), where a is defined as (1 - p) / p.

    lines 4–5

      unfold biased_bit_critical_cost
      let a := (1 - p) / p
  2. The parameter bounds 0 < p, 0 < a < 1, and 0 < 1 - a hold.

    From 1 / 2 < p < 1, linear arithmetic gives 0 < p and 0 < 1 - p. Since both the numerator and denominator are positive, 0 < a by div_pos. Since p is positive, a < 1 is equivalent to 1 - p < p by div_lt_one, which holds because p > 1 / 2. Then a < 1 implies 1 - a > 0.

    lines 6–11

    uses div_pos, div_lt_one

      have hp0 : 0 < p := by linarith
      have ha0 : 0 < a := div_pos (by linarith) hp0
      have ha1 : a < 1 := by
        rw [div_lt_one hp0]
        linarith
      have h1a : 0 < 1 - a := by linarith
  3. The set of costs {l + a * (2 * a ^ l - 1) / (1 - a) | l ∈ ℕ} is bounded below by -a / (1 - a).

    For any l ∈ ℕ, the integer part l is nonnegative (Nat.cast_nonneg), and a ^ l ≥ 0 because a ≥ 0 (le_of_lt and pow_nonneg). Since 1 - a > 0, clearing denominators via div_le_div_iff_of_pos_right reduces the lower bound -a / (1 - a) ≤ a * (2 * a ^ l - 1) / (1 - a) to -a ≤ a * (2 * a ^ l - 1), which holds because 2 * a ^ (l + 1) ≥ 0. Adding l ≥ 0 confirms -a / (1 - a) is a lower bound for every element of the set.

    lines 12–21

    uses Nat.cast_nonneg, pow_nonneg, le_of_lt, div_le_div_iff_of_pos_right

      have hbdd : BddBelow (Set.range fun (l : ℕ) => (l : ℝ) + a * (2 * a ^ l - 1) / (1 - a)) := by
        use (-a / (1 - a))
        rintro x ⟨l, rfl⟩
        dsimp
        have hl : 0 ≤ (l : ℝ) := Nat.cast_nonneg l
        have hal : 0 ≤ a ^ l := pow_nonneg (le_of_lt ha0) l
        have h_frac : -a / (1 - a) ≤ a * (2 * a ^ l - 1) / (1 - a) := by
          rw [div_le_div_iff_of_pos_right h1a]
          nlinarith
        linarith
  4. The value a / (1 - a) belongs to the range of the cost function.

    Choosing l = 0, the expression evaluates to 0 + a * (2 * a ^ 0 - 1) / (1 - a) = a * (2 - 1) / (1 - a) = a / (1 - a), verified by polynomial ring simplification.

    lines 22–25

      have hmem : a / (1 - a) ∈ Set.range (fun (l : ℕ) => (l : ℝ) + a * (2 * a ^ l - 1) / (1 - a)) := by
        use 0
        dsimp
        ring
  5. The critical cost biased_bit_critical_cost p is at most ((1 - p) / p) / (1 - (1 - p) / p).

    Since the set of costs is bounded below and contains a / (1 - a), the greatest lower bound (sInf) is at most a / (1 - a) by csInf_le.

    line 26

    uses csInf_le

      exact csInf_le hbdd hmem
div_pos
The quotient of two positive elements is positive.
div_lt_one
For a positive denominator, a fraction is strictly less than 1 if and only if its numerator is strictly less than its denominator.
Nat.cast_nonneg
The natural number cast into an ordered semiring is nonnegative.
pow_nonneg
A nonnegative element raised to any natural power is nonnegative.
le_of_lt
A strict inequality a < b implies the non-strict inequality a ≤ b.
div_le_div_iff_of_pos_right
For a positive denominator c, a / c ≤ b / c is equivalent to a ≤ b.
csInf_le
In a conditionally complete lattice, the infimum of a set bounded below is at most any element in the set.

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

/-- The critical cost c_crit(p) is at most the shift l = 0 evaluation a / (1 - a). -/theorem biased_bit_critical_cost_le_zero_shift (p : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1) :    biased_bit_critical_cost p ≤ ((1 - p) / p) / (1 - (1 - p) / p) := by  unfold biased_bit_critical_cost  let a := (1 - p) / p  have hp0 : 0 < p := by linarith  have ha0 : 0 < a := div_pos (by linarith) hp0  have ha1 : a < 1 := by    rw [div_lt_one hp0]    linarith  have h1a : 0 < 1 - a := by linarith  have hbdd : BddBelow (Set.range fun (l : ℕ) => (l : ℝ) + a * (2 * a ^ l - 1) / (1 - a)) := by    use (-a / (1 - a))    rintro x ⟨l, rfl⟩    dsimp    have hl : 0 ≤ (l : ℝ) := Nat.cast_nonneg l    have hal : 0 ≤ a ^ l := pow_nonneg (le_of_lt ha0) l    have h_frac : -a / (1 - a) ≤ a * (2 * a ^ l - 1) / (1 - a) := by      rw [div_le_div_iff_of_pos_right h1a]      nlinarith    linarith  have hmem : a / (1 - a) ∈ Set.range (fun (l : ℕ) => (l : ℝ) + a * (2 * a ^ l - 1) / (1 - a)) := by    use 0    dsimp    ring  exact csInf_le hbdd hmem
See it in the graphDiscuss this resultChallenge it