AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_full_gap_class_no_island

theoremverified

In a tight exact full ordinary-coverage dyadic model, every class rooted strictly between full roots zero and g has no selected island between missing offsets, when g lies between half and the full radius.

Statement

theorem cycle_power_dyadic_full_gap_class_no_island
    (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)
    (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) =
      (range (2^m)).sum (fun i => (x p i).toNat))
    (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ,
      ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true)
    (g : ℕ) (hlo : 2^(m-1) ≤ g) (hg : g ≤ 2^m)
    (hfull₀ : ∀ i < 2^m, x 0 i = true)
    (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) :
    ∀ r : ℕ, 0 < r → r < g → ∀ a b c : ℕ, a < b → b < c → c < 2^m →
      x (r : ℤ) a = false → x (r : ℤ) b = true → x (r : ℤ) c = true
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 6
Used by 1

The proof, explained

To show that a missing offset a cannot be followed by an isolated selected offset b without all subsequent offsets c > b also being selected, the proof uses the convexity of the gap sides of intermediate root classes. An overlap-gap lemma partitions the possibilities for the selected offset b into either the left gap side (r + b < g) or the right gap side (2^m ≤ r + b). If b were on the left side, convexity between the endpoint offset 0 and b would force offset a to be selected, contradicting that a is missing. Thus b must lie on the right side, where convexity between b and the right endpoint 2^m - 1 forces any subsequent offset c to be selected.

  1. The left and right gap sides of each root class r ∈ (0, g) are convex subsets of Fin g.

    Using the hypotheses that the dyadic model is tight, exact, and covering, with full roots at 0 and g satisfying 2^(m-1) ≤ g ≤ 2^m, lemma cycle_power_dyadic_full_gap_sides_convex establishes that for every intermediate root class r, both the left gap side (offsets i - r for r ≤ i < g) and the right gap side (offsets 2^m + i - r for i < r) are order-convex in Fin g.

    lines 18–20

    uses cycle_power_dyadic_full_gap_sides_convex

      classical
      have hconv := cycle_power_dyadic_full_gap_sides_convex m hm x htight hexact hcover
        g hlo hg hfull₀ hfullg
  2. Fix an intermediate root r ∈ (0, g) and three ordered offsets a < b < c < 2^m with x(r, a) = false and x(r, b) = true.

    We introduce the root r with 0 < r < g, the offsets a < b < c < 2^m, and the assumptions that a is unselected (x(r, a) = false) while b is selected (x(r, b) = true); the remaining goal is to prove that c must also be selected (x(r, c) = true).

    line 21

      intro r hr₀ hrg a b c hab hbc hcD hxa hxb
  3. The endpoint offsets 0 and 2^m - 1 are selected, and either r + b < g or 2^m ≤ r + b.

    We represent r as q.val + 1 with q ∈ Fin (g - 1) via linear arithmetic. Lemma cycle_power_dyadic_exact_endpoints shows that the exactness hypothesis forces x(r, 0) = true and x(r, 2^m - 1) = true. Lemma cycle_power_dyadic_two_full_roots_overlap_empty applied to the selected offset b proves that b cannot lie in the overlap gap, giving the disjunction r + b < g ∨ 2^m ≤ r + b. Finally, rcases splits the proof into these two cases.

    lines 22–27

    uses cycle_power_dyadic_exact_endpoints, cycle_power_dyadic_two_full_roots_overlap_empty

      let q : Fin (g-1) := ⟨r-1, by omega⟩
      have hq : q.val+1 = r := by dsimp [q]; omega
      have hends := cycle_power_dyadic_exact_endpoints m hm x hexact (r : ℤ)
      have hgap := cycle_power_dyadic_two_full_roots_overlap_empty m hm x htight hexact
        g hg hfull₀ hfullg r hr₀ hrg b (by omega) hxb
      rcases hgap with hleft | hright
  4. The case r + b < g is impossible.

    In the first case where r + b < g, we consider the elements i = r, j = r + a, and k = r + b in Fin g, which satisfy i ≤ j ≤ k because a < b. The index i belongs to the left gap side because its offset is i - r = 0 (by Nat.sub_self) and x(r, 0) = true. The index k belongs to the left gap side because its offset is k - r = b (by Nat.add_sub_cancel_left) and x(r, b) = true. By the convexity of the left gap side, the intermediate index j must also belong to the left gap side, which means x(r, j - r) = x(r, a) = true. This contradicts the assumption x(r, a) = false.

    lines 28–46

    uses mem_filter.mpr, mem_univ, le_rfl, Nat.sub_self, Nat.add_sub_cancel_left, mem_filter.mp

      · let i : Fin g := ⟨r, hrg⟩
        let j : Fin g := ⟨r+a, by omega⟩
        let k : Fin g := ⟨r+b, hleft⟩
        have hi : i ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by
          apply mem_filter.mpr
          refine ⟨mem_univ _, le_rfl, ?_⟩
          simpa only [i, Nat.sub_self] using hends.1
        have hk : k ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by
          apply mem_filter.mpr
          refine ⟨mem_univ _, by dsimp [k]; omega, ?_⟩
          simpa only [k, Nat.add_sub_cancel_left] using hxb
        have hi' : i ∈ cycle_power_gap_left_side g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hi
        have hk' : k ∈ cycle_power_gap_left_side g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hk
        have hj := hconv.1 q i j k (by change r ≤ r+a; omega) (by change r+a ≤ r+b; omega) hi' hk'
        have hj' : j ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by simpa only [hq] using hj
        have he := (mem_filter.mp hj').2.2
        have ha : x (r : ℤ) a = true := by simpa only [j, Nat.add_sub_cancel_left] using he
        rw [hxa] at ha
        contradiction
  5. In the case 2^m ≤ r + b, the offset c is selected: x(r, c) = true.

    In the second case where 2^m ≤ r + b, we define indices i = r + b - 2^m, j = r + c - 2^m, and k = r - 1 in Fin g, which satisfy i ≤ j ≤ k because b < c < 2^m. The index i belongs to the right gap side because its corresponding offset is 2^m + i - r = b and x(r, b) = true. The index k belongs to the right gap side because its corresponding offset is 2^m + k - r = 2^m - 1 and x(r, 2^m - 1) = true. By the convexity of the right gap side, the intermediate index j also belongs to the right gap side, which implies its offset 2^m + j - r = c is selected, giving x(r, c) = true.

    lines 47–67

    uses mem_filter.mpr, mem_univ, mem_filter.mp

      · let i : Fin g := ⟨r+b-2^m, by omega⟩
        let j : Fin g := ⟨r+c-2^m, by omega⟩
        let k : Fin g := ⟨r-1, by omega⟩
        have hi : i ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by
          apply mem_filter.mpr
          refine ⟨mem_univ _, by dsimp [i]; omega, ?_⟩
          have he : 2^m+i.val-r = b := by dsimp [i]; omega
          simpa only [he] using hxb
        have hk : k ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by
          apply mem_filter.mpr
          refine ⟨mem_univ _, by dsimp [k]; omega, ?_⟩
          have he : 2^m+k.val-r = 2^m-1 := by dsimp [k]; omega
          simpa only [he] using hends.2
        have hi' : i ∈ cycle_power_gap_right_side (2^m) g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hi
        have hk' : k ∈ cycle_power_gap_right_side (2^m) g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hk
        have hj := hconv.2 q i j k (by change r+b-2^m ≤ r+c-2^m; omega)
          (by change r+c-2^m ≤ r-1; omega) hi' hk'
        have hj' : j ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by simpa only [hq] using hj
        have he := (mem_filter.mp hj').2.2
        have hoff : 2^m+j.val-r = c := by dsimp [j]; omega
        simpa only [hoff] using he
cycle_power_dyadic_full_gap_sides_convex
In a tight, exact, covering dyadic model with full roots at 0 and g, both the left gap side and the right gap side of any intermediate root class are order-convex subsets of Fin g.
cycle_power_dyadic_exact_endpoints
Under the exactness condition, every class has its extreme offsets 0 and 2^m - 1 selected.
cycle_power_dyadic_two_full_roots_overlap_empty
For any intermediate root class r between full roots 0 and g, any selected offset a satisfies either r + a < g or 2^m ≤ r + a.
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, it belongs to the base finset and satisfies the filtering predicate.
mem_univ
Every element of a finite type belongs to the universal finset univ.
le_rfl
The ordering relation ≤ is reflexive: a ≤ a for every element a.
Nat.sub_self
Subtracting a natural number from itself gives zero: n - n = 0.
Nat.add_sub_cancel_left
Adding and then subtracting the same natural number cancels: (n + m) - n = m.

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_dyadic_full_gap_class_no_island    (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)    (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) =      (range (2^m)).sum (fun i => (x p i).toNat))    (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ,      ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true)    (g : ℕ) (hlo : 2^(m-1) ≤ g) (hg : g ≤ 2^m)    (hfull₀ : ∀ i < 2^m, x 0 i = true)    (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) :    ∀ r : ℕ, 0 < r → r < g → ∀ a b c : ℕ, a < b → b < c → c < 2^m →      x (r : ℤ) a = false → x (r : ℤ) b = true → x (r : ℤ) c = true := by  classical  have hconv := cycle_power_dyadic_full_gap_sides_convex m hm x htight hexact hcover    g hlo hg hfull₀ hfullg  intro r hr₀ hrg a b c hab hbc hcD hxa hxb  let q : Fin (g-1) := ⟨r-1, by omega⟩  have hq : q.val+1 = r := by dsimp [q]; omega  have hends := cycle_power_dyadic_exact_endpoints m hm x hexact (r : ℤ)  have hgap := cycle_power_dyadic_two_full_roots_overlap_empty m hm x htight hexact    g hg hfull₀ hfullg r hr₀ hrg b (by omega) hxb  rcases hgap with hleft | hright  · let i : Fin g := ⟨r, hrg⟩    let j : Fin g := ⟨r+a, by omega⟩    let k : Fin g := ⟨r+b, hleft⟩    have hi : i ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by      apply mem_filter.mpr      refine ⟨mem_univ _, le_rfl, ?_⟩      simpa only [i, Nat.sub_self] using hends.1    have hk : k ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by      apply mem_filter.mpr      refine ⟨mem_univ _, by dsimp [k]; omega, ?_⟩      simpa only [k, Nat.add_sub_cancel_left] using hxb    have hi' : i ∈ cycle_power_gap_left_side g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hi    have hk' : k ∈ cycle_power_gap_left_side g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hk    have hj := hconv.1 q i j k (by change r ≤ r+a; omega) (by change r+a ≤ r+b; omega) hi' hk'    have hj' : j ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by simpa only [hq] using hj    have he := (mem_filter.mp hj').2.2    have ha : x (r : ℤ) a = true := by simpa only [j, Nat.add_sub_cancel_left] using he    rw [hxa] at ha    contradiction  · let i : Fin g := ⟨r+b-2^m, by omega⟩    let j : Fin g := ⟨r+c-2^m, by omega⟩    let k : Fin g := ⟨r-1, by omega⟩    have hi : i ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by      apply mem_filter.mpr      refine ⟨mem_univ _, by dsimp [i]; omega, ?_⟩      have he : 2^m+i.val-r = b := by dsimp [i]; omega      simpa only [he] using hxb    have hk : k ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by      apply mem_filter.mpr      refine ⟨mem_univ _, by dsimp [k]; omega, ?_⟩      have he : 2^m+k.val-r = 2^m-1 := by dsimp [k]; omega      simpa only [he] using hends.2    have hi' : i ∈ cycle_power_gap_right_side (2^m) g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hi    have hk' : k ∈ cycle_power_gap_right_side (2^m) g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hk    have hj := hconv.2 q i j k (by change r+b-2^m ≤ r+c-2^m; omega)      (by change r+c-2^m ≤ r-1; omega) hi' hk'    have hj' : j ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by simpa only [hq] using hj    have he := (mem_filter.mp hj').2.2    have hoff : 2^m+j.val-r = c := by dsimp [j]; omega    simpa only [hoff] using he
See it in the graphDiscuss this resultChallenge it