cycle_power_dyadic_exact_half_cover
Exact dyadic pair ownership supplies a witness covering every edge at half the radius, with the distance normalized to a power of two.
Statement
theorem cycle_power_dyadic_exact_half_cover (k : ℕ) (x : ℤ → ℕ → Bool) (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1) : ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+1) ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+2^(k+1)) = true
- Source
- Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cycle_power_exact_pair_existsAn exact Boolean pair-count sum of one supplies a selected owning pair.
- Used by 2
- cycle_power_dyadic_no_island_of_middle_full_pruneIn a tight exact full ordinary-cover dyadic integer model, current-scale middle-bit fullness alone implies that every class has no…
- cycle_power_dyadic_half_monotone_of_full_class_coverA tight exact full ordinary-cover dyadic integer model with a full class covering every vertex is monotone toward the endpoints separately…
The proof, explained
The proof specializes the dyadic exact ownership hypothesis to the index j = k + 1, where the interval length is 2^(k+1) (half the cycle radius 2^(k+2)). Applying cycle_power_exact_pair_exists yields an index a < 2^(k+1) with both endpoint indicators active. Elementary dyadic arithmetic then reduces the offset a + 2^(k+2) - 2^(k+1) to a + 2^(k+1).
2^(k+2) = 2 * 2^(k+1) automation
Rewriting 2^(k+2) as 2^(k+1) * 2 using pow_succ, the identity follows by commutativity of multiplication, handled by linear arithmetic.
uses
pow_succhave hD : 2^(k+2) = 2*2^(k+1) := by rw [pow_succ]; omega
For any vertex v : ℤ, there exists an index a < 2^(k+1) such that x(v - a, a) = true and x(v - a, a + 2^(k+2) - 2^(k+1)) = true.
Fix a vertex v. Since k + 1 < k + 2 (by linear arithmetic), we instantiate the dyadic exactness hypothesis hexact at index j = k + 1. Applying cycle_power_exact_pair_exists with cycle length D = 2^(k+2) and range R = 2^(k+1) then yields a witness a < 2^(k+1) satisfying both boolean conditions.
uses
cycle_power_exact_pair_existsintro v obtain ⟨a, ha, h₀, h₁⟩ := cycle_power_exact_pair_exists (2^(k+2)) (2^(k+1)) x (hexact (k+1) (by omega)) v
a + 2^(k+2) - 2^(k+1) = a + 2^(k+1) automation
Linear integer arithmetic simplifies the index expression using the identity 2^(k+2) = 2 * 2^(k+1) in scope.
have he : a+2^(k+2)-2^(k+1) = a+2^(k+1) := by omega
The witness a satisfies a < 2^(k+1), x(v - a, a) = true, and x(v - a, a + 2^(k+1)) = true.
We package the witness a, the bound a < 2^(k+1), and the first equality x(v - a, a) = true. Rewriting the second equality using the arithmetic identity replaces a + 2^(k+2) - 2^(k+1) by a + 2^(k+1), concluding the proof.
exact ⟨a, ha, h₀, by simpa only [he] using h₁⟩
pow_succ- For any monoid element a and natural number n, a^(n+1) = a^n * a.
cycle_power_exact_pair_exists- If for every vertex v the sum over a in [0, R) of the indicator for pair ownership (x(v - a, a) ∧ x(v - a, a + D - R)) equals 1, then for every vertex v there exists some index a < R where both indicators are true.
- The helper identity 2^(k+2) = 2 * 2^(k+1) established on line 11 is needed because Lean's Presburger arithmetic solver (omega) does not natively handle non-linear operations like variable powers; providing this identity allows omega to simplify expressions involving powers of two.
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 cycle_power_dyadic_exact_half_cover (k : ℕ) (x : ℤ → ℕ → Bool) (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1) : ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+1) ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+2^(k+1)) = true := by have hD : 2^(k+2) = 2*2^(k+1) := by rw [pow_succ]; omega intro v obtain ⟨a, ha, h₀, h₁⟩ := cycle_power_exact_pair_exists (2^(k+2)) (2^(k+1)) x (hexact (k+1) (by omega)) v have he : a+2^(k+2)-2^(k+1) = a+2^(k+1) := by omega exact ⟨a, ha, h₀, by simpa only [he] using h₁⟩