cycle_power_gap_ordinary_side_cover
Ordinary distance coverage in an integer radius-D model, restricted to g at most D, gives a cut-separated biclique cover of the complete ordered graph on Fin g.
Statement
theorem cycle_power_gap_ordinary_side_cover
(D g : ℕ) (hg : g ≤ D) (x : ℤ → ℕ → Bool)
(hcover : ∀ d : ℕ, 1 ≤ d → d < D → ∀ v : ℤ,
∃ a : ℕ, a < D-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) :
∀ i j : Fin g, i < j → ∃ r : Fin (g-1),
i ∈ cycle_power_gap_right_side D g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) ∧
j ∈ cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ))- 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 2
- 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.
- Used by 1
- cycle_power_dyadic_full_gap_sides_convexIn a tight exact full ordinary-coverage dyadic model, all compressed sides between full roots zero and g are intervals when g lies between…
The proof, explained
To cover an arbitrary ordered pair $i < j$ in $\text{Fin } g$, the proof explicitly constructs a cut index $r \in \text{Fin}(g - 1)$. Setting the distance parameter to $d = D - (j - i)$, the hypothesis $g \le D$ guarantees $1 \le d < D$, allowing the coverage assumption to produce an offset $a < j - i$ where the Boolean sequence $x(j - a)$ is true at both $a$ and $a + d$. Defining the cut point by $r + 1 = j - a$ separates the vertices as $i < r + 1 \le j$. Under this choice, the wrap-around offset $D + i - (r + 1) = a + d$ and forward offset $j - (r + 1) = a$ match the two true points of $x(j - a)$, placing $i$ in the right side and $j$ in the left side of the biclique.
Let $i, j \in \text{Fin } g$ be vertices with $i < j$.
We introduce the two vertices $i$ and $j$ together with the ordering hypothesis $i < j$, extracting the inequalities $i < g$, $j < g$, and $i < j$ on their numerical values.
intro i j hij have hi : i.val < g := i.isLt have hj : j.val < g := j.isLt have hij' : i.val < j.val := hij
The complementary distance $d = D - (j - i)$ satisfies $1 \le d < D$.
Defining $d = D - (j - i)$, the bounds $0 \le i < j < g \le D$ ensure that $1 \le j - i < D$, so linear arithmetic (`omega`) confirms that $1 \le d$ and $d < D$.
let d := D-(j.val-i.val) have hd₀ : 1 ≤ d := by dsimp [d]; omega have hdD : d < D := by dsimp [d]; omega
There exists an offset $a < D - d$ such that $x(j - a, a) = \text{true}$ and $x(j - a, a + d) = \text{true}$.
We apply the coverage hypothesis `hcover` at distance $d$ and base coordinate $v = j$ (cast to an integer) to obtain an offset $a < D - d$ where the Boolean sequence $x(j - a)$ is true at both $a$ and $a + d$.
obtain ⟨a, ha, h₀, h₁⟩ := hcover d hd₀ hdD (j.val : ℤ)The offset $a$ satisfies $a < j - i$, and setting $r = j - a - 1 \in \text{Fin}(g - 1)$ gives $r + 1 = j - a$, $j - (r + 1) = a$, and $D + i - (r + 1) = a + d$.
Since $D - d = j - i$, the bound $a < D - d$ simplifies to $a < j - i$. Because $i \ge 0$ and $j < g$, the integer $j - a - 1$ is strictly less than $g - 1$, giving a well-defined cut index $r \in \text{Fin}(g - 1)$ satisfying $r + 1 = j - a$. Linear arithmetic verifies the shift identities $j - (r + 1) = a$ and $D + i - (r + 1) = a + d$.
have ha' : a < j.val-i.val := by dsimp [d] at ha; omega let r : Fin (g-1) := ⟨j.val-a-1, by omega⟩ have hr : r.val+1 = j.val-a := by dsimp [r]; omega have hroot : (j.val : ℤ)-(a : ℤ) = ((r.val+1 : ℕ) : ℤ) := by omega have ha₀ : j.val-(r.val+1) = a := by omega have ha₁ : D+i.val-(r.val+1) = a+d := by dsimp [d]; omega
The index $r$ provides the existential witness for the cut.
We instantiate the existential goal with $r$, splitting the goal into proving that $i$ lies in the right-side set and $j$ lies in the left-side set of the cut at $r + 1$.
refine ⟨r, ?_, ?_⟩The vertex $i$ belongs to `cycle_power_gap_right_side D g (r + 1) (x (r + 1))`.
By definition of `cycle_power_gap_right_side` as a filtered subset of `univ` (via `mem_filter.mpr`), $i$ belongs to this set if $i \in \text{univ}$ (via `mem_univ`), $i < r + 1$, and $x(r + 1)(D + i - (r + 1)) = \text{true}$. The inequality $i < r + 1$ holds by linear arithmetic since $r + 1 = j - a > i$. Rewriting $D + i - (r + 1)$ as $a + d$ and using $r + 1 = j - a$, the Boolean condition matches the coverage hypothesis $h_1$.
uses
mem_filter.mpr,mem_univ· apply mem_filter.mpr refine ⟨mem_univ _, by omega, ?_⟩ rw [ha₁] simpa only [hroot] using h₁
The vertex $j$ belongs to `cycle_power_gap_left_side g (r + 1) (x (r + 1))`.
By definition of `cycle_power_gap_left_side` as a filtered subset of `univ` (via `mem_filter.mpr`), $j$ belongs to this set if $j \in \text{univ}$ (via `mem_univ`), $r + 1 \le j$, and $x(r + 1)(j - (r + 1)) = \text{true}$. The inequality $r + 1 \le j$ holds since $r + 1 = j - a \le j$. Rewriting $j - (r + 1)$ as $a$ and using $r + 1 = j - a$, the Boolean condition matches the coverage hypothesis $h_0$.
uses
mem_filter.mpr,mem_univ· apply mem_filter.mpr refine ⟨mem_univ _, by omega, ?_⟩ rw [ha₀] simpa only [hroot] using h₀
mem_filter.mpr- An element belongs to a filtered finset if it belongs to the base finset and satisfies the filtering predicate.
mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
- The natural-number arithmetic involving bounded differences (such as `d = D - (j - i)` and `r = j - a - 1`) and inequality bounds is discharged automatically by Lean's `omega` tactic.
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_ordinary_side_cover (D g : ℕ) (hg : g ≤ D) (x : ℤ → ℕ → Bool) (hcover : ∀ d : ℕ, 1 ≤ d → d < D → ∀ v : ℤ, ∃ a : ℕ, a < D-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) : ∀ i j : Fin g, i < j → ∃ r : Fin (g-1), i ∈ cycle_power_gap_right_side D g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) ∧ j ∈ cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) := by intro i j hij have hi : i.val < g := i.isLt have hj : j.val < g := j.isLt have hij' : i.val < j.val := hij let d := D-(j.val-i.val) have hd₀ : 1 ≤ d := by dsimp [d]; omega have hdD : d < D := by dsimp [d]; omega obtain ⟨a, ha, h₀, h₁⟩ := hcover d hd₀ hdD (j.val : ℤ) have ha' : a < j.val-i.val := by dsimp [d] at ha; omega let r : Fin (g-1) := ⟨j.val-a-1, by omega⟩ have hr : r.val+1 = j.val-a := by dsimp [r]; omega have hroot : (j.val : ℤ)-(a : ℤ) = ((r.val+1 : ℕ) : ℤ) := by omega have ha₀ : j.val-(r.val+1) = a := by omega have ha₁ : D+i.val-(r.val+1) = a+d := by dsimp [d]; omega refine ⟨r, ?_, ?_⟩ · apply mem_filter.mpr refine ⟨mem_univ _, by omega, ?_⟩ rw [ha₁] simpa only [hroot] using h₁ · apply mem_filter.mpr refine ⟨mem_univ _, by omega, ?_⟩ rw [ha₀] simpa only [hroot] using h₀