AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_alternating_half_crossed_cover

theoremverified

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
Used by 1

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.

  1. 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.

    lines 13–20

    uses cycle_power_dyadic_alternating_bit_one_parity, pow_succ, Nat.pow_le_pow_right

      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
  2. 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).

    lines 21–24

    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⟩
  3. 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.

    lines 25–30

        · 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
  4. 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`.

    lines 31–36

    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
  5. 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).

    lines 37–39

    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⟩
  6. 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`.

    lines 40–48

    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
  7. 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.

    lines 49–54

        · 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.

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_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
See it in the graphDiscuss this resultChallenge it