biased_bit_non_tie_of_gt_two_thirds
For any bias parameter p satisfying 2 / 3 < p and p < 1, the non-tie condition biased_bit_non_tie p holds.
Statement
theorem biased_bit_non_tie_of_gt_two_thirds (p : ℝ) (hp : 2 / 3 < p) (hp1 : p < 1) :
biased_bit_non_tie p- Source
- arXiv:2611.16066 Cor 5.9
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- biased_bit_non_tieFor a bias parameter p : ℝ, biased_bit_non_tie p is the proposition that for all natural numbers j and k with 1 ≤ j and j < k, 2 * a ^ j ≠…
Read back from the Lean
For every real number $p$, if $2 / 3 < p$ and $p < 1$, then biased_bit_non_tie p holds (that is, for all natural numbers $j$ and $k$ with $1 \le j$ and $j < k$, $2 a^j \neq 1 + a^k$, where $a = (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 proof establishes the non-tie condition by showing that 2 * a^j and 1 + a^k are separated by 1, namely 2 * a^j < 1 < 1 + a^k, for all 1 ≤ j < k, where a = (1 - p) / p. When p > 2 / 3, the ratio a lies strictly between 0 and 1 / 2. Since a ≤ 1 and j ≥ 1, powers of a decrease, yielding 2 * a^j ≤ 2 * a < 1, while positivity of a guarantees 1 + a^k > 1.
Let 1 ≤ j < k be given, and define a = (1 - p) / p; it suffices to show 2 * a^j ≠ 1 + a^k.
Unfolding the definition of biased_bit_non_tie p, we introduce arbitrary natural numbers j and k satisfying 1 ≤ j < k and define a = (1 - p) / p.
intro j k hj hjk set a := (1 - p) / p
The ratio a satisfies 0 < a < 1 / 2 and a ≤ 1.
From 2 / 3 < p < 1, both p and 1 - p are strictly positive by linear arithmetic, so their quotient a is strictly positive by div_pos. Clearing the positive denominator p using div_lt_iff₀ transforms a < 1 / 2 into 1 - p < p / 2, which holds by linear arithmetic since p > 2 / 3. Finally, a < 1 / 2 immediately implies a ≤ 1.
uses
div_pos,div_lt_iff₀have hp0 : 0 < p := by linarith have h1 : 0 < 1 - p := by linarith have hpos : 0 < a := div_pos h1 hp0 have hlt : a < 1 / 2 := by rw [div_lt_iff₀ hp0] linarith have h_le_one : a ≤ 1 := by linarith
a^j ≤ a
Since 0 ≤ a ≤ 1 (using le_of_lt on 0 < a) and 1 ≤ j, pow_le_pow_of_le_one shows that a^j ≤ a^1 = a.
uses
pow_le_pow_of_le_one,le_of_lthave haj : a ^ j ≤ a := by have := pow_le_pow_of_le_one (le_of_lt hpos) h_le_one hj simpa using this
2 * a^j < 1
Combining the bounds a^j ≤ a and a < 1 / 2 in a chain of inequalities gives 2 * a^j ≤ 2 * a < 2 * (1 / 2) = 1.
have h_left : 2 * a ^ j < 1 := by calc 2 * a ^ j ≤ 2 * a := by linarith _ < 2 * (1 / 2) := by linarith _ = 1 := by norm_num
1 < 1 + a^k
Since a > 0, pow_pos ensures a^k > 0, so adding 1 gives 1 < 1 + a^k.
uses
pow_poshave h_right : 1 < 1 + a ^ k := by have : 0 < a ^ k := pow_pos hpos k linarith
2 * a^j ≠ 1 + a^k
Because 2 * a^j < 1 and 1 < 1 + a^k, the two values are separated by 1 and therefore cannot be equal.
linarith
div_lt_iff₀- For a positive denominator c, b / c < a is equivalent to b < a * c.
div_pos- The quotient of two strictly positive elements is strictly positive.
le_of_lt- Strict inequality implies non-strict inequality: if a < b, then a ≤ b.
pow_le_pow_of_le_one- For a base between 0 and 1, raising to a greater exponent yields a smaller or equal value: if 0 ≤ a ≤ 1 and m ≤ n, then a^n ≤ a^m.
pow_pos- Any natural power of a strictly positive element is strictly positive.
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 any bias parameter p > 2/3, the non-tie condition holds because 2 * a^j < 1 < 1 + a^k for all 1 ≤ j < k. -/theorem biased_bit_non_tie_of_gt_two_thirds (p : ℝ) (hp : 2 / 3 < p) (hp1 : p < 1) : biased_bit_non_tie p := by intro j k hj hjk set a := (1 - p) / p have hp0 : 0 < p := by linarith have h1 : 0 < 1 - p := by linarith have hpos : 0 < a := div_pos h1 hp0 have hlt : a < 1 / 2 := by rw [div_lt_iff₀ hp0] linarith have h_le_one : a ≤ 1 := by linarith have haj : a ^ j ≤ a := by have := pow_le_pow_of_le_one (le_of_lt hpos) h_le_one hj simpa using this have h_left : 2 * a ^ j < 1 := by calc 2 * a ^ j ≤ 2 * a := by linarith _ < 2 * (1 / 2) := by linarith _ = 1 := by norm_num have h_right : 1 < 1 + a ^ k := by have : 0 < a ^ k := pow_pos hpos k linarith linarith