AFTD Auto-Formalizing Theoretical Domains

cycle_power_gap_exact_side_owner

theoremverified

Exact distance D-R ownership in an integer model gives unique compressed gap-side owners for every forward distance-R pair on Fin g, when R and g are at most D.

Statement

theorem cycle_power_gap_exact_side_owner
    (D R g : ℕ) (hRD : R ≤ D) (hg : g ≤ D) (x : ℤ → ℕ → Bool)
    (hexact : ∀ v : ℤ, (range R).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1) :
    ∀ i j : Fin g, j.val+R = i.val → ∃! r : Fin (g-1),
      i ∈ cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) ∧
      j ∈ cycle_power_gap_right_side D 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 4
Used by 1

The proof, explained

To show that every forward pair (i, j) on Fin g at distance R (so j + R = i) has a unique gap owner r ∈ Fin (g - 1), the proof matches gap-side membership to exact ownership at base coordinate i. Applying the exact ownership hypothesis at coordinate i yields an offset a < R, which defines a candidate owner r = i - a - 1 ∈ Fin (g - 1). Verifying the filter conditions demonstrates that i lies in the left gap side and j lies in the right gap side of r. Conversely, the side-membership conditions for any owner s induce an offset b = i - (s + 1) < R satisfying the same boolean equations, so uniqueness of the offset forces b = a and consequently s = r.

  1. For any pair of vertices i, j ∈ Fin g separated by forward distance R (so j + R = i), there exists an offset a < R such that x(i - a, a) = true and x(i - a, a + D - R) = true.

    Fix vertices i, j ∈ Fin g satisfying j + R = i. Applying the exact ownership hypothesis cycle_power_exact_pair_exists at base coordinate v = i yields an offset a < R satisfying x(i - a, a) = true and x(i - a, a + D - R) = true. We also record that i < g and j < g.

    lines 12–15

    uses cycle_power_exact_pair_exists

      intro i j hdist
      obtain ⟨a, ha, h₀, h₁⟩ := cycle_power_exact_pair_exists D R x hexact (i.val : ℤ)
      have hi : i.val < g := i.isLt
      have hj : j.val < g := j.isLt
  2. The index r = i - a - 1 is a well-defined element of Fin (g - 1) satisfying r + 1 = i - a, left offset i - (r + 1) = a, and right offset D + j - (r + 1) = a + D - R.

    Since a < R ≤ i < g, the integer i - a - 1 is non-negative and strictly less than g - 1, defining r ∈ Fin (g - 1). Elementary arithmetic verifies that r + 1 = i - a, that the left offset i - (r + 1) is a, and, using j + R = i, that the right offset D + j - (r + 1) equals a + D - R.

    lines 16–20

      let r : Fin (g-1) := ⟨i.val-a-1, by omega⟩
      have hr : r.val+1 = i.val-a := by dsimp [r]; omega
      have hroot : (i.val : ℤ)-(a : ℤ) = ((r.val+1 : ℕ) : ℤ) := by omega
      have ha₀ : i.val-(r.val+1) = a := by omega
      have ha₁ : D+j.val-(r.val+1) = a+D-R := by omega
  3. The vertex i belongs to the left gap side for r, namely i ∈ cycle_power_gap_left_side g (r + 1) (x (r + 1)).

    By definition of cycle_power_gap_left_side, membership requires r + 1 ≤ i and x(r + 1, i - (r + 1)) = true. Applying mem_filter.mpr and mem_univ, the inequality r + 1 ≤ i holds since r + 1 = i - a ≤ i. Rewriting i - (r + 1) as a and r + 1 as i - a transforms the predicate into x(i - a, a) = true, which holds by choice of a.

    lines 21–25

    uses mem_filter.mpr, mem_univ

      have hAr : i ∈ cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) := by
        apply mem_filter.mpr
        refine ⟨mem_univ _, by omega, ?_⟩
        rw [ha₀]
        simpa only [hroot] using h₀
  4. The vertex j belongs to the right gap side for r, namely j ∈ cycle_power_gap_right_side D g (r + 1) (x (r + 1)).

    By definition of cycle_power_gap_right_side, membership requires j < r + 1 and x(r + 1, D + j - (r + 1)) = true. Applying mem_filter.mpr and mem_univ, j < r + 1 holds because r + 1 = j + R - a > j since a < R. Rewriting D + j - (r + 1) as a + D - R and r + 1 as i - a turns the condition into x(i - a, a + D - R) = true, which also holds by choice of a.

    lines 26–30

    uses mem_filter.mpr, mem_univ

      have hBr : j ∈ cycle_power_gap_right_side D g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) := by
        apply mem_filter.mpr
        refine ⟨mem_univ _, by omega, ?_⟩
        rw [ha₁]
        simpa only [hroot] using h₁
  5. The index r witnesses ownership of the pair (i, j), reducing unique existence to proving that any valid owner equals r.

    Supplying r along with the proofs of left and right membership satisfies the existential requirement, leaving the uniqueness claim: any owner s ∈ Fin (g - 1) must be equal to r.

    line 31

      refine ⟨r, ⟨hAr, hBr⟩, ?_⟩
  6. Any candidate owner s ∈ Fin (g - 1) satisfies s + 1 ≤ i, j < s + 1, x(s + 1, i - (s + 1)) = true, and x(s + 1, D + j - (s + 1)) = true.

    Assuming s ∈ Fin (g - 1) satisfies the left and right gap side conditions, unpacking the set filter definitions using mem_filter.mp extracts the inequalities s + 1 ≤ i and j < s + 1, along with the boolean equalities x(s + 1, i - (s + 1)) = true and x(s + 1, D + j - (s + 1)) = true.

    lines 32–34

    uses mem_filter.mp

      intro s hs
      have his := (mem_filter.mp hs.1).2
      have hjs := (mem_filter.mp hs.2).2
  7. The offset b = i - (s + 1) satisfies b < R, i - b = s + 1, and b + D - R = D + j - (s + 1).

    Defining b = i - (s + 1), linear arithmetic using j < s + 1 and i = j + R confirms that b < i - j = R. Rearranging yields i - b = s + 1 and b + D - R = D + j - (s + 1).

    lines 35–38

      let b := i.val-(s.val+1)
      have hb : b < R := by dsimp [b]; omega
      have hroot' : (i.val : ℤ)-(b : ℤ) = ((s.val+1 : ℕ) : ℤ) := by dsimp [b]; omega
      have hboff : b+D-R = D+j.val-(s.val+1) := by dsimp [b]; omega
  8. The offset b satisfies x(i - b, b) = true and x(i - b, b + D - R) = true.

    Substituting s + 1 = i - b and D + j - (s + 1) = b + D - R into the boolean conditions obtained for s shows that b satisfies both ownership conditions at base coordinate i.

    lines 39–42

      have hb₀ : x ((i.val : ℤ)-(b : ℤ)) b = true := by
        simpa only [hroot', b] using his.2
      have hb₁ : x ((i.val : ℤ)-(b : ℤ)) (b+D-R) = true := by
        simpa only [hroot', hboff] using hjs.2
  9. The candidate s equals r, establishing uniqueness of the owner.

    Because both a and b are offsets strictly less than R satisfying the pair conditions at base coordinate i, cycle_power_exact_pair_unique forces a = b. Substituting a = i - (r + 1) and b = i - (s + 1) into this equality yields s.val = r.val by linear arithmetic. Applying Fin.ext concludes that s = r.

    lines 43–48

    uses cycle_power_exact_pair_unique, Fin.ext

      have he := cycle_power_exact_pair_unique D R x hexact (i.val : ℤ)
        a b ha hb h₀ h₁ hb₀ hb₁
      apply Fin.ext
      dsimp [b] at he
      have hslt : s.val < g-1 := s.isLt
      omega
cycle_power_exact_pair_exists
Given exact distance D-R ownership, for every integer coordinate v there exists an offset a < R such that both x(v - a, a) and x(v - a, a + D - R) are true.
cycle_power_exact_pair_unique
Given exact distance D-R ownership, for every integer coordinate v there is at most one offset a < R satisfying x(v - a, a) = true and x(v - a, a + D - R) = true.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
mem_univ
Every element of a finite type belongs to the universal finset univ.
mem_filter.mpr
An element belongs to a filtered finset if it belongs to the base finset and satisfies the filtering predicate.
mem_filter.mp
If an element belongs to a filtered finset, then it belongs to the base finset and satisfies the filtering predicate.

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_exact_side_owner    (D R g : ℕ) (hRD : R ≤ D) (hg : g ≤ D) (x : ℤ → ℕ → Bool)    (hexact : ∀ v : ℤ, (range R).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1) :    ∀ i j : Fin g, j.val+R = i.val → ∃! r : Fin (g-1),      i ∈ cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) ∧      j ∈ cycle_power_gap_right_side D g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) := by  intro i j hdist  obtain ⟨a, ha, h₀, h₁⟩ := cycle_power_exact_pair_exists D R x hexact (i.val : ℤ)  have hi : i.val < g := i.isLt  have hj : j.val < g := j.isLt  let r : Fin (g-1) := ⟨i.val-a-1, by omega⟩  have hr : r.val+1 = i.val-a := by dsimp [r]; omega  have hroot : (i.val : ℤ)-(a : ℤ) = ((r.val+1 : ℕ) : ℤ) := by omega  have ha₀ : i.val-(r.val+1) = a := by omega  have ha₁ : D+j.val-(r.val+1) = a+D-R := by omega  have hAr : i ∈ cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) := by    apply mem_filter.mpr    refine ⟨mem_univ _, by omega, ?_⟩    rw [ha₀]    simpa only [hroot] using h₀  have hBr : j ∈ cycle_power_gap_right_side D g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) := by    apply mem_filter.mpr    refine ⟨mem_univ _, by omega, ?_⟩    rw [ha₁]    simpa only [hroot] using h₁  refine ⟨r, ⟨hAr, hBr⟩, ?_⟩  intro s hs  have his := (mem_filter.mp hs.1).2  have hjs := (mem_filter.mp hs.2).2  let b := i.val-(s.val+1)  have hb : b < R := by dsimp [b]; omega  have hroot' : (i.val : ℤ)-(b : ℤ) = ((s.val+1 : ℕ) : ℤ) := by dsimp [b]; omega  have hboff : b+D-R = D+j.val-(s.val+1) := by dsimp [b]; omega  have hb₀ : x ((i.val : ℤ)-(b : ℤ)) b = true := by    simpa only [hroot', b] using his.2  have hb₁ : x ((i.val : ℤ)-(b : ℤ)) (b+D-R) = true := by    simpa only [hroot', hboff] using hjs.2  have he := cycle_power_exact_pair_unique D R x hexact (i.val : ℤ)    a b ha hb h₀ h₁ hb₀ hb₁  apply Fin.ext  dsimp [b] at he  have hslt : s.val < g-1 := s.isLt  omega
See it in the graphDiscuss this resultChallenge it