cycle_power_gap_sides_pair_card
For a profile rooted below g at most D, whose selected distance D-R pairs cross the two blocks, its pair count equals the number of compressed side pairs at forward distance R.
Statement
theorem cycle_power_gap_sides_pair_card (D R g r : ℕ) (hRD : R ≤ D) (hg : g ≤ D) (hr : r < g) (b : ℕ → Bool) (hcross : ∀ a < R, b a = true → b (a+D-R) = true → r+a < g ∧ D ≤ r+(a+D-R)) : (range R).sum (fun a => (b a && b (a+D-R)).toNat) = (((cycle_power_gap_left_side g r b).product (cycle_power_gap_right_side D g r b)).filter (fun p : Fin g × Fin g => p.2.val+R = p.1.val)).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 3
- 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.
- 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 theorem equates the number of indices a < R where both b a and b (a + D - R) hold with the number of pairs (i, j) in the product of the left and right gap sides satisfying the distance condition j + R = i. First, the sum of booleans is rewritten as the cardinality of the filtered index set S = {a < R | b a && b (a + D - R) = true}. The proof then establishes a bijection between S and the target set via a ↦ (r + a, r + a - R), using the crossing hypothesis `hcross` to guarantee that both coordinates land strictly below g. Injectivity follows from equating the first coordinates, and surjectivity follows by choosing a = i - r for any valid pair (i, j).
The sum of boolean indicator values is reformulated as the cardinality of the subset S ⊆ {0, ..., R-1} of indices where both b a and b (a + D - R) hold.
Rewriting with `bool_sum_eq_card_filter` transforms the sum of boolean terms into the cardinality of the filtered set S = {a ∈ {0, ..., R-1} | (b a && b (a + D - R)) = true}. The proof then binds S as a local definition.
uses
bool_sum_eq_card_filterclassical rw [bool_sum_eq_card_filter] let S := (range R).filter (fun a => (b a && b (a+D-R)) = true)
The candidate mapping f : S → Fin g × Fin g defined by f(a) = (r + a, r + a - R) is well-defined, and the goal is restated as |S| = |T|.
For any a ∈ S, both b a and b (a + D - R) evaluate to true (via `Bool.and_eq_true`). The crossing hypothesis `hcross` guarantees that r + a < g and D ≤ r + (a + D - R). Together with R ≤ D, linear arithmetic (`omega`) implies r + a - R < g, ensuring that both coordinates are valid elements of Fin g. The proof then reformulates the goal as equating the cardinality of S to that of the filtered product set T.
uses
Bool.and_eq_truelet f (a : ℕ) (ha : a ∈ S) : Fin g × Fin g := (⟨r+a, by have hb := (mem_filter.mp ha).2 have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb exact (hcross a (mem_range.mp (mem_filter.mp ha).1) hbb.1 hbb.2).1⟩, ⟨r+a-R, by have hb := (mem_filter.mp ha).2 have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb have hc := hcross a (mem_range.mp (mem_filter.mp ha).1) hbb.1 hbb.2 omega⟩) change S.card = _
It suffices to show that f is a bijection from S onto the target set T.
Applying `card_bij` with the mapping f reduces the equality of cardinalities |S| = |T| to three subgoals: verifying that f maps S into T, that f is injective on S, and that f maps S surjectively onto T.
uses
card_bijapply card_bij fFor every a ∈ S, its image f(a) belongs to the target set T.
Let a ∈ S. Using `Bool.and_eq_true` and `hcross`, both b a and b (a + D - R) are true. To establish that f(a) lies in T, three conditions are verified: first, the left coordinate r + a satisfies r ≤ r + a and (r + a) - r = a, so it belongs to `cycle_power_gap_left_side g r b` using `mem_univ`; second, the right coordinate r + a - R satisfies r + a - R < r (since a < R) and D + (r + a - R) - r = a + D - R, placing it in `cycle_power_gap_right_side D g r b` using `mem_univ`; third, the forward distance condition (r + a - R) + R = r + a holds by linear arithmetic (`omega`).
uses
Bool.and_eq_true,mem_univ· intro a ha have haR := mem_range.mp (mem_filter.mp ha).1 have hb := (mem_filter.mp ha).2 have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb have hc := hcross a haR hbb.1 hbb.2 apply mem_filter.mpr constructor · apply mem_product.mpr constructor · apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [f]; omega, ?_⟩ have he : (f a ha).1.val-r = a := by dsimp [f]; omega simpa only [he] using hbb.1 · apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [f]; omega, ?_⟩ have he : D+(f a ha).2.val-r = a+D-R := by dsimp [f]; omega simpa only [he] using hbb.2 · dsimp [f] omega
The mapping f is injective on S.
Assuming f(a) = f(a') for a, a' ∈ S, applying `congrArg` with the first-component projection gives r + a = r + a'. Linear arithmetic (`omega`) immediately yields a = a'.
uses
congrArg· intro a ha a' ha' he have heval := congrArg (fun p : Fin g × Fin g => p.1.val) he dsimp [f] at heval omega
The mapping f is surjective onto T.
Given a pair p = (i, j) in the target set T, its defining properties give j + R = i, r ≤ i with b (i - r) = true, and j < r with b (D + j - r) = true. Setting a = i - r, linear arithmetic (`omega`) shows a < R (since i = j + R and j < r) and a + D - R = D + j - r. Hence a ∈ S by `Bool.and_eq_true`. Finally, the equality f(a) = p is verified componentwise using `Prod.ext` and `Fin.ext`, where `omega` checks r + (i - r) = i and r + (i - r) - R = j.
uses
Bool.and_eq_true,Prod.ext,Fin.ext· intro p hp have hdist := (mem_filter.mp hp).2 have hparts := mem_product.mp (mem_filter.mp hp).1 have hri := (mem_filter.mp hparts.1).2.1 have hbi := (mem_filter.mp hparts.1).2.2 have hjr := (mem_filter.mp hparts.2).2.1 have hbj := (mem_filter.mp hparts.2).2.2 have haR : p.1.val-r < R := by omega have haoff : (p.1.val-r)+D-R = D+p.2.val-r := by omega have ha : p.1.val-r ∈ S := by apply mem_filter.mpr refine ⟨mem_range.mpr haR, ?_⟩ simp only [Bool.and_eq_true, haoff] exact ⟨hbi, hbj⟩ refine ⟨p.1.val-r, ha, ?_⟩ apply Prod.ext <;> apply Fin.ext <;> dsimp [f] <;> omega
bool_sum_eq_card_filter- The sum over {0, ..., N-1} of a boolean predicate converted to natural numbers equals the cardinality of the subset where the predicate evaluates to true.
Bool.and_eq_true- A boolean conjunction a && b equals true if and only if both a and b equal true.
card_bij- Two finite sets have equal cardinality if there exists a map between them that lands in the target, is injective, and is surjective.
mem_univ- Every element of a finite type belongs to the universal finite set univ.
congrArg- Applying a function to equal inputs produces equal outputs.
Prod.ext- Two ordered pairs are equal if and only if their respective first and second components are equal.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural number values are equal.
- Linear arithmetic goals, including equalities and inequalities involving natural number subtraction with cutoff, are discharged automatically by `omega`.
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_pair_card (D R g r : ℕ) (hRD : R ≤ D) (hg : g ≤ D) (hr : r < g) (b : ℕ → Bool) (hcross : ∀ a < R, b a = true → b (a+D-R) = true → r+a < g ∧ D ≤ r+(a+D-R)) : (range R).sum (fun a => (b a && b (a+D-R)).toNat) = (((cycle_power_gap_left_side g r b).product (cycle_power_gap_right_side D g r b)).filter (fun p : Fin g × Fin g => p.2.val+R = p.1.val)).card := by classical rw [bool_sum_eq_card_filter] let S := (range R).filter (fun a => (b a && b (a+D-R)) = true) let f (a : ℕ) (ha : a ∈ S) : Fin g × Fin g := (⟨r+a, by have hb := (mem_filter.mp ha).2 have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb exact (hcross a (mem_range.mp (mem_filter.mp ha).1) hbb.1 hbb.2).1⟩, ⟨r+a-R, by have hb := (mem_filter.mp ha).2 have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb have hc := hcross a (mem_range.mp (mem_filter.mp ha).1) hbb.1 hbb.2 omega⟩) change S.card = _ apply card_bij f · intro a ha have haR := mem_range.mp (mem_filter.mp ha).1 have hb := (mem_filter.mp ha).2 have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb have hc := hcross a haR hbb.1 hbb.2 apply mem_filter.mpr constructor · apply mem_product.mpr constructor · apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [f]; omega, ?_⟩ have he : (f a ha).1.val-r = a := by dsimp [f]; omega simpa only [he] using hbb.1 · apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [f]; omega, ?_⟩ have he : D+(f a ha).2.val-r = a+D-R := by dsimp [f]; omega simpa only [he] using hbb.2 · dsimp [f] omega · intro a ha a' ha' he have heval := congrArg (fun p : Fin g × Fin g => p.1.val) he dsimp [f] at heval omega · intro p hp have hdist := (mem_filter.mp hp).2 have hparts := mem_product.mp (mem_filter.mp hp).1 have hri := (mem_filter.mp hparts.1).2.1 have hbi := (mem_filter.mp hparts.1).2.2 have hjr := (mem_filter.mp hparts.2).2.1 have hbj := (mem_filter.mp hparts.2).2.2 have haR : p.1.val-r < R := by omega have haoff : (p.1.val-r)+D-R = D+p.2.val-r := by omega have ha : p.1.val-r ∈ S := by apply mem_filter.mpr refine ⟨mem_range.mpr haR, ?_⟩ simp only [Bool.and_eq_true, haoff] exact ⟨hbi, hbj⟩ refine ⟨p.1.val-r, ha, ?_⟩ apply Prod.ext <;> apply Fin.ext <;> dsimp [f] <;> omega