AFTD Auto-Formalizing Theoretical Domains

dyadic_integer_tangent

theoremverified

For natural m and t, the rational number m+1-t is at most 2^m divided by 2^t.

Statement

theorem dyadic_integer_tangent (m t : ℕ) :
    (m : ℚ) + 1 - t ≤ (2 : ℚ)^m / 2^t
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
Used by 1

The proof, explained

The proof splits into two cases based on whether t ≤ m. When t ≤ m, the expression simplifies to (m - t) + 1 ≤ 2^(m - t), which follows directly from the fact that k < 2^k for every natural number k. When t > m, the left-hand side is at most 0, while the right-hand side is strictly positive, completing the claim by transitivity.

  1. It suffices to consider the cases t ≤ m and t > m separately.

    We perform a case split on whether t ≤ m.

    line 7

      by_cases htm : t ≤ m
  2. When t ≤ m, the inequality reduces to (m - t : ℚ) + 1 ≤ 2^(m - t).

    Since t ≤ m, the subtraction of natural numbers casts to rational subtraction by Nat.cast_sub, which gives (m : ℚ) + 1 - t = (m - t : ℕ) + 1. On the right-hand side, since 2 ≠ 0 and t ≤ m, div_eq_mul_inv and pow_sub₀ simplify 2^m / 2^t to 2^(m - t). Substituting both rewrites reduces the goal to (m - t : ℚ) + 1 ≤ 2^(m - t).

    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 : (2 : ℚ) ≠ 0) htm]
  3. The inequality holds when t ≤ m.

    For any natural number k, k < 2^k by Nat.lt_two_pow_self, which implies k + 1 ≤ 2^k. Setting k = m - t gives (m - t) + 1 ≤ 2^(m - t) over ℕ. Casting this inequality from ℕ to ℚ closes the case.

    lines 12–15

    uses Nat.lt_two_pow_self

        have hn : m-t+1 ≤ 2^(m-t) := by
          have : m-t < 2^(m-t) := Nat.lt_two_pow_self
          omega
        exact_mod_cast hn
  4. When t > m, the left-hand side satisfies (m : ℚ) + 1 - t ≤ 0.

    The assumption ¬(t ≤ m) means m + 1 ≤ t. Linear arithmetic over the integers yields (m : ℤ) + 1 - t ≤ 0, which casts to (m : ℚ) + 1 - t ≤ 0.

    lines 16–18

      · have hn : (m : ℚ) + 1 - t ≤ 0 := by
          have ht : m+1 ≤ t := by omega
          exact_mod_cast (show (m : ℤ) + 1 - t ≤ 0 by omega)
  5. The inequality holds when t > m.

    Because the left-hand side is at most 0 and the right-hand side 2^m / 2^t is non-negative (being a quotient of powers of 2), the inequality follows by transitivity.

    line 19

        exact hn.trans (by positivity)
Nat.cast_sub
For natural numbers m ≤ n, the subtraction n - m cast into an additive group with one equals ↑n - ↑m.
div_eq_mul_inv
In a group with division, dividing a by b is equivalent to multiplying a by the inverse of b.
pow_sub₀
For a non-zero element a in a group with zero and natural numbers n ≤ m, a^(m - n) = a^m * (a^n)⁻¹.
Nat.lt_two_pow_self
Every natural number n is strictly less than 2^n.

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 (m t : ℕ) :    (m : ℚ) + 1 - t ≤ (2 : ℚ)^m / 2^t := 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 : (2 : ℚ) ≠ 0) htm]    have hn : m-t+1 ≤ 2^(m-t) := by      have : m-t < 2^(m-t) := Nat.lt_two_pow_self      omega    exact_mod_cast hn  · have hn : (m : ℚ) + 1 - t ≤ 0 := by      have ht : m+1 ≤ t := by omega      exact_mod_cast (show (m : ℤ) + 1 - t ≤ 0 by omega)    exact hn.trans (by positivity)
See it in the graphDiscuss this resultChallenge it