dyadic_integer_tangent
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
- binary_partial_word_cube_minimum_incidenceFor pairwise conflicting finite partial words, if total support size plus 2^m equals the number of words times m+1, then their volume sum…
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.
It suffices to consider the cases t ≤ m and t > m separately.
We perform a case split on whether t ≤ m.
by_cases htm : t ≤ mWhen 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).
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]
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.
uses
Nat.lt_two_pow_selfhave hn : m-t+1 ≤ 2^(m-t) := by have : m-t < 2^(m-t) := Nat.lt_two_pow_self omega exact_mod_cast hn
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.
· have hn : (m : ℚ) + 1 - t ≤ 0 := by have ht : m+1 ≤ t := by omega exact_mod_cast (show (m : ℤ) + 1 - t ≤ 0 by omega)
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.
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
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.
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)