cycle_power_dyadic_no_island_of_alternating_paired
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
- cycle_power_dyadic_class_weight_congrThe dyadic class weight cycle_power_dyadic_class_weight m b depends only on the values b i for i < 2^m: if b i = b' i for every i < 2^m,…
- 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_class_weight_dilateDuplicating each membership bit of a dyadic class doubles its dyadic class weight, when the original radius is at least two.
- cycle_power_sum_range_doubleA sum over the first 2n indices equals the sum over n consecutive even-odd pairs.
- cycle_power_alternating_paired_compression_countAt every odd vertex, when all even-start classes consist exactly of their two endpoints, the original active count is one plus the count…
- cycle_power_alternating_paired_compression_coverIf all even-start classes are endpoint-only and all original distances less than 2h are covered, the odd-start classes, compressed to…
- cycle_power_alternating_paired_compression_exact_sumFor a positive distance d and s+d at most h, the original sum over 2s possible witnesses for distance 2d at an odd vertex equals the…
- Used by 1
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_alternating_pairedConditional resolution of OP-205: if, for every m ≥ 5, every tight, exactly dyadically covered, fully ordinarily covered integer Boolean…
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.
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`.
uses
Nat.two_pow_pos,pow_succset 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
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.
uses
pow_zero,range_one,sum_singleton,Nat.cast_zero,sub_zero,zero_addhave 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
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.
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
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'.
-- 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
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).
uses
Nat.even_or_oddset 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]
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).
uses
cycle_power_dyadic_class_weight_congr,cycle_power_dyadic_class_weight_dilate,cycle_power_sum_range_double,mul_sum,sum_congrhave 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
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.
uses
cycle_power_alternating_paired_compression_counthave 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
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.
uses
cycle_power_alternating_paired_compression_coverhave 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
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.
uses
Nat.pow_lt_pow_right,pow_succ,cycle_power_alternating_paired_compression_exact_sum,sum_congrhave 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]
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.
have yshape := hshape y ytight yexact ycover ycountThe 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.
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.
- In Step 2 (line 38), the truth table check from the dyadic sum condition (x(v,0) && x(v, 2h-1)).toNat = 1 to x(v,0) = true and x(v, 2h-1) = true is closed by finite Boolean case exhaustion (`decide`).
- In Step 11, arithmetic relationships between the halved indices (such as deriving ⌊a/2⌋ < ⌊b/2⌋ from a < b and ⌊a/2⌋ ≠ ⌊b/2⌋) are discharged by `omega`.
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_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