AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_class_no_island_of_full_class_cover

theoremverified

A positive-exponent integer dyadic rooted-class model with tight weights, exact dyadic pair ownership, all ordinary distance coverage, and a full class covering every vertex has no selected island between two missing offsets in any class.

Statement

theorem cycle_power_dyadic_class_no_island_of_full_class_cover
    (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)
    (hfullcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^m ∧ ∀ i < 2^m, x (v-(a : ℤ)) i = true) :
    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m →
      x p a = false → x p b = true → x p 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 4
Used by 1

The proof, explained

The theorem establishes that no class in the model can contain an 'island'—a true value flanked by false values at lower and higher offsets. Because class p has a false offset at a, it is not completely full, and the full-class covering hypothesis brackets p strictly between two full classes at distance at most 2^m. After shifting coordinates so the left full class is at the origin, the exact dyadic ownership condition forces the gap between the two full classes to be at least 2^(m - 1). The structural theorem for dyadic models within such a full-class gap then guarantees that the intermediate class p cannot contain an island, forcing offset c to be true.

  1. Fix an arbitrary class index p and increasing offsets a < b < c < 2^m, assuming x(p, a) = false and x(p, b) = true.

    We introduce the universal variables and hypotheses, setting the goal to prove that offset c is true (x(p, c) = true).

    lines 16–17

      classical
      intro p a b c hab hbc hcD hxa hxb
  2. Class p is not completely full (it does not have all offsets < 2^m set to true).

    If every offset in class p were true, then in particular offset a would be true, directly contradicting the assumption that x(p, a) = false.

    lines 18–22

      have hp : ¬(∀ i < 2^m, x p i = true) := by
        intro h
        have := h a (by omega)
        rw [hxa] at this
        contradiction
  3. There exist positive offsets l, r > 0 with l + r ≤ 2^m such that classes p - l and p + r are both completely full.

    Because full classes cover every integer within distance 2^m (by hypothesis hfullcover) and p is not itself a full class, int_dense_marks_bracket ensures that p is strictly bracketed between a full class p - l to its left and a full class p + r to its right, with total separation l + r ≤ 2^m.

    lines 23–24

    uses int_dense_marks_bracket

      obtain ⟨l, r, hl₀, hr₀, hlr, hFl, hFr⟩ := int_dense_marks_bracket
        (2^m) (fun q => ∀ i < 2^m, x q i = true) hfullcover p hp
  4. Define the shifted configuration y(q, i) = x(p - l + q, i), under which y(l) coincides with x(p).

    We shift the class coordinates by p - l so that the left full class p - l is positioned at the origin 0, placing class p at coordinate l.

    lines 25–26

      let y : ℤ → ℕ → Bool := fun q i => x ((p-(l : ℤ))+q) i
      have hyroot : ∀ i, y (l : ℤ) i = x p i := by intro i; dsimp [y]; congr 1; omega
  5. The shifted configuration y inherits the tight-weight, exact dyadic pair ownership, and distance coverage conditions.

    The model conditions are translation-invariant along the integers. Reassociating integer subtraction via add_sub_assoc shows that shifting by p - l preserves all three properties.

    lines 27–38

    uses add_sub_assoc

      have hytight : ∀ q : ℤ, cycle_power_dyadic_class_weight m (y q) =
          (range (2^m)).sum (fun i => (y q i).toNat) := by
        intro q
        exact htight ((p-(l : ℤ))+q)
      have hyexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>
          (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1 := by
        intro j hj v
        simpa only [y, add_sub_assoc] using hexact j hj ((p-(l : ℤ))+v)
      have hycover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ,
          ∃ a : ℕ, a < 2^m-d ∧ y (v-(a : ℤ)) a = true ∧ y (v-(a : ℤ)) (a+d) = true := by
        intro d hd₀ hdD v
        simpa only [y, add_sub_assoc] using hcover d hd₀ hdD ((p-(l : ℤ))+v)
  6. The shifted configuration y has full classes at coordinate 0 and coordinate l + r.

    Coordinate 0 in y corresponds to p - l (using add_zero), which is full by the definition of l. Coordinate l + r corresponds to (p - l) + (l + r) = p + r, which is full by the definition of r.

    lines 39–45

    uses add_zero

      have hyfull₀ : ∀ i < 2^m, y 0 i = true := by
        intro i hi
        simpa only [y, add_zero] using hFl i hi
      have hyfullg : ∀ i < 2^m, y ((l+r : ℕ) : ℤ) i = true := by
        intro i hi
        have hroot : (p-(l : ℤ))+((l+r : ℕ) : ℤ) = p+(r : ℤ) := by omega
        simpa only [y, hroot] using hFr i hi
  7. The separation between the two full classes satisfies 2^(m - 1) ≤ l + r.

    Using pow_succ and ring arithmetic, 2^m = 2 * 2^(m - 1). Applying cycle_power_two_full_roots_half_separated at the largest dyadic scale j = m - 1, the presence of two full classes at 0 and l + r > 0 under exact dyadic ownership implies that the gap l + r must be at least 2^(m - 1).

    lines 46–51

    uses pow_succ, cycle_power_two_full_roots_half_separated

      have hD : 2^m = 2*2^(m-1) := by
        have he : m = (m-1)+1 := by omega
        conv_lhs => rw [he, pow_succ]
        ring
      have hlo := cycle_power_two_full_roots_half_separated (2^m) (2^(m-1)) hD y
        (hyexact (m-1) (by omega)) (l+r) (by omega) hyfull₀ hyfullg
  8. x(p, c) = true, showing that no island occurs.

    By cycle_power_dyadic_full_gap_class_no_island, any intermediate class strictly between two full classes separated by a gap g with 2^(m - 1) ≤ g ≤ 2^m cannot have an isolated true value. Since 0 < l < l + r, class l is intermediate; since y(l, a) = false and y(l, b) = true, offset c must be true in y(l). Since y(l) = x(p), we conclude x(p, c) = true.

    lines 52–55

    uses cycle_power_dyadic_full_gap_class_no_island

      have hshape := cycle_power_dyadic_full_gap_class_no_island m hm y hytight hyexact hycover
        (l+r) hlo hlr hyfull₀ hyfullg l hl₀ (by omega) a b c hab hbc hcD
          (by simpa only [hyroot] using hxa) (by simpa only [hyroot] using hxb)
      simpa only [hyroot] using hshape
int_dense_marks_bracket
If every integer is within distance D of some integer satisfying property F, then any point p not satisfying F is strictly bracketed by points p - l and p + r satisfying F, with l, r > 0 and l + r ≤ D.
add_sub_assoc
In any additive group or monoid with subtraction, a + b - c = a + (b - c).
add_zero
Adding zero to an element leaves it unchanged: a + 0 = a.
pow_succ
In a monoid, a^(n + 1) = a^n * a.
cycle_power_two_full_roots_half_separated
In a block of length D = 2R where exact ownership holds for offset difference D - R = R, any two full classes at 0 and g > 0 must be separated by at least R (that is, R ≤ g).
cycle_power_dyadic_full_gap_class_no_island
In a tight dyadic class model with full classes at 0 and g separated by 2^(m - 1) ≤ g ≤ 2^m, every intermediate class r strictly between 0 and g has no isolated true values: if a < b < c < 2^m with offset a false and offset b true, then offset c must be true.

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_class_no_island_of_full_class_cover    (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)    (hfullcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^m ∧ ∀ i < 2^m, x (v-(a : ℤ)) i = true) :    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m →      x p a = false → x p b = true → x p c = true := by  classical  intro p a b c hab hbc hcD hxa hxb  have hp : ¬(∀ i < 2^m, x p i = true) := by    intro h    have := h a (by omega)    rw [hxa] at this    contradiction  obtain ⟨l, r, hl₀, hr₀, hlr, hFl, hFr⟩ := int_dense_marks_bracket    (2^m) (fun q => ∀ i < 2^m, x q i = true) hfullcover p hp  let y : ℤ → ℕ → Bool := fun q i => x ((p-(l : ℤ))+q) i  have hyroot : ∀ i, y (l : ℤ) i = x p i := by intro i; dsimp [y]; congr 1; omega  have hytight : ∀ q : ℤ, cycle_power_dyadic_class_weight m (y q) =      (range (2^m)).sum (fun i => (y q i).toNat) := by    intro q    exact htight ((p-(l : ℤ))+q)  have hyexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1 := by    intro j hj v    simpa only [y, add_sub_assoc] using hexact j hj ((p-(l : ℤ))+v)  have hycover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ,      ∃ a : ℕ, a < 2^m-d ∧ y (v-(a : ℤ)) a = true ∧ y (v-(a : ℤ)) (a+d) = true := by    intro d hd₀ hdD v    simpa only [y, add_sub_assoc] using hcover d hd₀ hdD ((p-(l : ℤ))+v)  have hyfull₀ : ∀ i < 2^m, y 0 i = true := by    intro i hi    simpa only [y, add_zero] using hFl i hi  have hyfullg : ∀ i < 2^m, y ((l+r : ℕ) : ℤ) i = true := by    intro i hi    have hroot : (p-(l : ℤ))+((l+r : ℕ) : ℤ) = p+(r : ℤ) := by omega    simpa only [y, hroot] using hFr i hi  have hD : 2^m = 2*2^(m-1) := by    have he : m = (m-1)+1 := by omega    conv_lhs => rw [he, pow_succ]    ring  have hlo := cycle_power_two_full_roots_half_separated (2^m) (2^(m-1)) hD y    (hyexact (m-1) (by omega)) (l+r) (by omega) hyfull₀ hyfullg  have hshape := cycle_power_dyadic_full_gap_class_no_island m hm y hytight hyexact hycover    (l+r) hlo hlr hyfull₀ hyfullg l hl₀ (by omega) a b c hab hbc hcD      (by simpa only [hyroot] using hxa) (by simpa only [hyroot] using hxb)  simpa only [hyroot] using hshape
See it in the graphDiscuss this resultChallenge it