AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_no_island_of_alternating_endpoint

theoremverified

Induction step without pairing. If every model at exponent m (m ≥ 2) has no island, then every tight, exactly dyadically covered, fully covered model at exponent m+1 with m+2 active classes per vertex, alternating bit 1 and endpoint-only classes without bit 1, has no island. Unlike cycle_power_dyadic_no_island_of_alternating_paired it does not assume the consecutive-bit pairing.

Statement

theorem cycle_power_dyadic_no_island_of_alternating_endpoint (m : ℕ) (hm : 2 ≤ m)
    (hshape : ∀ (y : ℤ → ℕ → Bool),
      (∀ p, cycle_power_dyadic_class_weight m (y p) =
        (Finset.range (2^m)).sum (fun a => (y p a).toNat)) →
      (∀ j < m, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>
        (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) →
      (∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ,
        ∃ a : ℕ, a < 2^m-d ∧ y (v-(a : ℤ)) a = true ∧
          y (v-(a : ℤ)) (a+d) = true) →
      (∀ v : ℤ, (Finset.range (2^m)).sum (fun a =>
        (y (v-(a : ℤ)) a).toNat) = m+1) →
      ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m →
        y p a = false → y p b = true → y p c = true)
    (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight (m+1) (x p) =
      (Finset.range (2^(m+1))).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < (m+1), ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(m+1)-2^j)).toNat) = 1)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(m+1) → ∀ v : ℤ,
      ∃ a : ℕ, a < 2^(m+1)-d ∧ x (v-(a : ℤ)) a = true ∧
        x (v-(a : ℤ)) (a+d) = true)
    (hcount : ∀ v : ℤ, (Finset.range (2^(m+1))).sum (fun a =>
      (x (v-(a : ℤ)) a).toNat) = (m+1)+1)
    (halt : ∀ p : ℤ, x (p+1) 1 = !x p 1)
    (hend : ∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^(m+1) - 1 → x p j = false) :
    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(m+1) →
      x p a = false → x p b = true → x p c = true
Source
Research thread RT-1, OP-205 (arXiv:2610.15635, Theorems 1.3-1.4: eq(C_n^k) for k+1 = 2^m, n even, (k+1) not dividing n). Session 2026-11-06: a no-island route that needs only alternation and endpoint-only classes, not the consecutive-bit pairing (the pairing of the middle offsets is non-local, exp 17235).
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The proof establishes the induction step for the absence of islands in alternating-endpoint models without assuming consecutive-bit pairing. Using cycle_power_dyadic_no_island_of_alternating_halves, the claim at exponent m+1 reduces to showing that each parity sub-model (even or odd coordinates) has no island. The helper cycle_power_dyadic_alternating_half_model verifies that every such sub-model satisfies all four defining properties of a model at exponent m, allowing the induction hypothesis to be applied directly at the base vertex to complete the step.

  1. It suffices to show that for any class p with x(p, 1) = true, parity e < 2, and indices a < b < c < 2^m, if x(p, 2a+e) = false and x(p, 2b+e) = true, then x(p, 2c+e) = true.

    By cycle_power_dyadic_no_island_of_alternating_halves, proving that x has no island at exponent m+1 reduces to checking that each parity half-model (even and odd classes) at any class with bit 1 set has no island. We introduce the class p, the parity e, the ordered indices a < b < c, and the hypotheses that x(p, 2a+e) is false and x(p, 2b+e) is true.

    lines 28–29

    uses cycle_power_dyadic_no_island_of_alternating_halves

      apply cycle_power_dyadic_no_island_of_alternating_halves m hm x htight hexact hcover hcount halt hend
      intro p hp1 e he a b c h1 h2 h3 h4 h5
  2. The sub-model y(q, k) := x(2q + p, 2k + e) satisfies tightness, exact dyadic coverage, full coverage, and vertex degree m+1 at exponent m.

    The lemma cycle_power_dyadic_alternating_half_model decomposes the assumptions on the full model x at exponent m+1 to show that the parity sub-model y satisfies all four model axioms at exponent m: class tightness (t), exact dyadic coverage (ex), full coverage (cv), and vertex degree m+1 (cn).

    lines 30–31

    uses cycle_power_dyadic_alternating_half_model

      obtain ⟨t, ex, cv, cn⟩ :=
        cycle_power_dyadic_alternating_half_model m hm x htight hexact hcover hcount halt hend p hp1 e he
  3. x(p, 2c+e) = true, showing that the sub-model has no island and concluding the proof.

    We instantiate the induction hypothesis (hshape) on the sub-model y with the four verified model properties (t, ex, cv, cn), vertex q = 0, and indices a, b, c. Because 2 * 0 + p = p, the sub-model at q = 0 corresponds to the original class p. The induction hypothesis then implies that x(p, 2a+e) = false and x(p, 2b+e) = true force x(p, 2c+e) = true, which matches our hypotheses and completes the proof.

    lines 32–35

      have hp0 : 2 * (0 : ℤ) + p = p := by ring
      have := hshape (fun q b => x (2 * q + p) (2 * b + e)) t ex cv cn 0 a b c h1 h2 h3
      simp only [hp0] at this
      exact this h4 h5
cycle_power_dyadic_no_island_of_alternating_halves
If a tight, dyadically covered, fully covered alternating-endpoint model at exponent m+1 has no islands in any of its parity sub-models x(p, 2b+e) for e < 2 whenever x(p, 1) = true, then the entire model at exponent m+1 has no islands.
cycle_power_dyadic_alternating_half_model
For a tight, dyadically covered, fully covered alternating-endpoint model x at exponent m+1, each parity sub-model y(q, b) = x(2q+s, 2b+e) with x(s, 1) = true and e < 2 satisfies tightness, exact dyadic coverage, full coverage, and vertex degree m+1 at exponent 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

theorem cycle_power_dyadic_no_island_of_alternating_endpoint (m : ℕ) (hm : 2 ≤ m)    (hshape : ∀ (y : ℤ → ℕ → Bool),      (∀ p, cycle_power_dyadic_class_weight m (y p) =        (Finset.range (2^m)).sum (fun a => (y p a).toNat)) →      (∀ j < m, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>        (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) →      (∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ,        ∃ a : ℕ, a < 2^m-d ∧ y (v-(a : ℤ)) a = true ∧          y (v-(a : ℤ)) (a+d) = true) →      (∀ v : ℤ, (Finset.range (2^m)).sum (fun a =>        (y (v-(a : ℤ)) a).toNat) = m+1) →      ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m →        y p a = false → y p b = true → y p c = true)    (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight (m+1) (x p) =      (Finset.range (2^(m+1))).sum (fun a => (x p a).toNat))    (hexact : ∀ j < (m+1), ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(m+1)-2^j)).toNat) = 1)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(m+1) → ∀ v : ℤ,      ∃ a : ℕ, a < 2^(m+1)-d ∧ x (v-(a : ℤ)) a = true ∧        x (v-(a : ℤ)) (a+d) = true)    (hcount : ∀ v : ℤ, (Finset.range (2^(m+1))).sum (fun a =>      (x (v-(a : ℤ)) a).toNat) = (m+1)+1)    (halt : ∀ p : ℤ, x (p+1) 1 = !x p 1)    (hend : ∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^(m+1) - 1 → x p j = false) :    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(m+1) →      x p a = false → x p b = true → x p c = true := by  apply cycle_power_dyadic_no_island_of_alternating_halves m hm x htight hexact hcover hcount halt hend  intro p hp1 e he a b c h1 h2 h3 h4 h5  obtain ⟨t, ex, cv, cn⟩ :=    cycle_power_dyadic_alternating_half_model m hm x htight hexact hcover hcount halt hend p hp1 e he  have hp0 : 2 * (0 : ℤ) + p = p := by ring  have := hshape (fun q b => x (2 * q + p) (2 * b + e)) t ex cv cn 0 a b c h1 h2 h3  simp only [hp0] at this  exact this h4 h5
See it in the graphDiscuss this resultChallenge it