AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_no_island_of_alternating_paired

theoremverified

Uniform induction step for the no-island class shape. Let m ≥ 1 and suppose every tight, exactly dyadically covered, fully ordinarily covered integer Boolean class model at exponent m with exactly m+1 active classes at each vertex has no island (a < b < c < 2^m, bit a missing and bit b selected force bit c selected). Let x be such a model at exponent m+1 (m+2 active classes per vertex) with the alternating-paired structure: x (p+1) 1 = !(x p 1) for all p; a class with bit 1 missing has no inner bit (0 < j < 2^(m+1) - 1); a class with bit 1 selected has x p (2j) = x p (2j+1) for all j < 2^m. Then x has no island either.

Statement

theorem cycle_power_dyadic_no_island_of_alternating_paired (m : ℕ) (hm : 1 ≤ 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)
    (hpair : ∀ p : ℤ, x p 1 = true → ∀ j < 2^m, x p (2*j) = x p (2*j+1)) :
    ∀ (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). Experiment 10383: the alternating-paired structure is forced at the centre of the window [-2D, 2D] of the layer-free model for m = 3, 4, 5 (D = 2^m), not at radius 1.5 D.
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1

The proof, explained

The theorem proves by induction on exponent m that an alternating-paired model x at exponent m+1 has no island, assuming that all tight, dyadically exact, fully covered models at exponent m have no islands. A global parity shift aligns x so that even classes have only boundary bits active, while odd classes have paired bits. Compressing the odd classes by halving yields a model y at exponent m that inherits tightness, exact dyadic coverage, full distance coverage, and the active vertex count m+1 via structural compression lemmas. The induction hypothesis guarantees y has no island, which pulls back to show x is island-free.

  1. Define h = 2^m and note 2^(m+1) = 2*h with h > 0.

    We abbreviate 2^m as h. Since m ≥ 1, h is strictly positive by `Nat.two_pow_pos`, and 2^(m+1) = 2 * 2^m = 2 * h by `pow_succ`.

    lines 29–31

    uses Nat.two_pow_pos, pow_succ

      set h := 2 ^ m with hh
      have hpos : 0 < h := Nat.two_pow_pos m
      have hD : 2 ^ (m+1) = 2 * h := by rw [pow_succ]; ring
  2. Every class x(v) has both boundary bits set: x(v, 0) = true and x(v, 2*h - 1) = true.

    Specializing the dyadic exact coverage hypothesis `hexact` to j = 0 at vertex v yields a single-term sum stating (x(v, 0) && x(v, 2*h - 1)).toNat = 1. A Boolean conjunction evaluates to 1 if and only if both bits are true, which is confirmed by exhaustively checking all four Boolean cases.

    lines 32–38

    uses pow_zero, range_one, sum_singleton, Nat.cast_zero, sub_zero, zero_add

      have hends : ∀ v : ℤ, x v 0 = true ∧ x v (2 * h - 1) = true := by
        intro v
        have e := hexact 0 (by omega) v
        rw [hD] at e
        simp only [pow_zero, range_one, sum_singleton, Nat.cast_zero, sub_zero, zero_add] at e
        revert e
        cases x v 0 <;> cases x v (2 * h - 1) <;> decide
  3. Bit 1 is 2-periodic across classes, and there exists an offset s ∈ {0, 1} such that x(2*q + s, 1) = false and x(2*q + 1 + s, 1) = true for all q ∈ ℤ.

    Because bit 1 alternates at each class step (x(p+1, 1) = !x(p, 1)), applying alternation twice gives x(p+2, 1) = x(p, 1) by `Bool.not_not`. By integer induction via `Int.induction_on`, all even classes share the value x(0, 1). Choosing s = 0 if x(0, 1) = false and s = 1 if x(0, 1) = true aligns the model so that classes 2*q + s have bit 1 false, while classes 2*q + 1 + s have bit 1 true.

    lines 39–56

    uses Bool.not_not, Int.induction_on, add_zero

      -- parity of the endpoint-only classes
      have h2 : ∀ p : ℤ, x (p + 2) 1 = x p 1 := by
        intro p
        rw [show p + 2 = (p + 1) + 1 by ring, halt (p+1), halt p, Bool.not_not]
      have hev : ∀ q : ℤ, x (2 * q) 1 = x 0 1 := by
        intro q
        induction q using Int.induction_on with
        | zero => simp
        | succ i ih => rw [show 2 * ((i:ℤ) + 1) = 2 * i + 2 by ring, h2, ih]
        | pred i ih =>
          rw [← ih, show 2 * (-(i:ℤ)) = 2 * (-(i:ℤ) - 1) + 2 by ring, h2]
      obtain ⟨s, hs⟩ : ∃ s : ℤ, ∀ q : ℤ, x (2 * q + s) 1 = false := by
        cases h0 : x 0 1
        · exact ⟨0, fun q => by rw [add_zero, hev, h0]⟩
        · exact ⟨1, fun q => by rw [halt, hev, h0]; rfl⟩
      have hs1 : ∀ q : ℤ, x (2 * q + 1 + s) 1 = true := by
        intro q
        rw [show 2 * q + 1 + s = (2 * q + s) + 1 by ring, halt, hs]; rfl
  4. In the shifted model x'(q, j) = x(q+s, j), even classes activate only the endpoints 0 and 2*h - 1, odd classes have paired bits, and full distance coverage is preserved.

    For an even class 2*p, bit 1 is false by construction, so the endpoint-only assumption `hend` forces all inner bits 0 < j < 2*h - 1 to be false; combined with the boundary bits, x'(2*p, j) is true precisely when j is 0 or 2*h - 1. For an odd class 2*q + 1, bit 1 is true, so consecutive bits are paired (x'(2*q+1, 2*j) = x'(2*q+1, 2*j+1)) by `hpair`. Shifting the vertex argument by s transfers the full distance coverage `hcover` directly to x'.

    lines 57–80

      -- the shifted model
      set x' : ℤ → ℕ → Bool := fun q j => x (q + s) j with hx'
      have hsh : ∀ v a : ℤ, v - a + s = v + s - a := fun v a => by ring
      have heven : ∀ p : ℤ, ∀ j < 2 * h, x' (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1 := by
        intro p j hj
        simp only [hx']
        constructor
        · intro hx
          by_contra hne
          push Not at hne
          have := hend (2 * p + s) (hs p) j (by omega) (by rw [hD]; omega)
          rw [this] at hx; exact absurd hx (by decide)
        · rintro (rfl | rfl)
          · exact (hends _).1
          · exact (hends _).2
      have hpair' : ∀ q : ℤ, ∀ j < h, x' (2 * q + 1) (2 * j) = x' (2 * q + 1) (2 * j + 1) :=
        fun q j hj => hpair _ (hs1 q) j hj
      have hcover' : ∀ d, 1 ≤ d → d < 2 * h → ∀ u : ℤ,
          ∃ a < 2 * h - d, x' (u - (a : ℤ)) a = true ∧ x' (u - (a : ℤ)) (a + d) = true := by
        intro d hd1 hd u
        obtain ⟨a, ha, h1, h2⟩ := hcover d hd1 (by rw [hD]; exact hd) (u + s)
        refine ⟨a, by rw [hD] at ha; exact ha, ?_, ?_⟩
        · simp only [hx', hsh]; exact h1
        · simp only [hx', hsh]; exact h2
  5. The odd classes of x' are dilations of the compressed model y(q, i) = x'(2*q + 1, 2*i), satisfying x'(2*q + 1, j) = y(q, ⌊j/2⌋) for all j < 2*h.

    Using `Nat.even_or_odd`, any index j < 2*h is either 2*t or 2*t + 1. If j is even, x'(2*q+1, 2*t) = y(q, t) by definition. If j is odd, the pairing property of odd classes equates x'(2*q+1, 2*t+1) with x'(2*q+1, 2*t) = y(q, t).

    lines 81–88

    uses Nat.even_or_odd

      set y : ℤ → ℕ → Bool := fun q i => x' (2 * q + 1) (2 * i) with hy
      -- the class of x' at 2q+1 is the dilation of y q
      have hdil : ∀ q : ℤ, ∀ j < 2 * h, x' (2 * q + 1) j = y q (j / 2) := by
        intro q j hj
        simp only [hy]
        rcases Nat.even_or_odd j with ⟨t, ht⟩ | ⟨t, ht⟩
        · rw [show j / 2 = t by omega, show 2 * t = j by omega]
        · rw [show j / 2 = t by omega, hpair' q t (by omega), show 2 * t + 1 = j by omega]
  6. Every class of the compressed model y is tight at exponent m.

    By hypothesis `htight`, the class x'(2*q+1) is tight at exponent m+1. Since x'(2*q+1) is the dilation of y(q), lemma `cycle_power_dyadic_class_weight_dilate` proves that its dyadic weight is 2 * weight(y(q)). Similarly, pairing consecutive bits using `cycle_power_sum_range_double` and `mul_sum` shows that the bit sum of x'(2*q+1) is 2 * sum(y(q)). Dividing by 2 yields tightness for y(q).

    lines 89–110

    uses cycle_power_dyadic_class_weight_congr, cycle_power_dyadic_class_weight_dilate, cycle_power_sum_range_double, mul_sum, sum_congr

      have ytight : ∀ q, cycle_power_dyadic_class_weight m (y q) =
          (range (2 ^ m)).sum (fun a => (y q a).toNat) := by
        intro q
        change cycle_power_dyadic_class_weight m (y q) = (range h).sum (fun a => (y q a).toNat)
        have ht := htight (2 * q + 1 + s)
        have hw : cycle_power_dyadic_class_weight (m+1) (x (2 * q + 1 + s)) =
            cycle_power_dyadic_class_weight (m+1) (fun j => y q (j / 2)) := by
          apply cycle_power_dyadic_class_weight_congr
          intro i hi
          rw [hD] at hi
          exact hdil q i hi
        rw [hw, cycle_power_dyadic_class_weight_dilate m hm, hD, cycle_power_sum_range_double] at ht
        have hs2 : (range h).sum (fun i => (x (2 * q + 1 + s) (2 * i)).toNat +
            (x (2 * q + 1 + s) (2 * i + 1)).toNat) = 2 * (range h).sum (fun a => (y q a).toNat) := by
          rw [mul_sum]
          apply sum_congr rfl
          intro i hi
          have e := hpair' q i (mem_range.mp hi)
          simp only [hx', hy] at e ⊢
          rw [← e]; ring
        rw [hs2] at ht
        omega
  7. At every vertex v, the compressed model y has exactly m+1 active classes.

    Lemma `cycle_power_alternating_paired_compression_count` equates the vertex sum in x' at vertex 2*v+1 to 1 plus the vertex sum in y at vertex v, because even classes only contribute their endpoint to the vertex sum. Since the vertex sum in x' is (m+1)+1 = m+2 by `hcount`, subtracting 1 yields that the vertex sum in y is m+1.

    lines 111–119

    uses cycle_power_alternating_paired_compression_count

      have ycount : ∀ v : ℤ, (range (2 ^ m)).sum (fun a => (y (v - (a : ℤ)) a).toNat) = m + 1 := by
        intro v
        have e := cycle_power_alternating_paired_compression_count h hpos x' heven v
        have c := hcount (2 * v + 1 + s)
        rw [hD] at c
        have c' : (range (2 * h)).sum (fun j => (x' (2 * v + 1 - (j : ℤ)) j).toNat) = m + 1 + 1 := by
          simp only [hx', hsh]; exact c
        have : (range h).sum (fun j => (x' (2 * (v - (j : ℤ)) + 1) (2 * j)).toNat) = m + 1 := by omega
        exact this
  8. The compressed model y covers every distance 1 ≤ d < 2^m at every vertex v.

    Lemma `cycle_power_alternating_paired_compression_cover` directly transfers distance coverage from x' to y: any distance 2*d < 2*h covered in x' must be covered by an odd class (as even classes have only endpoints separated by 2*h - 1), which projects to a covering witness for distance d in y.

    lines 120–122

    uses cycle_power_alternating_paired_compression_cover

      have ycover : ∀ d : ℕ, 1 ≤ d → d < 2 ^ m → ∀ v : ℤ,
          ∃ a : ℕ, a < 2 ^ m - d ∧ y (v - (a : ℤ)) a = true ∧ y (v - (a : ℤ)) (a + d) = true :=
        fun d hd1 hd v => cycle_power_alternating_paired_compression_cover h x' heven hcover' d hd1 hd v
  9. The compressed model y satisfies exact dyadic coverage at exponent m.

    For any j < m and vertex v, lemma `cycle_power_alternating_paired_compression_exact_sum` equates the dyadic sum for y at scale 2^j and step 2^m - 2^j to the dyadic sum for x' at scale 2^(j+1) and step 2*(2^m - 2^j) = 2^(m+1) - 2^(j+1). The exact dyadic coverage hypothesis `hexact` of x at scale j+1 ensures that this sum equals 1.

    lines 123–144

    uses Nat.pow_lt_pow_right, pow_succ, cycle_power_alternating_paired_compression_exact_sum, sum_congr

      have yexact : ∀ j < m, ∀ v : ℤ, (range (2 ^ j)).sum (fun a =>
          (y (v - (a : ℤ)) a && y (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1 := by
        intro j hj v
        have hjm : 2 ^ j < 2 ^ m := Nat.pow_lt_pow_right (by decide) hj
        have hj1 : 2 ^ (j + 1) = 2 * 2 ^ j := by rw [pow_succ]; ring
        have e := cycle_power_alternating_paired_compression_exact_sum h (2 ^ m - 2 ^ j) (2 ^ j)
          (by omega) (by omega) x' heven v
        have c := hexact (j + 1) (by omega) (2 * v + 1 + s)
        rw [hD, hj1] at c
        have c' : (range (2 * 2 ^ j)).sum (fun a => (x' (2 * v + 1 - (a : ℤ)) a &&
            x' (2 * v + 1 - (a : ℤ)) (a + 2 * (2 ^ m - 2 ^ j))).toNat) = 1 := by
          rw [← c]
          apply sum_congr rfl
          intro a ha
          simp only [hx', hsh]
          rw [show a + 2 * (2 ^ m - 2 ^ j) = a + 2 * h - 2 * 2 ^ j by omega]
        rw [c'] at e
        rw [e]
        apply sum_congr rfl
        intro a ha
        simp only [hy]
        rw [show a + 2 ^ m - 2 ^ j = a + (2 ^ m - 2 ^ j) by omega]
  10. The compressed model y has no island.

    All four conditions required by the induction hypothesis `hshape` at exponent m (tightness, exact dyadic coverage, full distance coverage, and m+1 active classes per vertex) have been established for y. Applying `hshape` to y yields that y has no island.

    line 145

      have yshape := hshape y ytight yexact ycover ycount
  11. The model x has no island: whenever a < b < c < 2^(m+1) with x(p, a) = false and x(p, b) = true, we have x(p, c) = true.

    Suppose a < b < c < 2^(m+1) with x(p, a) = false and x(p, b) = true. If x(p, 1) = false, then hypothesis `hend` forces all inner bits of class p to be false; since 0 ≤ a < b < c < 2^(m+1), b is an inner bit, giving x(p, b) = false, a contradiction. Thus x(p, 1) = true, meaning p is an odd shifted class p = 2*q + 1 + s. For this class, each bit satisfies x(p, j) = y(q, ⌊j/2⌋), so y(q, ⌊a/2⌋) = false and y(q, ⌊b/2⌋) = true, which forces ⌊a/2⌋ < ⌊b/2⌋. If ⌊b/2⌋ = ⌊c/2⌋, then x(p, c) = y(q, ⌊c/2⌋) = y(q, ⌊b/2⌋) = true. If ⌊b/2⌋ < ⌊c/2⌋, the no-island property `yshape` for y gives y(q, ⌊c/2⌋) = true, hence x(p, c) = true.

    lines 146–168

    uses Nat.lt_or_ge

      -- lift back
      intro p a b c hab hbc hc ha hb
      rw [hD] at hc
      cases hp1 : x p 1
      · have := hend p hp1 b (by omega) (by rw [hD]; omega)
        rw [this] at hb; exact absurd hb (by decide)
      · set q := (p - s) / 2
        rcases (show p = 2 * q + s ∨ p = 2 * q + 1 + s by omega) with h0 | hpq
        · rw [h0, hs q] at hp1; exact absurd hp1 (by decide)
        · have hpq := hpq
          have hxy : ∀ j < 2 * h, x p j = y q (j / 2) := by
            intro j hj
            rw [← hdil q j hj, hpq]
          rw [hxy a (by omega)] at ha
          rw [hxy b (by omega)] at hb
          rw [hxy 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 yshape q (a / 2) (b / 2) (c / 2) hab2 h' (by omega) ha hb
          · rw [show c / 2 = b / 2 by omega]; exact hb
Nat.two_pow_pos
For any natural number w, 2^w > 0.
pow_succ
In any monoid, a^(n+1) = a^n * a.
pow_zero
In any monoid, a^0 = 1.
range_one
The range of length 1 consists of the singleton set {0}.
sum_singleton
The sum of a function over a singleton set {a} equals f(a).
Nat.cast_zero
The coercion of 0 from ℕ to any ring or additive group is 0.
sub_zero
Subtracting 0 leaves an element unchanged: a - 0 = a.
zero_add
Adding 0 on the left leaves an element unchanged: 0 + a = a.
Bool.not_not
Double negation of a Boolean value returns the original value: !!b = b.
Int.induction_on
Integer induction: a property holding at 0 and preserved under incrementing and decrementing holds for all integers.
add_zero
Adding 0 on the right leaves an element unchanged: a + 0 = a.
Nat.even_or_odd
Every natural number is either even or odd.
cycle_power_dyadic_class_weight_congr
If two Boolean functions agree on all inputs strictly less than 2^m, their dyadic class weights at exponent m are equal.
cycle_power_dyadic_class_weight_dilate
Dilating a Boolean function by repeating each bit doubles its dyadic class weight at exponent m+1 compared to weight at exponent m.
cycle_power_sum_range_double
A sum over 2n terms can be rewritten as a sum over n pairs of consecutive even and odd terms.
mul_sum
Distributivity of multiplication over a finite sum: a * ∑ f(i) = ∑ a * f(i).
sum_congr
Two finite sums are equal if their index sets are identical and their summands agree on all elements.
cycle_power_alternating_paired_compression_count
In an alternating model where even classes have only endpoints active, the vertex sum at an odd class equals 1 plus the vertex sum of the compressed odd classes.
cycle_power_alternating_paired_compression_cover
If an alternating-paired model covers all distances, then its compressed odd classes cover all distances strictly less than h.
Nat.pow_lt_pow_right
If a > 1 and m < n, then a^m < a^n.
cycle_power_alternating_paired_compression_exact_sum
The dyadic exact sum at scale 2*s and distance 2*d in an alternating model equals the dyadic sum at scale s and distance d in the compressed model.
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_paired (m : ℕ) (hm : 1 ≤ 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)    (hpair : ∀ p : ℤ, x p 1 = true → ∀ j < 2^m, x p (2*j) = x p (2*j+1)) :    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(m+1) →      x p a = false → x p b = true → x p c = true := open Finset in by  set h := 2 ^ m with hh  have hpos : 0 < h := Nat.two_pow_pos m  have hD : 2 ^ (m+1) = 2 * h := by rw [pow_succ]; ring  have hends : ∀ v : ℤ, x v 0 = true ∧ x v (2 * h - 1) = true := by    intro v    have e := hexact 0 (by omega) v    rw [hD] at e    simp only [pow_zero, range_one, sum_singleton, Nat.cast_zero, sub_zero, zero_add] at e    revert e    cases x v 0 <;> cases x v (2 * h - 1) <;> decide  -- parity of the endpoint-only classes  have h2 : ∀ p : ℤ, x (p + 2) 1 = x p 1 := by    intro p    rw [show p + 2 = (p + 1) + 1 by ring, halt (p+1), halt p, Bool.not_not]  have hev : ∀ q : ℤ, x (2 * q) 1 = x 0 1 := by    intro q    induction q using Int.induction_on with    | zero => simp    | succ i ih => rw [show 2 * ((i:ℤ) + 1) = 2 * i + 2 by ring, h2, ih]    | pred i ih =>      rw [← ih, show 2 * (-(i:ℤ)) = 2 * (-(i:ℤ) - 1) + 2 by ring, h2]  obtain ⟨s, hs⟩ : ∃ s : ℤ, ∀ q : ℤ, x (2 * q + s) 1 = false := by    cases h0 : x 0 1    · exact ⟨0, fun q => by rw [add_zero, hev, h0]⟩    · exact ⟨1, fun q => by rw [halt, hev, h0]; rfl⟩  have hs1 : ∀ q : ℤ, x (2 * q + 1 + s) 1 = true := by    intro q    rw [show 2 * q + 1 + s = (2 * q + s) + 1 by ring, halt, hs]; rfl  -- the shifted model  set x' : ℤ → ℕ → Bool := fun q j => x (q + s) j with hx'  have hsh : ∀ v a : ℤ, v - a + s = v + s - a := fun v a => by ring  have heven : ∀ p : ℤ, ∀ j < 2 * h, x' (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1 := by    intro p j hj    simp only [hx']    constructor    · intro hx      by_contra hne      push Not at hne      have := hend (2 * p + s) (hs p) j (by omega) (by rw [hD]; omega)      rw [this] at hx; exact absurd hx (by decide)    · rintro (rfl | rfl)      · exact (hends _).1      · exact (hends _).2  have hpair' : ∀ q : ℤ, ∀ j < h, x' (2 * q + 1) (2 * j) = x' (2 * q + 1) (2 * j + 1) :=    fun q j hj => hpair _ (hs1 q) j hj  have hcover' : ∀ d, 1 ≤ d → d < 2 * h → ∀ u : ℤ,      ∃ a < 2 * h - d, x' (u - (a : ℤ)) a = true ∧ x' (u - (a : ℤ)) (a + d) = true := by    intro d hd1 hd u    obtain ⟨a, ha, h1, h2⟩ := hcover d hd1 (by rw [hD]; exact hd) (u + s)    refine ⟨a, by rw [hD] at ha; exact ha, ?_, ?_⟩    · simp only [hx', hsh]; exact h1    · simp only [hx', hsh]; exact h2  set y : ℤ → ℕ → Bool := fun q i => x' (2 * q + 1) (2 * i) with hy  -- the class of x' at 2q+1 is the dilation of y q  have hdil : ∀ q : ℤ, ∀ j < 2 * h, x' (2 * q + 1) j = y q (j / 2) := by    intro q j hj    simp only [hy]    rcases Nat.even_or_odd j with ⟨t, ht⟩ | ⟨t, ht⟩    · rw [show j / 2 = t by omega, show 2 * t = j by omega]    · rw [show j / 2 = t by omega, hpair' q t (by omega), show 2 * t + 1 = j by omega]  have ytight : ∀ q, cycle_power_dyadic_class_weight m (y q) =      (range (2 ^ m)).sum (fun a => (y q a).toNat) := by    intro q    change cycle_power_dyadic_class_weight m (y q) = (range h).sum (fun a => (y q a).toNat)    have ht := htight (2 * q + 1 + s)    have hw : cycle_power_dyadic_class_weight (m+1) (x (2 * q + 1 + s)) =        cycle_power_dyadic_class_weight (m+1) (fun j => y q (j / 2)) := by      apply cycle_power_dyadic_class_weight_congr      intro i hi      rw [hD] at hi      exact hdil q i hi    rw [hw, cycle_power_dyadic_class_weight_dilate m hm, hD, cycle_power_sum_range_double] at ht    have hs2 : (range h).sum (fun i => (x (2 * q + 1 + s) (2 * i)).toNat +        (x (2 * q + 1 + s) (2 * i + 1)).toNat) = 2 * (range h).sum (fun a => (y q a).toNat) := by      rw [mul_sum]      apply sum_congr rfl      intro i hi      have e := hpair' q i (mem_range.mp hi)      simp only [hx', hy] at e ⊢      rw [← e]; ring    rw [hs2] at ht    omega  have ycount : ∀ v : ℤ, (range (2 ^ m)).sum (fun a => (y (v - (a : ℤ)) a).toNat) = m + 1 := by    intro v    have e := cycle_power_alternating_paired_compression_count h hpos x' heven v    have c := hcount (2 * v + 1 + s)    rw [hD] at c    have c' : (range (2 * h)).sum (fun j => (x' (2 * v + 1 - (j : ℤ)) j).toNat) = m + 1 + 1 := by      simp only [hx', hsh]; exact c    have : (range h).sum (fun j => (x' (2 * (v - (j : ℤ)) + 1) (2 * j)).toNat) = m + 1 := by omega    exact this  have ycover : ∀ d : ℕ, 1 ≤ d → d < 2 ^ m → ∀ v : ℤ,      ∃ a : ℕ, a < 2 ^ m - d ∧ y (v - (a : ℤ)) a = true ∧ y (v - (a : ℤ)) (a + d) = true :=    fun d hd1 hd v => cycle_power_alternating_paired_compression_cover h x' heven hcover' d hd1 hd v  have yexact : ∀ j < m, ∀ v : ℤ, (range (2 ^ j)).sum (fun a =>      (y (v - (a : ℤ)) a && y (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1 := by    intro j hj v    have hjm : 2 ^ j < 2 ^ m := Nat.pow_lt_pow_right (by decide) hj    have hj1 : 2 ^ (j + 1) = 2 * 2 ^ j := by rw [pow_succ]; ring    have e := cycle_power_alternating_paired_compression_exact_sum h (2 ^ m - 2 ^ j) (2 ^ j)      (by omega) (by omega) x' heven v    have c := hexact (j + 1) (by omega) (2 * v + 1 + s)    rw [hD, hj1] at c    have c' : (range (2 * 2 ^ j)).sum (fun a => (x' (2 * v + 1 - (a : ℤ)) a &&        x' (2 * v + 1 - (a : ℤ)) (a + 2 * (2 ^ m - 2 ^ j))).toNat) = 1 := by      rw [← c]      apply sum_congr rfl      intro a ha      simp only [hx', hsh]      rw [show a + 2 * (2 ^ m - 2 ^ j) = a + 2 * h - 2 * 2 ^ j by omega]    rw [c'] at e    rw [e]    apply sum_congr rfl    intro a ha    simp only [hy]    rw [show a + 2 ^ m - 2 ^ j = a + (2 ^ m - 2 ^ j) by omega]  have yshape := hshape y ytight yexact ycover ycount  -- lift back  intro p a b c hab hbc hc ha hb  rw [hD] at hc  cases hp1 : x p 1  · have := hend p hp1 b (by omega) (by rw [hD]; omega)    rw [this] at hb; exact absurd hb (by decide)  · set q := (p - s) / 2    rcases (show p = 2 * q + s ∨ p = 2 * q + 1 + s by omega) with h0 | hpq    · rw [h0, hs q] at hp1; exact absurd hp1 (by decide)    · have hpq := hpq      have hxy : ∀ j < 2 * h, x p j = y q (j / 2) := by        intro j hj        rw [← hdil q j hj, hpq]      rw [hxy a (by omega)] at ha      rw [hxy b (by omega)] at hb      rw [hxy 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 yshape q (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