AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_no_island_of_alternating_halves

theoremverified

Alignment conjecture. In a tight, exactly dyadically covered, fully covered integer Boolean class model at exponent m+1 (m ≥ 2) with m+2 active classes per vertex, alternating bit 1 and endpoint-only classes without bit 1, if for every class with bit 1 both its even-offset half and its odd-offset half have no island, then no class has an island (a < b < c with bit a missing, bit b selected, bit c missing).

Statement

theorem cycle_power_dyadic_no_island_of_alternating_halves (m : ℕ) (hm : 2 ≤ m) (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)
    (hhalf : ∀ p : ℤ, x p 1 = true → ∀ e < 2, ∀ a b c : ℕ, a < b → b < c → c < 2^m →
      x p (2*a+e) = false → x p (2*b+e) = true → x p (2*c+e) = true) :
    ∀ (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). Experiments 17276 and 17282: with H, endpoint-only and no-island halves assumed at every root, an island in the class rooted at 0 is impossible already with guard 0 beyond its span at exponents 3 and 4, guard 2 at 5, guard 4 at 6 and 7; the only candidates at smaller guards are the offsets D/4, D/4+1, 3D/4-2, 3D/4-1.
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

The proof, explained

The proof first eliminates the case where class p has bit 1 false, because such endpoint-only classes contain no interior active bits, contradicting the assumption that bit b is true. For a class with bit 1 true, the parity hypothesis ensures that bit 1 remains true for all classes 2*q + p, allowing both the even-offset and odd-offset bits to form valid dyadic sub-models at exponent m. Since both half-models have no islands and are cross-covered, the uniqueness theorem for crossed models proves that they are identical, which means adjacent bits in class p are paired (x p (2*i) = x p (2*i+1)). Dividing indices by 2 collapses the problem to the even half-model, where the no-island hypothesis on that half forces x p c to be true.

  1. Introduce the class index p and bit indices a < b < c < 2^(m+1) satisfying the premise, and factor 2^(m+1) = 2 * 2^m.

    We introduce the arbitrary class p and bit positions a < b < c < 2^(m+1) with x p a = false and x p b = true, and rewrite 2^(m+1) as 2 * 2^m using pow_succ.

    lines 17–18

    uses pow_succ

      intro p a b c hab hbc hc ha hb
      have hD : 2 ^ (m + 1) = 2 * 2 ^ m := by rw [pow_succ]; ring
  2. The class p must have bit 1 selected: x p 1 = true.

    We split into cases on whether x p 1 is true or false. If x p 1 = false, hypothesis hend states that all intermediate bits strictly between 0 and 2^(m+1)-1 must be false. Since 0 ≤ a < b < c < 2^(m+1), index b is strictly interior (0 < b < 2^(m+1)-1), forcing x p b = false, which contradicts the hypothesis x p b = true.

    lines 19–21

      cases hp1 : x p 1
      · have := hend p hp1 b (by omega) (by omega)
        rw [this] at hb; exact absurd hb (by decide)
  3. The even-offset and odd-offset classes at p induce tight, dyadically exact models at exponent m that satisfy a crossed-cover condition.

    By cycle_power_dyadic_alternating_bit_one_parity, alternating bit 1 implies that all classes of the form 2*q + p have bit 1 true. Invoking cycle_power_dyadic_alternating_half_model for offsets e = 0 and e = 1 proves that the even-offset and odd-offset sub-models are tight and dyadically exact at exponent m. Furthermore, cycle_power_dyadic_alternating_half_crossed_cover establishes that these two sub-models are cross-covered at every scale.

    lines 22–29

    uses cycle_power_dyadic_alternating_bit_one_parity, cycle_power_dyadic_alternating_half_model, cycle_power_dyadic_alternating_half_crossed_cover

      · have hpar := cycle_power_dyadic_alternating_bit_one_parity x halt p hp1
        obtain ⟨ytight, yexact, -, -⟩ :=
          cycle_power_dyadic_alternating_half_model m hm x htight hexact hcover hcount halt hend p hp1 0
            (by norm_num)
        obtain ⟨ztight, zexact, -, -⟩ :=
          cycle_power_dyadic_alternating_half_model m hm x htight hexact hcover hcount halt hend p hp1 1
            (by norm_num)
        have hcr := cycle_power_dyadic_alternating_half_crossed_cover m x hcover halt hend p hp1
  4. In class p, adjacent bits have identical values: x p (2*i) = x p (2*i+1) for all i < 2^m.

    Because both the even and odd sub-models satisfy the no-island assumption (hhalf), theorem cycle_power_dyadic_crossed_no_island_models_eq implies that the two models are identical everywhere. Specializing this equality to q = 0 yields x p (2*i) = x p (2*i+1) for all i < 2^m.

    lines 30–41

    uses cycle_power_dyadic_crossed_no_island_models_eq, Nat.add_zero

        have heq := cycle_power_dyadic_crossed_no_island_models_eq m (by omega)
          (fun q i => x (2 * q + p) (2 * i + 0)) (fun q i => x (2 * q + p) (2 * i + 1))
          ytight ztight yexact zexact
          (fun q a b c h1 h2 h3 h4 h5 => hhalf (2 * q + p) (hpar q).1 0 (by norm_num) a b c h1 h2 h3 h4 h5)
          (fun q a b c h1 h2 h3 h4 h5 => hhalf (2 * q + p) (hpar q).1 1 (by norm_num) a b c h1 h2 h3 h4 h5)
          hcr
        have hp0 : 2 * (0 : ℤ) + p = p := by ring
        have hpair : ∀ i < 2 ^ m, x p (2 * i) = x p (2 * i + 1) := by
          intro i hi
          have := heq 0 i hi
          simp only [hp0, Nat.add_zero] at this
          exact this
  5. Every bit value x p j equals the even bit x p (2 * (j / 2)), reducing the problem to the even-offset sub-model.

    By case analysis on the parity of j (Nat.even_or_odd), if j is even then j = 2 * (j / 2), and if j is odd then x p j = x p (2 * (j / 2) + 1) = x p (2 * (j / 2)) by adjacent-bit pairing. Rewriting with this identity transforms the assumptions to x p (2 * (a / 2)) = false and x p (2 * (b / 2)) = true, and the goal to x p (2 * (c / 2)) = true.

    lines 42–49

    uses Nat.even_or_odd, Nat.add_zero

        have hxe : ∀ j < 2 ^ (m + 1), x p j = x p (2 * (j / 2) + 0) := by
          intro j hj
          rcases Nat.even_or_odd j with ⟨t, ht⟩ | ⟨t, ht⟩
          · rw [show j / 2 = t by omega, show 2 * t + 0 = j by omega]
          · rw [show j / 2 = t by omega, Nat.add_zero, hpair t (by omega), show 2 * t + 1 = j by omega]
        rw [hxe a (by omega)] at ha
        rw [hxe b (by omega)] at hb
        rw [hxe c hc]
  6. The halved indices strictly increase: a / 2 < b / 2.

    Since a < b, integer division gives a / 2 ≤ b / 2. If a / 2 = b / 2, then 2 * (a / 2) = 2 * (b / 2), which would make x p (2 * (a / 2)) both false and true, a contradiction.

    lines 50–53

    uses Nat.lt_or_ge

        have hab2 : a / 2 < b / 2 := by
          rcases Nat.lt_or_ge (a / 2) (b / 2) with h' | h'
          · exact h'
          · rw [show a / 2 = b / 2 by omega, hb] at ha; exact absurd ha (by decide)
  7. Bit c is selected: x p c = true.

    We split into cases on whether b / 2 < c / 2 or b / 2 ≥ c / 2 using Nat.lt_or_ge. If b / 2 < c / 2, then a / 2 < b / 2 < c / 2 < 2^m, so the no-island hypothesis hhalf for offset e = 0 directly proves x p (2 * (c / 2)) = true. If b / 2 ≥ c / 2, then since b < c, the quotients must be equal (c / 2 = b / 2), so x p (2 * (c / 2)) = x p (2 * (b / 2)) = true.

    lines 54–56

    uses Nat.lt_or_ge

        rcases Nat.lt_or_ge (b / 2) (c / 2) with h' | h'
        · exact hhalf p hp1 0 (by norm_num) (a / 2) (b / 2) (c / 2) hab2 h' (by omega) ha hb
        · rw [show c / 2 = b / 2 by omega]; exact hb
pow_succ
In a monoid (such as ℕ under multiplication), a^(n+1) = a^n * a.
cycle_power_dyadic_alternating_bit_one_parity
In a Boolean model where bit 1 alternates at each step, if class s has bit 1 set to true, then every class 2*q + s has bit 1 set to true and every class 2*q + s + 1 has bit 1 set to false.
cycle_power_dyadic_alternating_half_model
Under the dyadic model assumptions at exponent m+1, extracting the bits at even offset (or odd offset) across alternating classes produces a valid tight, dyadically exact, and fully covered model at exponent m.
cycle_power_dyadic_alternating_half_crossed_cover
Under the dyadic model assumptions with alternating bit 1, the even-offset and odd-offset half-models satisfy a crossed dyadic covering condition at all dyadic scales 1 ≤ j < m.
cycle_power_dyadic_crossed_no_island_models_eq
If two tight, dyadically exact Boolean class models at exponent m both satisfy the no-island condition and are cross-covered by each other, then they are identical.
Nat.add_zero
For any natural number n, n + 0 = n.
Nat.even_or_odd
Every natural number is either even or odd.
Nat.lt_or_ge
For any natural numbers n and m, either n < m or 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

theorem cycle_power_dyadic_no_island_of_alternating_halves (m : ℕ) (hm : 2 ≤ m) (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)    (hhalf : ∀ p : ℤ, x p 1 = true → ∀ e < 2, ∀ a b c : ℕ, a < b → b < c → c < 2^m →      x p (2*a+e) = false → x p (2*b+e) = true → x p (2*c+e) = true) :    ∀ (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  intro p a b c hab hbc hc ha hb  have hD : 2 ^ (m + 1) = 2 * 2 ^ m := by rw [pow_succ]; ring  cases hp1 : x p 1  · have := hend p hp1 b (by omega) (by omega)    rw [this] at hb; exact absurd hb (by decide)  · have hpar := cycle_power_dyadic_alternating_bit_one_parity x halt p hp1    obtain ⟨ytight, yexact, -, -⟩ :=      cycle_power_dyadic_alternating_half_model m hm x htight hexact hcover hcount halt hend p hp1 0        (by norm_num)    obtain ⟨ztight, zexact, -, -⟩ :=      cycle_power_dyadic_alternating_half_model m hm x htight hexact hcover hcount halt hend p hp1 1        (by norm_num)    have hcr := cycle_power_dyadic_alternating_half_crossed_cover m x hcover halt hend p hp1    have heq := cycle_power_dyadic_crossed_no_island_models_eq m (by omega)      (fun q i => x (2 * q + p) (2 * i + 0)) (fun q i => x (2 * q + p) (2 * i + 1))      ytight ztight yexact zexact      (fun q a b c h1 h2 h3 h4 h5 => hhalf (2 * q + p) (hpar q).1 0 (by norm_num) a b c h1 h2 h3 h4 h5)      (fun q a b c h1 h2 h3 h4 h5 => hhalf (2 * q + p) (hpar q).1 1 (by norm_num) a b c h1 h2 h3 h4 h5)      hcr    have hp0 : 2 * (0 : ℤ) + p = p := by ring    have hpair : ∀ i < 2 ^ m, x p (2 * i) = x p (2 * i + 1) := by      intro i hi      have := heq 0 i hi      simp only [hp0, Nat.add_zero] at this      exact this    have hxe : ∀ j < 2 ^ (m + 1), x p j = x p (2 * (j / 2) + 0) := by      intro j hj      rcases Nat.even_or_odd j with ⟨t, ht⟩ | ⟨t, ht⟩      · rw [show j / 2 = t by omega, show 2 * t + 0 = j by omega]      · rw [show j / 2 = t by omega, Nat.add_zero, hpair t (by omega), show 2 * t + 1 = j by omega]    rw [hxe a (by omega)] at ha    rw [hxe b (by omega)] at hb    rw [hxe c hc]    have hab2 : a / 2 < b / 2 := by      rcases Nat.lt_or_ge (a / 2) (b / 2) with h' | h'      · exact h'      · rw [show a / 2 = b / 2 by omega, hb] at ha; exact absurd ha (by decide)    rcases Nat.lt_or_ge (b / 2) (c / 2) with h' | h'    · exact hhalf p hp1 0 (by norm_num) (a / 2) (b / 2) (c / 2) hab2 h' (by omega) ha hb    · rw [show c / 2 = b / 2 by omega]; exact hb
See it in the graphDiscuss this resultChallenge it