cycle_power_exact_pair_exists
An exact Boolean pair-count sum of one supplies a selected owning pair.
Statement
theorem cycle_power_exact_pair_exists (D R : ℕ) (x : ℤ → ℕ → Bool) (hexact : ∀ v : ℤ, (range R).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1) : ∀ v : ℤ, ∃ a : ℕ, a < R ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+D-R) = 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- Used by 2
- cycle_power_gap_exact_side_ownerExact distance D-R ownership in an integer model gives unique compressed gap-side owners for every forward distance-R pair on Fin g, when…
- cycle_power_dyadic_exact_half_coverExact dyadic pair ownership supplies a witness covering every edge at half the radius, with the distance normalized to a power of two.
The proof, explained
To show the existence of an index a < R satisfying the condition for a given v, the proof observes that the sum of the Boolean indicators over a ∈ range R is 1, hence non-zero. By exists_ne_zero_of_sum_ne_zero, there must exist an index a < R whose term is non-zero. A case analysis on the Boolean values of the two factors shows that their conjunction can only be non-zero when both factors are true.
For any integer v, there exists an index a in range R whose summand is non-zero.
We introduce an arbitrary integer v. The assumption hexact states that the sum of (x(v - a, a) && x(v - a, a + D - R)).toNat over a ∈ range R is equal to 1. Since 1 ≠ 0, this sum is non-zero (verified by decide). Applying exists_ne_zero_of_sum_ne_zero produces an index a ∈ range R for which the summand is non-zero.
uses
exists_ne_zero_of_sum_ne_zerointro v obtain ⟨a, ha, he⟩ := exists_ne_zero_of_sum_ne_zero (show (range R).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) ≠ 0 by rw [hexact v]; decide)
The index a satisfies a < R, reducing the goal to showing that both Boolean factors are true.
From a ∈ range R, the lemma mem_range.mp yields a < R. Providing a and this bound as the witness for the existential quantifier leaves the remaining goal to prove that x(v - a, a) = true and x(v - a, a + D - R) = true.
uses
mem_range.mprefine ⟨a, mem_range.mp ha, ?_⟩Both x(v - a, a) and x(v - a, a + D - R) are true.
We perform a case split on the Boolean values of x(v - a, a) and x(v - a, a + D - R). In the three cases where either term is false, the conjunction evaluates to false and its numerical value is 0, which contradicts the established fact that the summand is non-zero. In the remaining case where both terms are true, the conjunction is true, establishing the claim.
uses
Bool.false_and,Bool.true_and,Bool.toNat_false,Bool.toNat_true,ne_eq,not_true_eq_false,and_selfcases h₀ : x (v-(a : ℤ)) a <;> cases h₁ : x (v-(a : ℤ)) (a+D-R) <;> simp_all only [Bool.false_and, Bool.true_and, Bool.toNat_false, Bool.toNat_true, ne_eq, not_true_eq_false, and_self]
exists_ne_zero_of_sum_ne_zero- If the sum of a function over a finite set is non-zero, then the function takes a non-zero value at some element of the set.
mem_range.mp- If a natural number belongs to `range n`, then it is strictly less than `n`.
Bool.false_and- The conjunction of `false` with any Boolean value is `false`.
Bool.true_and- The conjunction of `true` with any Boolean value `b` equals `b`.
Bool.toNat_false- The natural number corresponding to `false` is 0.
Bool.toNat_true- The natural number corresponding to `true` is 1.
ne_eq- The inequality `a ≠ b` is defined as the negation of equality, `¬(a = b)`.
not_true_eq_false- The negation of `True` is equal to `False`.
and_self- For any proposition `p`, the conjunction `p ∧ p` is equivalent to `p`.
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_exact_pair_exists (D R : ℕ) (x : ℤ → ℕ → Bool) (hexact : ∀ v : ℤ, (range R).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1) : ∀ v : ℤ, ∃ a : ℕ, a < R ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+D-R) = true := by intro v obtain ⟨a, ha, he⟩ := exists_ne_zero_of_sum_ne_zero (show (range R).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) ≠ 0 by rw [hexact v]; decide) refine ⟨a, mem_range.mp ha, ?_⟩ cases h₀ : x (v-(a : ℤ)) a <;> cases h₁ : x (v-(a : ℤ)) (a+D-R) <;> simp_all only [Bool.false_and, Bool.true_and, Bool.toNat_false, Bool.toNat_true, ne_eq, not_true_eq_false, and_self]