AFTD Auto-Formalizing Theoretical Domains

cycle_power_gap_ordinary_side_cover

theoremverified

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
Used by 1

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.

  1. 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.

    lines 12–15

      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
  2. 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$.

    lines 16–18

      let d := D-(j.val-i.val)
      have hd₀ : 1 ≤ d := by dsimp [d]; omega
      have hdD : d < D := by dsimp [d]; omega
  3. 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$.

    line 19

      obtain ⟨a, ha, h₀, h₁⟩ := hcover d hd₀ hdD (j.val : ℤ)
  4. 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$.

    lines 20–25

      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
  5. 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$.

    line 26

      refine ⟨r, ?_, ?_⟩
  6. 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$.

    lines 27–30

    uses mem_filter.mpr, mem_univ

      · apply mem_filter.mpr
        refine ⟨mem_univ _, by omega, ?_⟩
        rw [ha₁]
        simpa only [hroot] using h₁
  7. 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$.

    lines 31–34

    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`.

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

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₀
See it in the graphDiscuss this resultChallenge it