cycle_power_dyadic_no_island_of_alternating_halves
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
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- cycle_power_dyadic_alternating_half_crossed_coverCrossed coverage of the half models. In an integer Boolean class model at exponent m+1 in which every distance 1 ≤ d < 2^(m+1) is covered,…
- cycle_power_dyadic_crossed_no_island_models_eqPairing conjecture for coupled no-island models. Let m ≥ 1 and let y, z : ℤ → ℕ → Bool be two integer Boolean class models at exponent m,…
- cycle_power_dyadic_alternating_half_modelHalf models. In a tight, exactly dyadically covered, fully covered integer Boolean class model at exponent m+1 (m ≥ 2) with m+2 active…
- Used by 1
- cycle_power_dyadic_no_island_of_alternating_endpointInduction step without pairing. If every model at exponent m (m ≥ 2) has no island, then every tight, exactly dyadically covered, fully…
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.
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.
uses
pow_succintro p a b c hab hbc hc ha hb have hD : 2 ^ (m + 1) = 2 * 2 ^ m := by rw [pow_succ]; ring
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.
cases hp1 : x p 1 · have := hend p hp1 b (by omega) (by omega) rw [this] at hb; exact absurd hb (by decide)
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.
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
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.
uses
cycle_power_dyadic_crossed_no_island_models_eq,Nat.add_zerohave 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
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.
uses
Nat.even_or_odd,Nat.add_zerohave 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]
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.
uses
Nat.lt_or_gehave 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)
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.
uses
Nat.lt_or_gercases 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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