cycle_power_dyadic_alternating_half_crossed_cover
Crossed 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, bit 1 alternates (x (p+1) 1 = !x p 1) and every class without bit 1 has no inner bit, fix a root s with bit 1. Then for every 1 ≤ j < m and every v there is a < 2^j such that the class rooted at 2(v-a)+s contains the even offset 2a and the odd offset 2(a+2^m-2^j)+1, and there is a < 2^j such that it contains the odd offset 2a+1 and the even offset 2(a+2^m-2^j). These are the covers of the odd distances 2^(m+1)-2^(j+1)±1; in half-model terms (y q b = x (2q+s) (2b), z q b = x (2q+s) (2b+1)) they are the mixed pairs y–z and z–y at the dyadic distance 2^m-2^j.
Statement
theorem cycle_power_dyadic_alternating_half_crossed_cover (m : ℕ) (x : ℤ → ℕ → Bool)
(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)
(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)
(s : ℤ) (hs : x s 1 = true) :
∀ j : ℕ, 1 ≤ j → j < m → ∀ v : ℤ,
(∃ a : ℕ, a < 2^j ∧ x (2*(v-(a : ℤ))+s) (2*a) = true ∧
x (2*(v-(a : ℤ))+s) (2*(a+2^m-2^j)+1) = true) ∧
(∃ a : ℕ, a < 2^j ∧ x (2*(v-(a : ℤ))+s) (2*a+1) = true ∧
x (2*(v-(a : ℤ))+s) (2*(a+2^m-2^j)) = true)- Source
- 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-08: the alignment lemma cycle_power_dyadic_no_island_of_alternating_halves reduced to the pairing of the two half models, which experiment 18632 finds forced already inside the span of one class.
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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_halvesAlignment conjecture. In a tight, exactly dyadically covered, fully covered integer Boolean class model at exponent m+1 (m ≥ 2) with m+2…
The proof, explained
The theorem proves that any class model satisfying the coverage hypothesis, bit 1 alternation, and the no-inner-bits condition has crossed dyadic coverage at level j: from 2(v-a)+s one can reach both an even-odd pair and an odd-even pair at dyadic distance 2^m-2^j. The proof queries the global coverage hypothesis at odd distances 2(2^m - 2^j) ± 1 from classes 2v+s and 2v+s+1, respectively. In each case, parity analysis shows that one parity forces the root to have bit 1 false, which contradicts the existence of true inner bits, while the other parity places the root at an alternating class where bit 1 is true, providing the desired witness a < 2^j.
Establish parity properties of bit 1 and bounds on powers of 2 for the chosen level j.
We fix j with 1 ≤ j < m and an integer v. Lemma `cycle_power_dyadic_alternating_bit_one_parity` applies the alternating hypothesis `halt` to show that bit 1 is true at all classes of the form 2q+s and false at classes 2q+s+1. Using `pow_succ` and `Nat.pow_le_pow_right`, we establish the power identities 2^(m+1) = 2 * 2^m and 2^(j+1) = 2 * 2^j, as well as the bounds 2 ≤ 2^j and 2^(j+1) ≤ 2^m.
uses
cycle_power_dyadic_alternating_bit_one_parity,pow_succ,Nat.pow_le_pow_rightintro j hj1 hjm v have hpar := cycle_power_dyadic_alternating_bit_one_parity x halt s hs have hpow : 2 ^ (m + 1) = 2 * 2 ^ m := by rw [pow_succ]; omega have hjpow : 2 ^ (j + 1) = 2 * 2 ^ j := by rw [pow_succ]; omega have hj2 : 2 ≤ 2 ^ j := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ j := Nat.pow_le_pow_right (by decide) hj1 have hjm2 : 2 ^ (j + 1) ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) hjm
For the first conjunct, obtain a covering offset a at distance 2(2^m-2^j)+1 from class 2v+s and split on its parity.
We split the goal into two conjuncts. For the first conjunct, we instantiate the coverage hypothesis `hcover` at distance d = 2(2^m-2^j)+1 starting from class 2v+s, giving an offset a < 2^(m+1)-d where both bit a and bit a+d are true. Using `Nat.even_or_odd'`, we divide into cases depending on whether a is even (a = 2a') or odd (a = 2a'+1).
uses
Nat.even_or_odd'constructor · -- the pair (2v+s, 2v+s + 2(2^m-2^j)+1) obtain ⟨a, ha, h1, h2⟩ := hcover (2 * (2 ^ m - 2 ^ j) + 1) (by omega) (by omega) (2 * v + s) rcases Nat.even_or_odd' a with ⟨a', rfl | rfl⟩
When a is even, a' is the desired witness for the even-odd pair.
When a = 2a', the bound a < 2^(m+1) - (2(2^m-2^j)+1) implies a' < 2^j. Rewriting the root class shows (2v+s) - 2a' = 2(v-a')+s. Thus, bit 2a' is true at root 2(v-a')+s, and bit 2a'+d = 2(a'+2^m-2^j)+1 is also true at that root, satisfying the first conjunct.
· refine ⟨a', by omega, ?_, ?_⟩ · have hr : 2 * v + s - ((2 * a' : ℕ) : ℤ) = 2 * (v - a') + s := by push_cast; ring rw [hr] at h1; exact h1 · have hr : 2 * v + s - ((2 * a' : ℕ) : ℤ) = 2 * (v - a') + s := by push_cast; ring rw [hr, show 2 * a' + (2 * (2 ^ m - 2 ^ j) + 1) = 2 * (a' + 2 ^ m - 2 ^ j) + 1 by omega] at h2 exact h2
The case where a is odd is ruled out by the absence of inner bits.
If a = 2a'+1, the class (2v+s) - (2a'+1) simplifies to 2(v-a'-1)+s+1. By the parity lemma, this class has bit 1 set to false. By hypothesis `hend`, all interior bits of such a class must be false. Since 0 < 2a'+1 < 2^(m+1)-1, bit 2a'+1 is an interior bit and must be false. But the coverage hypothesis asserts it is true, yielding a contradiction via `Bool.false_ne_true`.
uses
Bool.false_ne_true· exfalso have hr : 2 * v + s - ((2 * a' + 1 : ℕ) : ℤ) = 2 * (v - a' - 1) + s + 1 := by push_cast; ring rw [hr] at h1 rw [hend _ (hpar _).2 (2 * a' + 1) (by omega) (by omega)] at h1 exact Bool.false_ne_true h1
For the second conjunct, obtain a covering offset a at distance 2(2^m-2^j)-1 from class 2v+s+1 and split on its parity.
For the second conjunct, we query `hcover` at distance d = 2(2^m-2^j)-1 from class 2v+s+1. This yields an offset a < 2^(m+1)-d such that bit a and bit a+d are true. Using `Nat.even_or_odd'`, we split into cases where a is even (a = 2a') or odd (a = 2a'+1).
uses
Nat.even_or_odd'· -- the pair (2v+s+1, 2v+s+1 + 2(2^m-2^j)-1) obtain ⟨a, ha, h1, h2⟩ := hcover (2 * (2 ^ m - 2 ^ j) - 1) (by omega) (by omega) (2 * v + s + 1) rcases Nat.even_or_odd' a with ⟨a', rfl | rfl⟩
The case where a is even is ruled out by the absence of inner bits.
When a = 2a', the class (2v+s+1) - 2a' = 2(v-a')+s+1 has bit 1 false, so by `hend` all its interior bits must be false. We split on whether a' = 0 or a' > 0 using `Nat.eq_zero_or_pos`. If a' = 0, the second offset a+d = 2(2^m-2^j)-1 is an interior bit and is true, contradicting `hend`. If a' > 0, the first offset 2a' is an interior bit and is true, again contradicting `hend`. Both cases conclude by `Bool.false_ne_true`.
uses
Nat.eq_zero_or_pos,Bool.false_ne_true· exfalso have hr : 2 * v + s + 1 - ((2 * a' : ℕ) : ℤ) = 2 * (v - a') + s + 1 := by push_cast; ring rw [hr] at h1 h2 rcases Nat.eq_zero_or_pos a' with h0 | h0 · subst h0 rw [hend _ (hpar _).2 (2 * 0 + (2 * (2 ^ m - 2 ^ j) - 1)) (by omega) (by omega)] at h2 exact Bool.false_ne_true h2 · rw [hend _ (hpar _).2 (2 * a') (by omega) (by omega)] at h1 exact Bool.false_ne_true h1
When a is odd, a' is the desired witness for the odd-even pair.
When a = 2a'+1, the bound a < 2^(m+1) - (2(2^m-2^j)-1) implies a' < 2^j. Rewriting the root class yields (2v+s+1) - (2a'+1) = 2(v-a')+s. Then bit 2a'+1 is true at root 2(v-a')+s, and bit (2a'+1) + (2(2^m-2^j)-1) = 2(a'+2^m-2^j) is also true at that root, completing the proof of the second conjunct.
· refine ⟨a', by omega, ?_, ?_⟩ · have hr : 2 * v + s + 1 - ((2 * a' + 1 : ℕ) : ℤ) = 2 * (v - a') + s := by push_cast; ring rw [hr] at h1; exact h1 · have hr : 2 * v + s + 1 - ((2 * a' + 1 : ℕ) : ℤ) = 2 * (v - a') + s := by push_cast; ring rw [hr, show 2 * a' + 1 + (2 * (2 ^ m - 2 ^ j) - 1) = 2 * (a' + 2 ^ m - 2 ^ j) by omega] at h2 exact h2
cycle_power_dyadic_alternating_bit_one_parity- If bit 1 alternates between adjacent classes and class s has bit 1 set to true, then any class 2q+s has bit 1 true, and any class 2q+s+1 has bit 1 false.
pow_succ- In any monoid, a^(n+1) = a^n * a.
Nat.pow_le_pow_right- For a base n > 0, the exponential map i ↦ n^i is monotonically increasing: i ≤ j implies n^i ≤ n^j.
Nat.even_or_odd'- Every natural number n can be written either as 2k (even) or 2k+1 (odd) for some natural number k.
Nat.eq_zero_or_pos- Every natural number is either equal to 0 or strictly positive.
Bool.false_ne_true- The boolean false is distinct from true.
- Arithmetic bounds on powers of two and polynomial ring identities on integer indices are discharged by `omega` and `ring` throughout the proof.
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_alternating_half_crossed_cover (m : ℕ) (x : ℤ → ℕ → Bool) (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) (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) (s : ℤ) (hs : x s 1 = true) : ∀ j : ℕ, 1 ≤ j → j < m → ∀ v : ℤ, (∃ a : ℕ, a < 2^j ∧ x (2*(v-(a : ℤ))+s) (2*a) = true ∧ x (2*(v-(a : ℤ))+s) (2*(a+2^m-2^j)+1) = true) ∧ (∃ a : ℕ, a < 2^j ∧ x (2*(v-(a : ℤ))+s) (2*a+1) = true ∧ x (2*(v-(a : ℤ))+s) (2*(a+2^m-2^j)) = true) := by intro j hj1 hjm v have hpar := cycle_power_dyadic_alternating_bit_one_parity x halt s hs have hpow : 2 ^ (m + 1) = 2 * 2 ^ m := by rw [pow_succ]; omega have hjpow : 2 ^ (j + 1) = 2 * 2 ^ j := by rw [pow_succ]; omega have hj2 : 2 ≤ 2 ^ j := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ j := Nat.pow_le_pow_right (by decide) hj1 have hjm2 : 2 ^ (j + 1) ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) hjm constructor · -- the pair (2v+s, 2v+s + 2(2^m-2^j)+1) obtain ⟨a, ha, h1, h2⟩ := hcover (2 * (2 ^ m - 2 ^ j) + 1) (by omega) (by omega) (2 * v + s) rcases Nat.even_or_odd' a with ⟨a', rfl | rfl⟩ · refine ⟨a', by omega, ?_, ?_⟩ · have hr : 2 * v + s - ((2 * a' : ℕ) : ℤ) = 2 * (v - a') + s := by push_cast; ring rw [hr] at h1; exact h1 · have hr : 2 * v + s - ((2 * a' : ℕ) : ℤ) = 2 * (v - a') + s := by push_cast; ring rw [hr, show 2 * a' + (2 * (2 ^ m - 2 ^ j) + 1) = 2 * (a' + 2 ^ m - 2 ^ j) + 1 by omega] at h2 exact h2 · exfalso have hr : 2 * v + s - ((2 * a' + 1 : ℕ) : ℤ) = 2 * (v - a' - 1) + s + 1 := by push_cast; ring rw [hr] at h1 rw [hend _ (hpar _).2 (2 * a' + 1) (by omega) (by omega)] at h1 exact Bool.false_ne_true h1 · -- the pair (2v+s+1, 2v+s+1 + 2(2^m-2^j)-1) obtain ⟨a, ha, h1, h2⟩ := hcover (2 * (2 ^ m - 2 ^ j) - 1) (by omega) (by omega) (2 * v + s + 1) rcases Nat.even_or_odd' a with ⟨a', rfl | rfl⟩ · exfalso have hr : 2 * v + s + 1 - ((2 * a' : ℕ) : ℤ) = 2 * (v - a') + s + 1 := by push_cast; ring rw [hr] at h1 h2 rcases Nat.eq_zero_or_pos a' with h0 | h0 · subst h0 rw [hend _ (hpar _).2 (2 * 0 + (2 * (2 ^ m - 2 ^ j) - 1)) (by omega) (by omega)] at h2 exact Bool.false_ne_true h2 · rw [hend _ (hpar _).2 (2 * a') (by omega) (by omega)] at h1 exact Bool.false_ne_true h1 · refine ⟨a', by omega, ?_, ?_⟩ · have hr : 2 * v + s + 1 - ((2 * a' + 1 : ℕ) : ℤ) = 2 * (v - a') + s := by push_cast; ring rw [hr] at h1; exact h1 · have hr : 2 * v + s + 1 - ((2 * a' + 1 : ℕ) : ℤ) = 2 * (v - a') + s := by push_cast; ring rw [hr, show 2 * a' + 1 + (2 * (2 ^ m - 2 ^ j) - 1) = 2 * (a' + 2 ^ m - 2 ^ j) by omega] at h2 exact h2