dyadic_integer_tangent_eq_iff
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
- 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 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.
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`.
by_cases htm : t ≤ mAssuming 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₀.
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]
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.
uses
two_pow_eq_succ_iffhave 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
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.
· 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
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.
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.
- The equivalence hc and the bound hn involve casting between ℕ, ℤ, and ℚ using exact_mod_cast; these are formal type-coercion steps with no paper-and-pencil counterpart.
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_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