AFTD Auto-Formalizing Theoretical Domains

dyadic_integer_tangent_eq_iff

theoremverified

Equality in the rational dyadic tangent bound occurs exactly at t=m or t+1=m.

Statement

theorem dyadic_integer_tangent_eq_iff (m t : ℕ) :
    (m : ℚ) + 1 - t = (2 : ℚ)^m / 2^t ↔ t = m ∨ t+1 = m
Source
Reusable finite-cube and ordered-biclique helpers for the uniform OP-205 / RT-1 full-root-gap reduction following arXiv:2610.15635. The deficiency-one singular-coordinate/tree argument formalizes the Boolean setting of arXiv:1103.3693 Lemma 2.5.4 and Corollary 2.5.6; arXiv:2212.14685 Section 2.3 gives a related partition-size discussion. These are helper formalizations, not an original graph covering result; no advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • two_pow_eq_succ_iffFor a natural d, two to the power d equals d+1 exactly when d is zero or one.
Used by 1

The proof, explained

The proof proceeds by case distinction on whether t ≤ m. When t ≤ m, the rational equation simplifies by the laws of exponents to 2^(m-t) = (m-t) + 1. By the lemma two_pow_eq_succ_iff, this equation holds in ℕ if and only if m - t ∈ {0, 1}, which translates to t = m or t + 1 = m. When t > m, the left-hand side is at most 0 while the right-hand side is strictly positive, making equality impossible and leaving both sides of the equivalence false.

  1. It suffices to establish the equivalence separately in the cases t ≤ m and t > m.

    We perform a case split on whether t ≤ m using `by_cases`.

    line 7

      by_cases htm : t ≤ m
  2. Assuming t ≤ m, the rational equation is equivalent to (m - t : ℕ) + 1 = 2^(m - t).

    Since t ≤ m, the rational difference (m : ℚ) - t equals the cast of the natural subtraction (m - t : ℕ) by Nat.cast_sub, so (m : ℚ) + 1 - t simplifies to (m - t : ℕ) + 1. Furthermore, since 2 ≠ 0 and t ≤ m, the right-hand side 2^m / 2^t simplifies to 2^(m - t) using div_eq_mul_inv and pow_sub₀.

    lines 8–11

    uses Nat.cast_sub, div_eq_mul_inv, pow_sub₀

      · have he : (m : ℚ) + 1 - t = (m-t : ℕ) + 1 := by
          rw [Nat.cast_sub htm]
          ring
        rw [he, div_eq_mul_inv, ← pow_sub₀ (2 : ℚ) (by norm_num) htm]
  3. When t ≤ m, the equation holds if and only if t = m or t + 1 = m.

    After transferring the equality from ℚ to ℕ, the equation becomes 2^(m - t) = (m - t) + 1. Applying two_pow_eq_succ_iff reduces this to m - t = 0 ∨ m - t = 1. Under the assumption t ≤ m, Presburger arithmetic (`omega`) shows that this disjunction is equivalent to t = m ∨ t + 1 = m.

    lines 12–16

    uses two_pow_eq_succ_iff

        have hc : ((m-t : ℕ) : ℚ) + 1 = (2 : ℚ)^(m-t) ↔
            2^(m-t) = (m-t)+1 := by
          constructor <;> intro h <;> exact_mod_cast h.symm
        rw [hc, two_pow_eq_succ_iff]
        omega
  4. When t > m, the left-hand side is non-positive while the right-hand side is strictly positive.

    From ¬(t ≤ m), we have m + 1 ≤ t, which implies (m : ℚ) + 1 - t ≤ 0. Meanwhile, the right-hand side 2^m / 2^t is strictly positive by `positivity` since powers of 2 and their quotients are positive.

    lines 17–20

      · have ht : m+1 ≤ t := by omega
        have hn : (m : ℚ) + 1 - t ≤ 0 := by
          exact_mod_cast (show (m : ℤ) + 1 - t ≤ 0 by omega)
        have hp : (0 : ℚ) < 2^m / 2^t := by positivity
  5. When t > m, neither side of the equivalence can hold, completing the proof.

    For the forward direction, assuming equality yields a contradiction by linear arithmetic (`linarith`), as a non-positive value cannot equal a strictly positive one. For the backward direction, the assumption t = m ∨ t + 1 = m contradicts m + 1 ≤ t, which `omega` refutes.

    lines 21–24

        constructor
        · intro h
          linarith
        · omega
Nat.cast_sub
For natural numbers m ≤ n, the difference n - m cast into an additive group with one equals the difference of the casts ↑n - ↑m.
div_eq_mul_inv
In any division monoid, a / b = a * b⁻¹.
pow_sub₀
For any non-zero element a in a group with zero and natural numbers n ≤ m, a^(m - n) = a^m * (a^n)⁻¹.
two_pow_eq_succ_iff
For any natural number d, 2^d = d + 1 holds if and only if d = 0 or d = 1.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem dyadic_integer_tangent_eq_iff (m t : ℕ) :    (m : ℚ) + 1 - t = (2 : ℚ)^m / 2^t ↔ t = m ∨ t+1 = m := by  by_cases htm : t ≤ m  · have he : (m : ℚ) + 1 - t = (m-t : ℕ) + 1 := by      rw [Nat.cast_sub htm]      ring    rw [he, div_eq_mul_inv, ← pow_sub₀ (2 : ℚ) (by norm_num) htm]    have hc : ((m-t : ℕ) : ℚ) + 1 = (2 : ℚ)^(m-t) ↔        2^(m-t) = (m-t)+1 := by      constructor <;> intro h <;> exact_mod_cast h.symm    rw [hc, two_pow_eq_succ_iff]    omega  · have ht : m+1 ≤ t := by omega    have hn : (m : ℚ) + 1 - t ≤ 0 := by      exact_mod_cast (show (m : ℤ) + 1 - t ≤ 0 by omega)    have hp : (0 : ℚ) < 2^m / 2^t := by positivity    constructor    · intro h      linarith    · omega
See it in the graphDiscuss this resultChallenge it