AFTD Auto-Formalizing Theoretical Domains

biased_bit_non_tie_of_gt_two_thirds

theoremverified

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.

  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.

    lines 4–5

      intro j k hj hjk
      set a := (1 - p) / p
  2. 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.

    lines 6–12

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

    lines 13–15

    uses pow_le_pow_of_le_one, le_of_lt

      have haj : a ^ j ≤ a := by
        have := pow_le_pow_of_le_one (le_of_lt hpos) h_le_one hj
        simpa using this
  4. 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.

    lines 16–20

      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
  5. 1 < 1 + a^k

    Since a > 0, pow_pos ensures a^k > 0, so adding 1 gives 1 < 1 + a^k.

    lines 21–23

    uses pow_pos

      have h_right : 1 < 1 + a ^ k := by
        have : 0 < a ^ k := pow_pos hpos k
        linarith
  6. 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.

    line 24

      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

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