cycle_power_gap_sides_card
If r is below g, g is at most D, and every selected offset of a radius-D profile is localized below absolute vertex g or at least D, its selected-offset count equals the sum of its two compressed side sizes.
Statement
theorem cycle_power_gap_sides_card (D g r : ℕ) (hg : g ≤ D) (hr : r < g) (b : ℕ → Bool) (hgap : ∀ a < D, b a = true → r+a < g ∨ D ≤ r+a) : (range D).sum (fun a => (b a).toNat) = (cycle_power_gap_left_side g r b).card + (cycle_power_gap_right_side D g r b).card
- 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 4
- cycle_power_gap_left_sideThe lower-block vertices of a rooted profile, represented by their absolute positions in Fin g.
- cycle_power_gap_right_sideThe upper-block vertices of a rooted profile, represented in Fin g after subtracting the radius.
- bool_sum_eq_card_filterA Boolean profile summed through toNat over a natural range counts exactly its true offsets in that range.
- cycle_power_gap_sides_disjointThe lower and upper sides of a rooted gap profile are disjoint because their compressed vertex coordinates lie on opposite sides of the…
- Used by 1
- cycle_power_dyadic_gap_side_treeBetween two full roots at distance g at most the radius, the compressed sides of every interior tight class satisfy the tree identity:…
The proof, explained
The proof shows that the number of active offsets in {0, ..., D-1} equals the total size of the two gap sides by constructing an explicit bijection. First, the boolean sum and the sum of side sizes are converted into the cardinalities of the active index set S and the disjoint union of the two sides. The circular shift map a ↦ (r + a) mod D is well-defined into Fin g thanks to the gap hypothesis, and it is verified to be a bijection by splitting on whether r + a < D (mapping to the left side) or r + a ≥ D (mapping to the right side).
The sum of booleans over range D equals the cardinality of the disjoint union of the left and right gap sides.
Using bool_sum_eq_card_filter, the sum of (b a).toNat over range D is rewritten as the size of the set S of indices with b a = true. Then, since the left and right gap sides are disjoint (by cycle_power_gap_sides_disjoint), card_union_of_disjoint equates the sum of their cardinalities to the cardinality of their union.
uses
bool_sum_eq_card_filter,card_union_of_disjoint,cycle_power_gap_sides_disjointclassical rw [bool_sum_eq_card_filter, ← card_union_of_disjoint (cycle_power_gap_sides_disjoint D g r b)]Define the set S and a well-defined map f : S → Fin g.
Let S = {a ∈ range D | b a = true}. The map f sends a ∈ S to r + a if r + a < D, and to r + a - D otherwise. By the gap condition hgap, either r + a < g or D ≤ r + a. If r + a < D, then r + a < g; if r + a ≥ D, then since a < D and r < g, we have r + a - D < g. Thus f(a) is strictly less than g in both cases, which omega closes.
let S := (range D).filter (fun a => b a = true) let f (a : ℕ) (ha : a ∈ S) : Fin g := ⟨if r+a < D then r+a else r+a-D, by have haD := mem_range.mp (mem_filter.mp ha).1 have hba := (mem_filter.mp ha).2 have hga := hgap a haD hba split_ifs with h · omega · omega⟩
It suffices to show that f is a bijection from S to the union of the two sides.
By card_bij, showing that the cardinality of S equals the cardinality of the union of the left and right sides reduces to verifying that f maps S into the union, is injective, and is surjective.
uses
card_bijchange S.card = _ apply card_bij f
The map f takes every element of S into the union of the left and right sides.
For a ∈ S, we split into cases based on whether r + a < D. If r + a < D, then f(a) = r + a satisfies r ≤ f(a) and f(a) - r = a, so b(f(a) - r) = b(a) = true, placing f(a) in the left side. If r + a ≥ D, then f(a) = r + a - D satisfies f(a) < r (since a < D) and D + f(a) - r = a, so b(D + f(a) - r) = b(a) = true, placing f(a) in the right side.
uses
if_pos,if_neg,mem_univ· intro a ha have haD := mem_range.mp (mem_filter.mp ha).1 have hba := (mem_filter.mp ha).2 have hga := hgap a haD hba by_cases h : r+a < D · apply mem_union.mpr left apply mem_filter.mpr refine ⟨mem_univ _, ?_, ?_⟩ · dsimp [f] rw [if_pos h] omega · have he : (f a ha).val-r = a := by dsimp [f]; rw [if_pos h]; omega simpa only [he] using hba · apply mem_union.mpr right apply mem_filter.mpr refine ⟨mem_univ _, ?_, ?_⟩ · dsimp [f] rw [if_neg h] omega · have he : D+(f a ha).val-r = a := by dsimp [f]; rw [if_neg h]; omega simpa only [he] using hba
The map f is injective on S.
Assuming f(a) = f(a') for a, a' ∈ S, applying congrArg Fin.val equates their numerical values. Case splitting on whether r + a < D and r + a' < D yields four cases: when both are below D or both at least D, linear arithmetic directly implies a = a'; the two mixed cases produce impossible inequalities because a, a' < D. Linear arithmetic (omega) closes all branches.
uses
congrArg· intro a ha a' ha' he have heval := congrArg Fin.val he have haD := mem_range.mp (mem_filter.mp ha).1 have ha'D := mem_range.mp (mem_filter.mp ha').1 dsimp [f] at heval split_ifs at heval <;> omega
The map f is surjective onto the union of the left and right sides.
Given an element i ∈ Fin g in the union, if i belongs to the left side, then r ≤ i < g ≤ D and b(i - r) = true, so a = i - r is in S with r + a = i < D, meaning f(a) = i. If i belongs to the right side, then i < r and b(D + i - r) = true, so a = D + i - r is in S with r + a = D + i ≥ D, meaning f(a) = i. In both cases, Fin.ext confirms f(a) = i.
uses
lt_of_lt_of_le,Fin.ext,if_pos,if_neg· intro i hi rcases mem_union.mp hi with hi | hi · have hri := (mem_filter.mp hi).2.1 have hbi := (mem_filter.mp hi).2.2 have hiD : i.val < D := lt_of_lt_of_le i.isLt hg have ha : i.val-r ∈ S := mem_filter.mpr ⟨mem_range.mpr (by omega), hbi⟩ refine ⟨i.val-r, ha, ?_⟩ apply Fin.ext dsimp [f] rw [if_pos (by omega : r+(i.val-r) < D)] omega · have hir := (mem_filter.mp hi).2.1 have hbi := (mem_filter.mp hi).2.2 have ha : D+i.val-r ∈ S := mem_filter.mpr ⟨mem_range.mpr (by omega), hbi⟩ refine ⟨D+i.val-r, ha, ?_⟩ apply Fin.ext dsimp [f] rw [if_neg (by omega : ¬r+(D+i.val-r) < D)] omega
bool_sum_eq_card_filter- The sum of boolean values converted to ℕ over range N equals the cardinality of the filtered set of elements where the boolean is true.
card_union_of_disjoint- For disjoint finite sets s and t, the cardinality of their union equals the sum of their individual cardinalities.
cycle_power_gap_sides_disjoint- The left and right gap sides are disjoint subsets of Fin g.
card_bij- A function between two finite sets that maps into the target set, is injective, and is surjective proves the two sets have equal cardinality.
if_pos- If the condition c holds, then (if c then t else e) evaluates to t.
if_neg- If the condition c does not hold, then (if c then t else e) evaluates to e.
mem_univ- Every element of a finite type belongs to the universal set Finset.univ.
congrArg- If x = y, then f x = f y.
lt_of_lt_of_le- In a preorder, if a < b and b ≤ c, then a < c.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
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_gap_sides_card (D g r : ℕ) (hg : g ≤ D) (hr : r < g) (b : ℕ → Bool) (hgap : ∀ a < D, b a = true → r+a < g ∨ D ≤ r+a) : (range D).sum (fun a => (b a).toNat) = (cycle_power_gap_left_side g r b).card + (cycle_power_gap_right_side D g r b).card := by classical rw [bool_sum_eq_card_filter, ← card_union_of_disjoint (cycle_power_gap_sides_disjoint D g r b)] let S := (range D).filter (fun a => b a = true) let f (a : ℕ) (ha : a ∈ S) : Fin g := ⟨if r+a < D then r+a else r+a-D, by have haD := mem_range.mp (mem_filter.mp ha).1 have hba := (mem_filter.mp ha).2 have hga := hgap a haD hba split_ifs with h · omega · omega⟩ change S.card = _ apply card_bij f · intro a ha have haD := mem_range.mp (mem_filter.mp ha).1 have hba := (mem_filter.mp ha).2 have hga := hgap a haD hba by_cases h : r+a < D · apply mem_union.mpr left apply mem_filter.mpr refine ⟨mem_univ _, ?_, ?_⟩ · dsimp [f] rw [if_pos h] omega · have he : (f a ha).val-r = a := by dsimp [f]; rw [if_pos h]; omega simpa only [he] using hba · apply mem_union.mpr right apply mem_filter.mpr refine ⟨mem_univ _, ?_, ?_⟩ · dsimp [f] rw [if_neg h] omega · have he : D+(f a ha).val-r = a := by dsimp [f]; rw [if_neg h]; omega simpa only [he] using hba · intro a ha a' ha' he have heval := congrArg Fin.val he have haD := mem_range.mp (mem_filter.mp ha).1 have ha'D := mem_range.mp (mem_filter.mp ha').1 dsimp [f] at heval split_ifs at heval <;> omega · intro i hi rcases mem_union.mp hi with hi | hi · have hri := (mem_filter.mp hi).2.1 have hbi := (mem_filter.mp hi).2.2 have hiD : i.val < D := lt_of_lt_of_le i.isLt hg have ha : i.val-r ∈ S := mem_filter.mpr ⟨mem_range.mpr (by omega), hbi⟩ refine ⟨i.val-r, ha, ?_⟩ apply Fin.ext dsimp [f] rw [if_pos (by omega : r+(i.val-r) < D)] omega · have hir := (mem_filter.mp hi).2.1 have hbi := (mem_filter.mp hi).2.2 have ha : D+i.val-r ∈ S := mem_filter.mpr ⟨mem_range.mpr (by omega), hbi⟩ refine ⟨D+i.val-r, ha, ?_⟩ apply Fin.ext dsimp [f] rw [if_neg (by omega : ¬r+(D+i.val-r) < D)] omega