biased_bit_critical_cost_le_zero_shift
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.
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.
unfold biased_bit_critical_cost let a := (1 - p) / p
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.
uses
div_pos,div_lt_onehave 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
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.
uses
Nat.cast_nonneg,pow_nonneg,le_of_lt,div_le_div_iff_of_pos_righthave 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
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.
have hmem : a / (1 - a) ∈ Set.range (fun (l : ℕ) => (l : ℝ) + a * (2 * a ^ l - 1) / (1 - a)) := by use 0 dsimp ring
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.
uses
csInf_leexact 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.
- In Lean's conditionally complete lattice structure on ℝ, applying csInf_le to bound the infimum from above requires proving that the set is bounded below (BddBelow), a condition that is often left implicit on paper when evaluating an infimum at a specific element.
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.
/-- 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