cycle_power_sixteen_block_no_vertical_overlap
For any positive h and Boolean rooted model of radius16h satisfying the explicit Geometry hypotheses (selected endpoints, three parent matchings, exact12h/14h/15h ownership, monotone outer eighths, full ordinary coverage), suppose globally every selected C_t at offset2h+t also selects A_t at offset t. Then no root can select A_t,C_t while missing A_s with t<s<2h.
Statement
theorem cycle_power_sixteen_block_no_vertical_overlap
(h : ℕ) (x : ℤ → ℕ → Bool) (M : CyclePowerSixteenBlock.Geometry h x)
(nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true)
(p : ℤ) (t s : ℕ) (hts : t < s) (hsq : s < 2*h)
(hA : x p t = true) (hC : x p (2*h+t) = true) (hm : x p s = false) : False- Source
- Uniform structural reduction for OP-205 / RT-1 following arXiv:2610.15635. The main covering theorem and vertical-defect exclusion remain open. Experiments8048/8049 suggested the two ordinary distances; the proof is uniform in h and uses Lean only. No advance flag.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- cycle_power_eight_block_overlap_stabilizesUnder the explicit no-vertical hypothesis and active-root separation, every overlap defect yields the rigid three-root stable-overlap…
- cycle_power_eight_block_active_retained_halvesUnder the explicit seven-eighth parent and monotone outer eighths, a root selecting A_t and Z_t retains every first-h and last-h offset.
- cycle_power_eight_block_active_root_separationUnder the explicit third parent, monotone outer eighths and exact distance15h ownership, distinct roots selecting an A/Z overlap are…
- cycle_power_eight_block_double_gap_transferConditional on no vertical defects and h-separated active roots, two gap transfers preserve the gap, move the physical selected vertex…
- cycle_power_exact_pair_uniqueAn exact Boolean long-edge count of one gives a unique owning rooted class.
- cycle_power_eight_block_stable_overlapDefinition of a rigid overlap pattern on three roots p,p-h,p-2h with alternating selected offsets t and s-h and the displayed missing…
- Used by 9
- cycle_power_sixteen_block_second_eighth_monotoneUnder the Geometry hypotheses and the global no-vertical condition C_t implies A_t, the second eighth is an initial segment: u<=t<2h and…
- cycle_power_sixteen_block_left_quarter_of_no_verticalUnder the Geometry hypotheses and the global no-vertical condition C_t implies A_t, every first quarter of length4h is a selected initial…
- cycle_power_dyadic_outer_quarter_monotone_of_sixteen_block_coreConditional on upper-vertical exclusion only at dyadic block sizes h=2^j, every tight all-rank-exact fully ordinarily covered dyadic model…
- cycle_power_sixteen_block_outer_quarters_of_upper_verticalConditional on upper-half vertical exclusion for every Geometry model at the same h with exact8h ownership, a given such model has BOTH…
- cycle_power_dyadic_sixteen_block_geometryEvery tight dyadic rooted model of radius2^(k+4), with all-rank exactness, full ordinary coverage and monotone outer eighths, satisfies…
- cycle_power_sixteen_block_geometry_reflectThe full radius16h Geometry hypotheses, including all ordinary distances and exact12h/14h/15h ownership, are preserved by simultaneous…
- cycle_power_sixteen_block_overlap_reaches_upper_verticalUnder the explicit Geometry hypotheses, every overlap A_t,C_t selected and A_s missing with t<s<2h forces some upper-half vertical defect:…
- cycle_power_sixteen_block_left_defect_reaches_upper_verticalUnder the Geometry hypotheses, every first-quarter prefix defect (a<=b<4h, position a missing and b selected) forces an upper-half…
- cycle_power_sixteen_block_child_forces_full_prefixUnder the explicit Geometry hypotheses and the global no-vertical-defect condition C_t implies A_t, every root with any selected C_t has…
The proof, explained
The theorem proves that no root can select offsets t and 2h + t while missing an intermediate offset s with t < s < 2h. The argument stabilizes any assumed vertical overlap into three consecutive active roots spaced by h that all miss the boundary index 2h - 1. This boundary condition forces the third root to be canonical, which propagates backward to form an infinite chain of canonical roots. Finally, exact covering and ownership constraints in the 16-block geometry show that such an infinite chain cannot exist, completing the proof by contradiction.
For any offset a < 2h, selecting offset 2h + a forces selection at offset 14h + a.
Applying the parent matching hypothesis parent6 at offset 2h + a lifts the selection to offset 2h + a + 12h = 14h + a.
have hh := (M.parent6 p (2*h+a) (by omega)).2 (by omega) hc convert hh using 1 <;> congr 1 <;> omega
Every active root selects all offsets a < h and all offsets 15h + a for a < h.
This follows from cycle_power_eight_block_active_retained_halves using the parent7 hypothesis and monotonic outer eighths.
uses
cycle_power_eight_block_active_retained_halveslemma Geometry.fullRetained (M : Geometry h x) {p : ℤ} (hp : Active h x p) : ∀ a < h, x p a = true ∧ x p (15*h+a) = true := by obtain ⟨t,ht,hA,hB⟩ := hp exact cycle_power_eight_block_active_retained_halves h x M.parent7 (fun p => ⟨M.lowMono p,M.highMono p⟩) p t ht hA hB
Two distinct active roots p < r must satisfy r - p ≥ h.
Using cycle_power_eight_block_active_root_separation together with the exactness hypothesis exact15, any two active roots must be separated by at least h.
uses
cycle_power_eight_block_active_root_separationlemma Geometry.sep (M : Geometry h x) {p r : ℤ} (hpr : p < r) (hp : Active h x p) (hr : Active h x r) : (h : ℤ) ≤ r-p := by obtain ⟨t,ht,hpA,hpB⟩ := hp obtain ⟨u,hu,hrA,hrB⟩ := hr let d := (r-p).toNat have hd : r=p+(d : ℤ) := by dsimp [d]; omega have hs := cycle_power_eight_block_active_root_separation h M.pos x M.parent7 (fun p => ⟨M.lowMono p,M.highMono p⟩) M.exact15 p d t u (by dsimp [d]; omega) ht hu hpA hpB (by simpa only [← hd] using hrA) (by simpa only [← hd] using hrB) omega
Ownership of 12h-separated pairs is unique among offsets below 4h.
Using cycle_power_exact_pair_unique with the exact6 summation hypothesis, no two distinct roots can place a 12h-separated pair at the same absolute coordinates.
uses
cycle_power_exact_pair_uniquelemma Geometry.own6 (M : Geometry h x) (p r : ℤ) (a b : ℕ) (ha : a < 4*h) (hb : b < 4*h) (he : p+(a : ℤ)=r+(b : ℤ)) (hpa : x p a = true) (hpa' : x p (a+12*h) = true) (hrb : x r b = true) (hrb' : x r (b+12*h) = true) : p=r := by have hex : ∀ v : ℤ, (range (4*h)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+16*h-4*h)).toNat) = 1 := by intro v have hi (a : ℕ) : a+16*h-4*h=a+12*h := by omega simpa only [hi] using M.exact6 v have hu := cycle_power_exact_pair_unique (16*h) (4*h) x hex (p+(a : ℤ)) a b ha hb (by simpa using hpa) (by simpa only [add_sub_cancel_right,show a+16*h-4*h=a+12*h by omega] using hpa') (by convert hrb using 1 <;> congr 1 <;> omega) (by convert hrb' using 1 <;> congr 1 <;> omega) omega
Ownership of 14h-separated pairs is unique among offsets below 2h.
Similarly, cycle_power_exact_pair_unique with the exact7 summation hypothesis establishes that 14h-separated pairs have unique root ownership.
uses
cycle_power_exact_pair_uniquelemma Geometry.own7 (M : Geometry h x) (p r : ℤ) (a b : ℕ) (ha : a < 2*h) (hb : b < 2*h) (he : p+(a : ℤ)=r+(b : ℤ)) (hpa : x p a = true) (hpa' : x p (a+14*h) = true) (hrb : x r b = true) (hrb' : x r (b+14*h) = true) : p=r := by have hex : ∀ v : ℤ, (range (2*h)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+16*h-2*h)).toNat) = 1 := by intro v have hi (a : ℕ) : a+16*h-2*h=a+14*h := by omega simpa only [hi] using M.exact7 v have hu := cycle_power_exact_pair_unique (16*h) (2*h) x hex (p+(a : ℤ)) a b ha hb (by simpa using hpa) (by simpa only [add_sub_cancel_right,show a+16*h-2*h=a+14*h by omega] using hpa') (by convert hrb using 1 <;> congr 1 <;> omega) (by convert hrb' using 1 <;> congr 1 <;> omega) omega
An active root r in the window (p - 3h, p + h) of three active roots p, p - h, p - 2h must be equal to one of those three roots.
By root separation, r must either equal each known active root or be at distance at least h from it. Linear trichotomy (lt_trichotomy) applied to p, p - h, and p - 2h forces r to equal one of them.
uses
lt_trichotomylemma Geometry.grid (M : Geometry h x) (p r : ℤ) (hr : Active h x r) (h0 : Active h x p) (h1 : Active h x (p-(h : ℤ))) (h2 : Active h x (p-(2*h : ℕ))) (hl : p-(3*h : ℕ) < r) (hu : r < p+(h : ℤ)) : r=p ∨ r=p-(h : ℤ) ∨ r=p-(2*h : ℕ) := by have cmp (a : ℤ) (ha : Active h x a) : r=a ∨ r+(h : ℤ) ≤ a ∨ a+(h : ℤ) ≤ r := by rcases lt_trichotomy r a with hlt | he | hgt · have hs := M.sep hlt hr ha omega · exact Or.inl he · have hs := M.sep hgt ha hr omega have hc0 := cmp p h0 have hc1 := cmp (p-(h : ℤ)) h1 have hc2 := cmp (p-(2*h : ℕ)) h2 push_cast at * omega
Covering offset 13h produces a root with an active witness below 3h.
The cover hypothesis provides a pair at offset 13h. A case analysis on the offset a < 3h shows that the root is active using parent6, parent7, or monotonicity.
lemma Geometry.cover13Active (M : Geometry h x) (v : ℤ) : ∃ a < 3*h, x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+13*h) = true ∧ Active h x (v-(a : ℤ)) := by obtain ⟨a,ha,hA,hB⟩ := M.cover (13*h) (by have := M.pos; omega) (by have := M.pos; omega) v have ha3 : a < 3*h := by omega refine ⟨a,ha3,hA,hB,?_⟩ let p := v-(a : ℤ) by_cases ha1 : a < h · have hh : x p (h+a) = true := by apply (M.parent6 p (h+a) (by omega)).1 (by omega) convert hB using 1 <;> congr 1 <;> omega have hz := (M.parent7 p (h+a) (by omega)).2 (by omega) hh exact ⟨h+a,by omega,hh,by convert hz using 1 <;> congr 1 <;> omega⟩ · by_cases ha2 : a < 2*h · refine ⟨a,ha2,hA,?_⟩ apply M.highMono p (a+13*h) (14*h+a) (by omega) (by omega) (by omega) exact hB · let b := a-2*h have hb : b < h := by dsimp [b]; omega have hc : x p (2*h+b) = true := by convert hA using 1 <;> congr 1 <;> dsimp [b] <;> omega have hz := M.childZ p b (by omega) hc have ha' := (M.parent7 p b (by omega)).1 hb (by convert hz using 1 <;> congr 1 <;> omega) exact ⟨b,by omega,ha',hz⟩
Every canonical root is active.
A canonical root selects h - 1 and 3h - 1 = 2h + (h - 1). By childZ, it also selects 14h + (h - 1), witnessing that it is active.
lemma Geometry.canonicalActive (M : Geometry h x) {p : ℤ} (hp : Canonical h x p) : Active h x p := by have hc : x p (2*h+(h-1)) = true := by convert hp.2.1 using 1 <;> congr 1 <;> have := M.pos <;> omega exact ⟨h-1,by have := M.pos; omega,hp.1,M.childZ p (h-1) (by have := M.pos; omega) hc⟩
If a root misses any index below 2h, it must miss the boundary index 2h - 1.
By low monotonicity, if the root selected 2h - 1, it would have to select every index below it, contradicting the missed index.
lemma Geometry.missLast (M : Geometry h x) {p : ℤ} {a : ℕ} (ha : a < 2*h) (hm : x p a = false) : x p (2*h-1) = false := by apply Bool.eq_false_iff.mpr intro hc have hh := M.lowMono p a (2*h-1) (by omega) (by have := M.pos; omega) hc rw [hm] at hh contradiction
If three consecutive active roots p, p - h, p - 2h all miss 2h - 1, then p - 2h is canonical.
Covering 13h at coordinate p + h - 1 yields an active root in the grid window. Eliminating the alternatives p and p - h using their missed values forces p - 2h to have the selections required by Canonical.
lemma Geometry.maxChildOfThree (M : Geometry h x) (p : ℤ) (h0 : Active h x p) (h1 : Active h x (p-(h : ℤ))) (h2 : Active h x (p-(2*h : ℕ))) (m0 : x p (2*h-1) = false) (m1 : x (p-(h : ℤ)) (2*h-1) = false) (m2 : x (p-(2*h : ℕ)) (2*h-1) = false) : Canonical h x (p-(2*h : ℕ)) := by obtain ⟨a,ha,hA,hB,hact⟩ := M.cover13Active (p+(h : ℤ)-1) have hg := M.grid p (p+(h : ℤ)-1-(a : ℤ)) hact h0 h1 h2 (by have := M.pos; omega) (by omega) rcases hg with he | he | he · have hh : x p (2*h-1) = true := by apply (M.parent6 p (2*h-1) (by have := M.pos; omega)).1 (by have := M.pos; omega) convert hB using 1 <;> congr 1 <;> have := M.pos <;> omega rw [m0] at hh contradiction · have hh : x (p-(h : ℤ)) (2*h-1) = true := by convert hA using 1 <;> congr 1 <;> omega rw [m1] at hh contradiction · refine ⟨(M.fullRetained h2 (h-1) (by have := M.pos; omega)).1,?_,m2⟩ convert hA using 1 <;> congr 1 <;> omega
Three consecutive canonical roots at p, p - h, p - 2h force p - 3h to be canonical as well.
Covering 13h at p - 1 identifies p - 3h as the only consistent root. The ownership lemma own7 ensures that the canonical conditions at p - 3h are satisfied.
uses
lt_trichotomylemma Geometry.backward (M : Geometry h x) (p : ℤ) (h0 : Canonical h x p) (h1 : Canonical h x (p-(h : ℤ))) (h2 : Canonical h x (p-(2*h : ℕ))) : Canonical h x (p-(3*h : ℕ)) := by obtain ⟨a,ha,hA,hB,hact⟩ := M.cover13Active (p-1) have cmp (z : ℤ) (hz : Active h x z) : p-1-(a : ℤ)=z ∨ p-1-(a : ℤ)+(h : ℤ) ≤ z ∨ z+(h : ℤ) ≤ p-1-(a : ℤ) := by rcases lt_trichotomy (p-1-(a : ℤ)) z with hl | he | hr · have hs := M.sep hl hact hz omega · exact Or.inl he · have hs := M.sep hr hz hact omega have c1 := cmp (p-(h : ℤ)) (M.canonicalActive h1) have c2 := cmp (p-(2*h : ℕ)) (M.canonicalActive h2) have he : p-1-(a : ℤ)=p-(h : ℤ) ∨ p-1-(a : ℤ)=p-(2*h : ℕ) ∨ p-1-(a : ℤ)=p-(3*h : ℕ) := by push_cast at *; have := M.pos; omega rcases he with he | he | he · have hh : x (p-(h : ℤ)) (2*h-1) = true := by apply (M.parent6 (p-(h : ℤ)) (2*h-1) (by have := M.pos; omega)).1 (by have := M.pos; omega) convert hB using 1 <;> congr 1 <;> have := M.pos <;> omega rw [h1.2.2] at hh contradiction · have hh : x (p-(2*h : ℕ)) (2*h-1) = true := by convert hA using 1 <;> congr 1 <;> have := M.pos <;> omega rw [h2.2.2] at hh contradiction · have hc : x (p-(3*h : ℕ)) (3*h-1) = true := by convert hA using 1 <;> congr 1 <;> have := M.pos <;> omega have hc' : x (p-(3*h : ℕ)) (2*h+(h-1)) = true := by convert hc using 1 <;> congr 1 <;> have := M.pos <;> omega have hz := M.childZ (p-(3*h : ℕ)) (h-1) (by have := M.pos; omega) hc' have hlo := (M.parent7 (p-(3*h : ℕ)) (h-1) (by have := M.pos; omega)).1 (by have := M.pos; omega) (by convert hz using 1 <;> congr 1 <;> omega) refine ⟨hlo,hc,?_⟩ apply Bool.eq_false_iff.mpr intro hf have h2c : x (p-(2*h : ℕ)) (2*h+(h-1)) = true := by convert h2.2.1 using 1 <;> congr 1 <;> have := M.pos <;> omega have h2z := M.childZ (p-(2*h : ℕ)) (h-1) (by have := M.pos; omega) h2c have heq := M.own7 (p-(3*h : ℕ)) (p-(2*h : ℕ)) (2*h-1) (h-1) (by have := M.pos; omega) (by have := M.pos; omega) (by omega) hf (by convert (M.ends (p-(3*h : ℕ))).2 using 1 <;> congr 1 <;> have := M.pos <;> omega) h2.1 (by convert h2z using 1 <;> congr 1 <;> omega) have := M.pos omega end CyclePowerSixteenBlock
No vertical overlap can occur at an offset t ≥ h.
Strong induction on 2h - t using the gap transfer lemma cycle_power_eight_block_double_gap_transfer shows that any vertical overlap with t ≥ h leads to a contradiction.
uses
Nat.strong_induction_on,cycle_power_eight_block_double_gap_transfernamespace CyclePowerSixteenBlock variable {h : ℕ} {x : ℤ → ℕ → Bool} lemma Geometry.noHighOverlap (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) (p : ℤ) (t s : ℕ) (ht : h ≤ t) (hts : t < s) (hs : s < 2*h) (hA : x p t = true) (hC : x p (2*h+t) = true) (hm : x p s = false) : False := by have aux : ∀ N : ℕ, ∀ (p : ℤ) (t s : ℕ), 2*h-t=N → h ≤ t → t < s → s < 2*h → x p t = true → x p (2*h+t) = true → x p s = false → False := by intro N induction N using Nat.strong_induction_on with | h N ih => intro p t s hN ht hts hs hA hC hm obtain ⟨u,v,hu,hv,htv,hAu,hCu,hMu,hAv,hCv,hMv,heq⟩ := cycle_power_eight_block_double_gap_transfer h t s M.pos hts hs x p M.lowMono M.parent6 M.exact6 M.exact7 M.cover nov (fun p r a b hpr ha hb hpA hpB hrA hrB => M.sep hpr ⟨a,ha,hpA,hpB⟩ ⟨b,hb,hrA,hrB⟩) hA hC hm by_cases he : v=t · have he' := heq he omega · exact ih (2*h-v) (by omega) (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) v (v+s-t) rfl (by omega) (by omega) (by omega) hAv hCv hMv exact aux (2*h-t) p t s rfl ht hts hs hA hC hm
A canonical root must evaluate to false at offset 3h.
If a canonical root selected 3h = 2h + h, no-overlap would force selection at h, which by noHighOverlap contradicts the canonical missing value at 2h - 1.
lemma Geometry.midChildFalse (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) {p : ℤ} (hp : Canonical h x p) : x p (3*h) = false := by apply Bool.eq_false_iff.mpr intro hc have hc' : x p (2*h+h) = true := by convert hc using 1 <;> congr 1 <;> omega have ha := nov p h (by have := M.pos; omega) hc' by_cases he : h=2*h-1 · rw [he,hp.2.2] at ha contradiction · exact M.noHighOverlap nov p h (2*h-1) le_rfl (by have := M.pos; omega) (by have := M.pos; omega) ha hc' hp.2.2
A canonical root at p forces canonical roots at p - h and p - 2h.
Applying cycle_power_eight_block_double_gap_transfer to the canonical pattern at p transfers the configuration to shifts p - h and p - 2h with identical boundary values.
uses
cycle_power_eight_block_double_gap_transferlemma Geometry.canonicalTriple (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) {p : ℤ} (hp : Canonical h x p) : Canonical h x p ∧ Canonical h x (p-(h : ℤ)) ∧ Canonical h x (p-(2*h : ℕ)) := by obtain ⟨u,v,hu,hv,htv,hAu,hCu,hMu,hAv,hCv,hMv,heq⟩ := cycle_power_eight_block_double_gap_transfer h (h-1) (2*h-1) M.pos (by have := M.pos; omega) (by have := M.pos; omega) x p M.lowMono M.parent6 M.exact6 M.exact7 M.cover nov (fun p r a b hpr ha hb hpA hpB hrA hrB => M.sep hpr ⟨a,ha,hpA,hpB⟩ ⟨b,hb,hrA,hrB⟩) hp.1 (by convert hp.2.1 using 1 <;> congr 1 <;> have := M.pos <;> omega) hp.2.2 have hvEq : v=h-1 := by have := M.pos; omega have huEq : u=h-1 := by have hh := heq hvEq; have := M.pos; omega refine ⟨hp,⟨?_,?_,?_⟩,⟨?_,?_,?_⟩⟩ · convert hAu using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hCu using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hMu using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hAv using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hCv using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hMv using 1 <;> congr 1 <;> have := M.pos <;> omega
A canonical triple at p, p - h, p - 2h propagates to an infinite backward chain of canonical roots at p - n*h for all n ∈ ℕ.
By induction on n, each new step backward is provided by the backward propagation lemma.
lemma Geometry.canonicalChain (M : Geometry h x) {p : ℤ} (hp : Canonical h x p) (h1 : Canonical h x (p-(h : ℤ))) (h2 : Canonical h x (p-(2*h : ℕ))) : ∀ n : ℕ, Canonical h x (p-(n : ℤ)*(h : ℤ)) := by have aux (n : ℕ) : Canonical h x (p-(n : ℤ)*(h : ℤ)) ∧ Canonical h x (p-((n : ℤ)+1)*(h : ℤ)) ∧ Canonical h x (p-((n : ℤ)+2)*(h : ℤ)) := by induction n with | zero => simpa using And.intro hp (And.intro h1 h2) | succ n ih => have hb := M.backward (p-(n : ℤ)*(h : ℤ)) ih.1 (by convert ih.2.1 using 1 <;> push_cast <;> ring) (by convert ih.2.2 using 1 <;> push_cast <;> ring) refine ⟨?_,?_,?_⟩ · convert ih.2.1 using 1 <;> push_cast <;> ring · convert ih.2.2 using 1 <;> push_cast <;> ring · convert hb using 1 <;> push_cast <;> ring exact fun n => (aux n).1 end CyclePowerSixteenBlock
Three spaced canonical roots force the lowest root r to select offset 12h.
Covering offset 12h - 1 from coordinate r + 4h leaves only the root r capable of owning the required pair, forcing selection at 12h.
uses
lt_trichotomynamespace CyclePowerSixteenBlock variable {h : ℕ} {x : ℤ → ℕ → Bool} lemma Geometry.forceH0 (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) (r : ℤ) (hr : Canonical h x r) (hp : Canonical h x (r+(h : ℤ))) (hv : Canonical h x (r+(4*h : ℕ))) : x r (12*h) = true := by let v : ℤ := r+(4*h : ℕ) let p : ℤ := r+(h : ℤ) obtain ⟨a,ha,hA,hB⟩ := M.cover (12*h-1) (by have := M.pos; omega) (by have := M.pos; omega) v have ha4 : a ≤ 4*h := by have := M.pos; omega let w : ℤ := v-(a : ℤ) by_cases ha0 : a=0 · have hg : x v (12*h-1) = true := by simpa only [ha0,Nat.cast_zero,sub_zero,zero_add] using hB have hc : x v (4*h-1) = true := by apply (M.parent4 v (4*h-1) (by have := M.pos; omega)).1 (by have := M.pos; omega) convert hg using 1 <;> congr 1 <;> have := M.pos <;> omega have hc' : x v (2*h+(2*h-1)) = true := by convert hc using 1 <;> congr 1 <;> have := M.pos <;> omega have hm := nov v (2*h-1) (by have := M.pos; omega) hc' rw [hv.2.2] at hm contradiction · by_cases ha2 : a ≤ 2*h · have hl : x w (a-1) = true := by apply (M.parent6 w (a-1) (by omega)).1 (by omega) convert hB using 1 <;> congr 1 <;> have := M.pos <;> omega have hpZ := M.childZ p (h-1) (by have := M.pos; omega) (by convert hp.2.1 using 1 <;> congr 1 <;> have := M.pos <;> omega) have he := M.own6 w p (a-1) (3*h-1) (by omega) (by have := M.pos; omega) (by dsimp [w,v,p]; have := M.pos; omega) hl (by convert hB using 1 <;> congr 1 <;> have := M.pos <;> omega) hp.2.1 (by convert hpZ using 1 <;> congr 1 <;> have := M.pos <;> omega) dsimp [w,v,p] at he have := M.pos omega · by_cases haEq : a=4*h · have hD : x r (4*h) = true := by convert hA using 1 <;> congr 1 <;> (try dsimp [v]) <;> omega have hh := (M.parent4 r (4*h) (by have := M.pos; omega)).2 le_rfl hD convert hh using 1 <;> congr 1 <;> omega · let b := a-2*h have hb : b < 2*h := by dsimp [b]; omega have hC : x w (2*h+b) = true := by convert hA using 1 <;> congr 1 <;> dsimp [b] <;> omega have hw : Active h x w := ⟨b,hb,nov w b hb hC,M.childZ w b hb hC⟩ have hpAct : Active h x p := M.canonicalActive hp have hew : w=p := by rcases lt_trichotomy w p with hlt | he | hgt · have hs := M.sep hlt hw hpAct dsimp [w,v,p] at hs have := M.pos omega · exact he · have hs := M.sep hgt hpAct hw dsimp [w,v,p] at hs have := M.pos omega dsimp [w,v,p] at hew have hc : x p (3*h) = true := by convert hA using 1 <;> congr 1 <;> (try dsimp [v,p]) <;> omega rw [M.midChildFalse nov hp] at hc contradiction
Adjacent selections at 12h force the shifted root to select offsets h and 14h.
Covering 13h near the roots and matching with the 12h selections via parent6 and own6 forces the root v - h to select both h and 14h.
lemma Geometry.cornerFromH0 (M : Geometry h x) (v : ℤ) (h0 : Canonical h x v) (h1 : Canonical h x (v-(h : ℤ))) (h2 : Canonical h x (v-(2*h : ℕ))) (hH : x v (12*h) = true) (hHnext : x (v+(h : ℤ)) (12*h) = true) : x (v-(h : ℤ)) h = true ∧ x (v-(h : ℤ)) (14*h) = true := by obtain ⟨a,ha,hA,hB,hact⟩ := M.cover13Active v have hg := M.grid v (v-(a : ℤ)) hact (M.canonicalActive h0) (M.canonicalActive h1) (M.canonicalActive h2) (by omega) (by have := M.pos; omega) rcases hg with he | he | he · have hh : x v (h+12*h) = true := by convert hB using 1 <;> congr 1 <;> omega have hl := (M.parent6 v h (by have := M.pos; omega)).1 (by have := M.pos; omega) hh have heq := M.own6 v (v+(h : ℤ)) h 0 (by have := M.pos; omega) (by have := M.pos; omega) (by omega) hl hh (M.ends _).1 (by simpa using hHnext) have := M.pos omega · constructor · convert hA using 1 <;> congr 1 <;> omega · convert hB using 1 <;> congr 1 <;> omega · have hc : x (v-(2*h : ℕ)) (2*h+0) = true := by convert hA using 1 <;> congr 1 <;> omega have hz := M.childZ (v-(2*h : ℕ)) 0 (by have := M.pos; omega) hc have heq := M.own6 (v-(2*h : ℕ)) v (2*h) 0 (by have := M.pos; omega) (by have := M.pos; omega) (by omega) (by simpa using hc) (by convert hz using 1 <;> congr 1 <;> omega) (M.ends v).1 (by simpa using hH) have := M.pos omega
An infinite backward chain of canonical roots is impossible.
Applying forceH0 and cornerFromH0 along the chain produces conflicting 14h-pair ownerships between roots shifted by h, contradicting own7.
lemma Geometry.chainImpossible (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) (p : ℤ) (chain : ∀ n : ℕ, Canonical h x (p-(n : ℤ)*(h : ℤ))) : False := by have ch (n : ℕ) : Canonical h x (p-(n : ℤ)*(h : ℤ)) := chain n have hf (j : ℕ) (hj : 4 ≤ j) : x (p-(j : ℤ)*(h : ℤ)) (12*h) = true := by apply M.forceH0 nov (p-(j : ℤ)*(h : ℤ)) (ch j) · convert ch (j-1) using 1 <;> push_cast [Nat.cast_sub (by omega : 1 ≤ j)] <;> ring · convert ch (j-4) using 1 <;> push_cast [Nat.cast_sub hj] <;> ring have hc5 := M.cornerFromH0 (p-5*(h : ℤ)) (by simpa using ch 5) (by convert ch 6 using 1 <;> push_cast <;> ring) (by convert ch 7 using 1 <;> push_cast <;> ring) (by simpa using hf 5 (by omega)) (by convert hf 4 (by omega) using 1 <;> push_cast <;> ring) have hc6 := M.cornerFromH0 (p-6*(h : ℤ)) (by simpa using ch 6) (by convert ch 7 using 1 <;> push_cast <;> ring) (by convert ch 8 using 1 <;> push_cast <;> ring) (by simpa using hf 6 (by omega)) (by convert hf 5 (by omega) using 1 <;> push_cast <;> ring) have hz : x (p-6*(h : ℤ)-(h : ℤ)) (h+14*h) = true := by apply M.highMono _ (14*h) (h+14*h) le_rfl (by omega) (by have := M.pos; omega) exact hc6.2 have heq := M.own7 (p-6*(h : ℤ)-(h : ℤ)) (p-5*(h : ℤ)-(h : ℤ)) h 0 (by have := M.pos; omega) (by have := M.pos; omega) (by ring) hc6.1 hz (M.ends _).1 (by simpa using hc5.2) have := M.pos omega end CyclePowerSixteenBlock
No root can have a vertical overlap.
An assumed vertical overlap at root p stabilizes via cycle_power_eight_block_overlap_stabilizes into three active roots missing 2h - 1. This forces r - 2h to be canonical, which spawns an infinite canonical chain that contradicts chainImpossible.
uses
cycle_power_eight_block_overlap_stabilizestheorem cycle_power_sixteen_block_no_vertical_overlap (h : ℕ) (x : ℤ → ℕ → Bool) (M : CyclePowerSixteenBlock.Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) (p : ℤ) (t s : ℕ) (hts : t < s) (hsq : s < 2*h) (hA : x p t = true) (hC : x p (2*h+t) = true) (hm : x p s = false) : False := by obtain ⟨r,a,b,ha,hb,hbq,hA0,hC0,hm0,hA1,hC1,hm1,hA2,hC2,hm2⟩ := cycle_power_eight_block_overlap_stabilizes h M.pos x M.lowMono M.parent6 M.exact6 M.exact7 M.cover nov (fun p r a b hpr ha hb hpA hpB hrA hrB => M.sep hpr ⟨a,ha,hpA,hpB⟩ ⟨b,hb,hrA,hrB⟩) p t s hts hsq hA hC hm have a0 : CyclePowerSixteenBlock.Active h x r := ⟨a,by omega,hA0,M.childZ r a (by omega) hC0⟩ have a1 : CyclePowerSixteenBlock.Active h x (r-(h : ℤ)) := ⟨b-h,by omega,hA1,M.childZ _ (b-h) (by omega) hC1⟩ have a2 : CyclePowerSixteenBlock.Active h x (r-(2*h : ℕ)) := ⟨a,by omega,hA2,M.childZ _ a (by omega) hC2⟩ have cc := M.maxChildOfThree r a0 a1 a2 (M.missLast hbq hm0) (M.missLast (by omega) hm1) (M.missLast hbq hm2) obtain ⟨c0,c1,c2⟩ := M.canonicalTriple nov cc
cycle_power_eight_block_active_retained_halves- An active root retains true at all offsets below h and at all offsets 15h + a for a < h.
cycle_power_eight_block_active_root_separation- Two active roots in the eight-block geometry must be separated by at least h.
cycle_power_exact_pair_unique- In a model with exact coverage by pairs of offset D - R, any two such pairs occurring at the same absolute position must coincide.
Nat.strong_induction_on- Strong induction on the natural numbers.
lt_trichotomy- Linear trichotomy: for any two elements in a linear order, either the first is less, they are equal, or the second is less.
cycle_power_eight_block_double_gap_transfer- A vertical overlap transfers across gaps to produce a strictly smaller or shifted overlap configuration.
cycle_power_eight_block_overlap_stabilizes- Any vertical overlap stabilizes to a periodic configuration across three roots spaced by multiples of h.
- The Lean proof is organized into 18 helper lemmas followed by the main theorem; the checker requires steps to partition all 19 declarations in the file.
- Unresolved check: no step explains line(s) 420 -- every tactic of the proof has to belong to some step
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.
Lean’s trace was cut to the first 400 of 600 tactics.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000namespace CyclePowerSixteenBlockstructure Geometry (h : ℕ) (x : ℤ → ℕ → Bool) : Prop where pos : 0 < h ends : ∀ p, x p 0 = true ∧ x p (16*h-1) = true lowMono : ∀ p a b, a ≤ b → b < 2*h → x p b = true → x p a = true highMono : ∀ p a b, 14*h ≤ a → a ≤ b → b < 16*h → x p a = true → x p b = true parent4 : ∀ p a, a < 8*h → (a < 4*h → x p (a+8*h) = true → x p a = true) ∧ (4*h ≤ a → x p a = true → x p (a+8*h) = true) parent6 : ∀ p a, a < 4*h → (a < 2*h → x p (a+12*h) = true → x p a = true) ∧ (2*h ≤ a → x p a = true → x p (a+12*h) = true) parent7 : ∀ p a, a < 2*h → (a < h → x p (a+14*h) = true → x p a = true) ∧ (h ≤ a → x p a = true → x p (a+14*h) = true) exact6 : ∀ v : ℤ, (range (4*h)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+12*h)).toNat) = 1 exact7 : ∀ v : ℤ, (range (2*h)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+14*h)).toNat) = 1 exact15 : ∀ v : ℤ, (range h).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+15*h)).toNat) = 1 cover : ∀ d : ℕ, 1 ≤ d → d < 16*h → ∀ v : ℤ, ∃ a : ℕ, a < 16*h-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = truedef Active (h : ℕ) (x : ℤ → ℕ → Bool) (p : ℤ) : Prop := ∃ t < 2*h, x p t = true ∧ x p (14*h+t) = truedef Canonical (h : ℕ) (x : ℤ → ℕ → Bool) (p : ℤ) : Prop := x p (h-1) = true ∧ x p (3*h-1) = true ∧ x p (2*h-1) = falsevariable {h : ℕ} {x : ℤ → ℕ → Bool}lemma Geometry.childZ (M : Geometry h x) (p : ℤ) (a : ℕ) (ha : a < 2*h) (hc : x p (2*h+a) = true) : x p (14*h+a) = true := by have hh := (M.parent6 p (2*h+a) (by omega)).2 (by omega) hc convert hh using 1 <;> congr 1 <;> omegalemma Geometry.fullRetained (M : Geometry h x) {p : ℤ} (hp : Active h x p) : ∀ a < h, x p a = true ∧ x p (15*h+a) = true := by obtain ⟨t,ht,hA,hB⟩ := hp exact cycle_power_eight_block_active_retained_halves h x M.parent7 (fun p => ⟨M.lowMono p,M.highMono p⟩) p t ht hA hBlemma Geometry.sep (M : Geometry h x) {p r : ℤ} (hpr : p < r) (hp : Active h x p) (hr : Active h x r) : (h : ℤ) ≤ r-p := by obtain ⟨t,ht,hpA,hpB⟩ := hp obtain ⟨u,hu,hrA,hrB⟩ := hr let d := (r-p).toNat have hd : r=p+(d : ℤ) := by dsimp [d]; omega have hs := cycle_power_eight_block_active_root_separation h M.pos x M.parent7 (fun p => ⟨M.lowMono p,M.highMono p⟩) M.exact15 p d t u (by dsimp [d]; omega) ht hu hpA hpB (by simpa only [← hd] using hrA) (by simpa only [← hd] using hrB) omegalemma Geometry.own6 (M : Geometry h x) (p r : ℤ) (a b : ℕ) (ha : a < 4*h) (hb : b < 4*h) (he : p+(a : ℤ)=r+(b : ℤ)) (hpa : x p a = true) (hpa' : x p (a+12*h) = true) (hrb : x r b = true) (hrb' : x r (b+12*h) = true) : p=r := by have hex : ∀ v : ℤ, (range (4*h)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+16*h-4*h)).toNat) = 1 := by intro v have hi (a : ℕ) : a+16*h-4*h=a+12*h := by omega simpa only [hi] using M.exact6 v have hu := cycle_power_exact_pair_unique (16*h) (4*h) x hex (p+(a : ℤ)) a b ha hb (by simpa using hpa) (by simpa only [add_sub_cancel_right,show a+16*h-4*h=a+12*h by omega] using hpa') (by convert hrb using 1 <;> congr 1 <;> omega) (by convert hrb' using 1 <;> congr 1 <;> omega) omegalemma Geometry.own7 (M : Geometry h x) (p r : ℤ) (a b : ℕ) (ha : a < 2*h) (hb : b < 2*h) (he : p+(a : ℤ)=r+(b : ℤ)) (hpa : x p a = true) (hpa' : x p (a+14*h) = true) (hrb : x r b = true) (hrb' : x r (b+14*h) = true) : p=r := by have hex : ∀ v : ℤ, (range (2*h)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+16*h-2*h)).toNat) = 1 := by intro v have hi (a : ℕ) : a+16*h-2*h=a+14*h := by omega simpa only [hi] using M.exact7 v have hu := cycle_power_exact_pair_unique (16*h) (2*h) x hex (p+(a : ℤ)) a b ha hb (by simpa using hpa) (by simpa only [add_sub_cancel_right,show a+16*h-2*h=a+14*h by omega] using hpa') (by convert hrb using 1 <;> congr 1 <;> omega) (by convert hrb' using 1 <;> congr 1 <;> omega) omegalemma Geometry.grid (M : Geometry h x) (p r : ℤ) (hr : Active h x r) (h0 : Active h x p) (h1 : Active h x (p-(h : ℤ))) (h2 : Active h x (p-(2*h : ℕ))) (hl : p-(3*h : ℕ) < r) (hu : r < p+(h : ℤ)) : r=p ∨ r=p-(h : ℤ) ∨ r=p-(2*h : ℕ) := by have cmp (a : ℤ) (ha : Active h x a) : r=a ∨ r+(h : ℤ) ≤ a ∨ a+(h : ℤ) ≤ r := by rcases lt_trichotomy r a with hlt | he | hgt · have hs := M.sep hlt hr ha omega · exact Or.inl he · have hs := M.sep hgt ha hr omega have hc0 := cmp p h0 have hc1 := cmp (p-(h : ℤ)) h1 have hc2 := cmp (p-(2*h : ℕ)) h2 push_cast at * omegalemma Geometry.cover13Active (M : Geometry h x) (v : ℤ) : ∃ a < 3*h, x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+13*h) = true ∧ Active h x (v-(a : ℤ)) := by obtain ⟨a,ha,hA,hB⟩ := M.cover (13*h) (by have := M.pos; omega) (by have := M.pos; omega) v have ha3 : a < 3*h := by omega refine ⟨a,ha3,hA,hB,?_⟩ let p := v-(a : ℤ) by_cases ha1 : a < h · have hh : x p (h+a) = true := by apply (M.parent6 p (h+a) (by omega)).1 (by omega) convert hB using 1 <;> congr 1 <;> omega have hz := (M.parent7 p (h+a) (by omega)).2 (by omega) hh exact ⟨h+a,by omega,hh,by convert hz using 1 <;> congr 1 <;> omega⟩ · by_cases ha2 : a < 2*h · refine ⟨a,ha2,hA,?_⟩ apply M.highMono p (a+13*h) (14*h+a) (by omega) (by omega) (by omega) exact hB · let b := a-2*h have hb : b < h := by dsimp [b]; omega have hc : x p (2*h+b) = true := by convert hA using 1 <;> congr 1 <;> dsimp [b] <;> omega have hz := M.childZ p b (by omega) hc have ha' := (M.parent7 p b (by omega)).1 hb (by convert hz using 1 <;> congr 1 <;> omega) exact ⟨b,by omega,ha',hz⟩lemma Geometry.canonicalActive (M : Geometry h x) {p : ℤ} (hp : Canonical h x p) : Active h x p := by have hc : x p (2*h+(h-1)) = true := by convert hp.2.1 using 1 <;> congr 1 <;> have := M.pos <;> omega exact ⟨h-1,by have := M.pos; omega,hp.1,M.childZ p (h-1) (by have := M.pos; omega) hc⟩lemma Geometry.missLast (M : Geometry h x) {p : ℤ} {a : ℕ} (ha : a < 2*h) (hm : x p a = false) : x p (2*h-1) = false := by apply Bool.eq_false_iff.mpr intro hc have hh := M.lowMono p a (2*h-1) (by omega) (by have := M.pos; omega) hc rw [hm] at hh contradictionlemma Geometry.maxChildOfThree (M : Geometry h x) (p : ℤ) (h0 : Active h x p) (h1 : Active h x (p-(h : ℤ))) (h2 : Active h x (p-(2*h : ℕ))) (m0 : x p (2*h-1) = false) (m1 : x (p-(h : ℤ)) (2*h-1) = false) (m2 : x (p-(2*h : ℕ)) (2*h-1) = false) : Canonical h x (p-(2*h : ℕ)) := by obtain ⟨a,ha,hA,hB,hact⟩ := M.cover13Active (p+(h : ℤ)-1) have hg := M.grid p (p+(h : ℤ)-1-(a : ℤ)) hact h0 h1 h2 (by have := M.pos; omega) (by omega) rcases hg with he | he | he · have hh : x p (2*h-1) = true := by apply (M.parent6 p (2*h-1) (by have := M.pos; omega)).1 (by have := M.pos; omega) convert hB using 1 <;> congr 1 <;> have := M.pos <;> omega rw [m0] at hh contradiction · have hh : x (p-(h : ℤ)) (2*h-1) = true := by convert hA using 1 <;> congr 1 <;> omega rw [m1] at hh contradiction · refine ⟨(M.fullRetained h2 (h-1) (by have := M.pos; omega)).1,?_,m2⟩ convert hA using 1 <;> congr 1 <;> omegalemma Geometry.backward (M : Geometry h x) (p : ℤ) (h0 : Canonical h x p) (h1 : Canonical h x (p-(h : ℤ))) (h2 : Canonical h x (p-(2*h : ℕ))) : Canonical h x (p-(3*h : ℕ)) := by obtain ⟨a,ha,hA,hB,hact⟩ := M.cover13Active (p-1) have cmp (z : ℤ) (hz : Active h x z) : p-1-(a : ℤ)=z ∨ p-1-(a : ℤ)+(h : ℤ) ≤ z ∨ z+(h : ℤ) ≤ p-1-(a : ℤ) := by rcases lt_trichotomy (p-1-(a : ℤ)) z with hl | he | hr · have hs := M.sep hl hact hz omega · exact Or.inl he · have hs := M.sep hr hz hact omega have c1 := cmp (p-(h : ℤ)) (M.canonicalActive h1) have c2 := cmp (p-(2*h : ℕ)) (M.canonicalActive h2) have he : p-1-(a : ℤ)=p-(h : ℤ) ∨ p-1-(a : ℤ)=p-(2*h : ℕ) ∨ p-1-(a : ℤ)=p-(3*h : ℕ) := by push_cast at *; have := M.pos; omega rcases he with he | he | he · have hh : x (p-(h : ℤ)) (2*h-1) = true := by apply (M.parent6 (p-(h : ℤ)) (2*h-1) (by have := M.pos; omega)).1 (by have := M.pos; omega) convert hB using 1 <;> congr 1 <;> have := M.pos <;> omega rw [h1.2.2] at hh contradiction · have hh : x (p-(2*h : ℕ)) (2*h-1) = true := by convert hA using 1 <;> congr 1 <;> have := M.pos <;> omega rw [h2.2.2] at hh contradiction · have hc : x (p-(3*h : ℕ)) (3*h-1) = true := by convert hA using 1 <;> congr 1 <;> have := M.pos <;> omega have hc' : x (p-(3*h : ℕ)) (2*h+(h-1)) = true := by convert hc using 1 <;> congr 1 <;> have := M.pos <;> omega have hz := M.childZ (p-(3*h : ℕ)) (h-1) (by have := M.pos; omega) hc' have hlo := (M.parent7 (p-(3*h : ℕ)) (h-1) (by have := M.pos; omega)).1 (by have := M.pos; omega) (by convert hz using 1 <;> congr 1 <;> omega) refine ⟨hlo,hc,?_⟩ apply Bool.eq_false_iff.mpr intro hf have h2c : x (p-(2*h : ℕ)) (2*h+(h-1)) = true := by convert h2.2.1 using 1 <;> congr 1 <;> have := M.pos <;> omega have h2z := M.childZ (p-(2*h : ℕ)) (h-1) (by have := M.pos; omega) h2c have heq := M.own7 (p-(3*h : ℕ)) (p-(2*h : ℕ)) (2*h-1) (h-1) (by have := M.pos; omega) (by have := M.pos; omega) (by omega) hf (by convert (M.ends (p-(3*h : ℕ))).2 using 1 <;> congr 1 <;> have := M.pos <;> omega) h2.1 (by convert h2z using 1 <;> congr 1 <;> omega) have := M.pos omegaend CyclePowerSixteenBlocknamespace CyclePowerSixteenBlockvariable {h : ℕ} {x : ℤ → ℕ → Bool}lemma Geometry.noHighOverlap (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) (p : ℤ) (t s : ℕ) (ht : h ≤ t) (hts : t < s) (hs : s < 2*h) (hA : x p t = true) (hC : x p (2*h+t) = true) (hm : x p s = false) : False := by have aux : ∀ N : ℕ, ∀ (p : ℤ) (t s : ℕ), 2*h-t=N → h ≤ t → t < s → s < 2*h → x p t = true → x p (2*h+t) = true → x p s = false → False := by intro N induction N using Nat.strong_induction_on with | h N ih => intro p t s hN ht hts hs hA hC hm obtain ⟨u,v,hu,hv,htv,hAu,hCu,hMu,hAv,hCv,hMv,heq⟩ := cycle_power_eight_block_double_gap_transfer h t s M.pos hts hs x p M.lowMono M.parent6 M.exact6 M.exact7 M.cover nov (fun p r a b hpr ha hb hpA hpB hrA hrB => M.sep hpr ⟨a,ha,hpA,hpB⟩ ⟨b,hb,hrA,hrB⟩) hA hC hm by_cases he : v=t · have he' := heq he omega · exact ih (2*h-v) (by omega) (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) v (v+s-t) rfl (by omega) (by omega) (by omega) hAv hCv hMv exact aux (2*h-t) p t s rfl ht hts hs hA hC hmlemma Geometry.midChildFalse (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) {p : ℤ} (hp : Canonical h x p) : x p (3*h) = false := by apply Bool.eq_false_iff.mpr intro hc have hc' : x p (2*h+h) = true := by convert hc using 1 <;> congr 1 <;> omega have ha := nov p h (by have := M.pos; omega) hc' by_cases he : h=2*h-1 · rw [he,hp.2.2] at ha contradiction · exact M.noHighOverlap nov p h (2*h-1) le_rfl (by have := M.pos; omega) (by have := M.pos; omega) ha hc' hp.2.2lemma Geometry.canonicalTriple (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) {p : ℤ} (hp : Canonical h x p) : Canonical h x p ∧ Canonical h x (p-(h : ℤ)) ∧ Canonical h x (p-(2*h : ℕ)) := by obtain ⟨u,v,hu,hv,htv,hAu,hCu,hMu,hAv,hCv,hMv,heq⟩ := cycle_power_eight_block_double_gap_transfer h (h-1) (2*h-1) M.pos (by have := M.pos; omega) (by have := M.pos; omega) x p M.lowMono M.parent6 M.exact6 M.exact7 M.cover nov (fun p r a b hpr ha hb hpA hpB hrA hrB => M.sep hpr ⟨a,ha,hpA,hpB⟩ ⟨b,hb,hrA,hrB⟩) hp.1 (by convert hp.2.1 using 1 <;> congr 1 <;> have := M.pos <;> omega) hp.2.2 have hvEq : v=h-1 := by have := M.pos; omega have huEq : u=h-1 := by have hh := heq hvEq; have := M.pos; omega refine ⟨hp,⟨?_,?_,?_⟩,⟨?_,?_,?_⟩⟩ · convert hAu using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hCu using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hMu using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hAv using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hCv using 1 <;> congr 1 <;> have := M.pos <;> omega · convert hMv using 1 <;> congr 1 <;> have := M.pos <;> omegalemma Geometry.canonicalChain (M : Geometry h x) {p : ℤ} (hp : Canonical h x p) (h1 : Canonical h x (p-(h : ℤ))) (h2 : Canonical h x (p-(2*h : ℕ))) : ∀ n : ℕ, Canonical h x (p-(n : ℤ)*(h : ℤ)) := by have aux (n : ℕ) : Canonical h x (p-(n : ℤ)*(h : ℤ)) ∧ Canonical h x (p-((n : ℤ)+1)*(h : ℤ)) ∧ Canonical h x (p-((n : ℤ)+2)*(h : ℤ)) := by induction n with | zero => simpa using And.intro hp (And.intro h1 h2) | succ n ih => have hb := M.backward (p-(n : ℤ)*(h : ℤ)) ih.1 (by convert ih.2.1 using 1 <;> push_cast <;> ring) (by convert ih.2.2 using 1 <;> push_cast <;> ring) refine ⟨?_,?_,?_⟩ · convert ih.2.1 using 1 <;> push_cast <;> ring · convert ih.2.2 using 1 <;> push_cast <;> ring · convert hb using 1 <;> push_cast <;> ring exact fun n => (aux n).1end CyclePowerSixteenBlocknamespace CyclePowerSixteenBlockvariable {h : ℕ} {x : ℤ → ℕ → Bool}lemma Geometry.forceH0 (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) (r : ℤ) (hr : Canonical h x r) (hp : Canonical h x (r+(h : ℤ))) (hv : Canonical h x (r+(4*h : ℕ))) : x r (12*h) = true := by let v : ℤ := r+(4*h : ℕ) let p : ℤ := r+(h : ℤ) obtain ⟨a,ha,hA,hB⟩ := M.cover (12*h-1) (by have := M.pos; omega) (by have := M.pos; omega) v have ha4 : a ≤ 4*h := by have := M.pos; omega let w : ℤ := v-(a : ℤ) by_cases ha0 : a=0 · have hg : x v (12*h-1) = true := by simpa only [ha0,Nat.cast_zero,sub_zero,zero_add] using hB have hc : x v (4*h-1) = true := by apply (M.parent4 v (4*h-1) (by have := M.pos; omega)).1 (by have := M.pos; omega) convert hg using 1 <;> congr 1 <;> have := M.pos <;> omega have hc' : x v (2*h+(2*h-1)) = true := by convert hc using 1 <;> congr 1 <;> have := M.pos <;> omega have hm := nov v (2*h-1) (by have := M.pos; omega) hc' rw [hv.2.2] at hm contradiction · by_cases ha2 : a ≤ 2*h · have hl : x w (a-1) = true := by apply (M.parent6 w (a-1) (by omega)).1 (by omega) convert hB using 1 <;> congr 1 <;> have := M.pos <;> omega have hpZ := M.childZ p (h-1) (by have := M.pos; omega) (by convert hp.2.1 using 1 <;> congr 1 <;> have := M.pos <;> omega) have he := M.own6 w p (a-1) (3*h-1) (by omega) (by have := M.pos; omega) (by dsimp [w,v,p]; have := M.pos; omega) hl (by convert hB using 1 <;> congr 1 <;> have := M.pos <;> omega) hp.2.1 (by convert hpZ using 1 <;> congr 1 <;> have := M.pos <;> omega) dsimp [w,v,p] at he have := M.pos omega · by_cases haEq : a=4*h · have hD : x r (4*h) = true := by convert hA using 1 <;> congr 1 <;> (try dsimp [v]) <;> omega have hh := (M.parent4 r (4*h) (by have := M.pos; omega)).2 le_rfl hD convert hh using 1 <;> congr 1 <;> omega · let b := a-2*h have hb : b < 2*h := by dsimp [b]; omega have hC : x w (2*h+b) = true := by convert hA using 1 <;> congr 1 <;> dsimp [b] <;> omega have hw : Active h x w := ⟨b,hb,nov w b hb hC,M.childZ w b hb hC⟩ have hpAct : Active h x p := M.canonicalActive hp have hew : w=p := by rcases lt_trichotomy w p with hlt | he | hgt · have hs := M.sep hlt hw hpAct dsimp [w,v,p] at hs have := M.pos omega · exact he · have hs := M.sep hgt hpAct hw dsimp [w,v,p] at hs have := M.pos omega dsimp [w,v,p] at hew have hc : x p (3*h) = true := by convert hA using 1 <;> congr 1 <;> (try dsimp [v,p]) <;> omega rw [M.midChildFalse nov hp] at hc contradictionlemma Geometry.cornerFromH0 (M : Geometry h x) (v : ℤ) (h0 : Canonical h x v) (h1 : Canonical h x (v-(h : ℤ))) (h2 : Canonical h x (v-(2*h : ℕ))) (hH : x v (12*h) = true) (hHnext : x (v+(h : ℤ)) (12*h) = true) : x (v-(h : ℤ)) h = true ∧ x (v-(h : ℤ)) (14*h) = true := by obtain ⟨a,ha,hA,hB,hact⟩ := M.cover13Active v have hg := M.grid v (v-(a : ℤ)) hact (M.canonicalActive h0) (M.canonicalActive h1) (M.canonicalActive h2) (by omega) (by have := M.pos; omega) rcases hg with he | he | he · have hh : x v (h+12*h) = true := by convert hB using 1 <;> congr 1 <;> omega have hl := (M.parent6 v h (by have := M.pos; omega)).1 (by have := M.pos; omega) hh have heq := M.own6 v (v+(h : ℤ)) h 0 (by have := M.pos; omega) (by have := M.pos; omega) (by omega) hl hh (M.ends _).1 (by simpa using hHnext) have := M.pos omega · constructor · convert hA using 1 <;> congr 1 <;> omega · convert hB using 1 <;> congr 1 <;> omega · have hc : x (v-(2*h : ℕ)) (2*h+0) = true := by convert hA using 1 <;> congr 1 <;> omega have hz := M.childZ (v-(2*h : ℕ)) 0 (by have := M.pos; omega) hc have heq := M.own6 (v-(2*h : ℕ)) v (2*h) 0 (by have := M.pos; omega) (by have := M.pos; omega) (by omega) (by simpa using hc) (by convert hz using 1 <;> congr 1 <;> omega) (M.ends v).1 (by simpa using hH) have := M.pos omegalemma Geometry.chainImpossible (M : Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) (p : ℤ) (chain : ∀ n : ℕ, Canonical h x (p-(n : ℤ)*(h : ℤ))) : False := by have ch (n : ℕ) : Canonical h x (p-(n : ℤ)*(h : ℤ)) := chain n have hf (j : ℕ) (hj : 4 ≤ j) : x (p-(j : ℤ)*(h : ℤ)) (12*h) = true := by apply M.forceH0 nov (p-(j : ℤ)*(h : ℤ)) (ch j) · convert ch (j-1) using 1 <;> push_cast [Nat.cast_sub (by omega : 1 ≤ j)] <;> ring · convert ch (j-4) using 1 <;> push_cast [Nat.cast_sub hj] <;> ring have hc5 := M.cornerFromH0 (p-5*(h : ℤ)) (by simpa using ch 5) (by convert ch 6 using 1 <;> push_cast <;> ring) (by convert ch 7 using 1 <;> push_cast <;> ring) (by simpa using hf 5 (by omega)) (by convert hf 4 (by omega) using 1 <;> push_cast <;> ring) have hc6 := M.cornerFromH0 (p-6*(h : ℤ)) (by simpa using ch 6) (by convert ch 7 using 1 <;> push_cast <;> ring) (by convert ch 8 using 1 <;> push_cast <;> ring) (by simpa using hf 6 (by omega)) (by convert hf 5 (by omega) using 1 <;> push_cast <;> ring) have hz : x (p-6*(h : ℤ)-(h : ℤ)) (h+14*h) = true := by apply M.highMono _ (14*h) (h+14*h) le_rfl (by omega) (by have := M.pos; omega) exact hc6.2 have heq := M.own7 (p-6*(h : ℤ)-(h : ℤ)) (p-5*(h : ℤ)-(h : ℤ)) h 0 (by have := M.pos; omega) (by have := M.pos; omega) (by ring) hc6.1 hz (M.ends _).1 (by simpa using hc5.2) have := M.pos omegaend CyclePowerSixteenBlocktheorem cycle_power_sixteen_block_no_vertical_overlap (h : ℕ) (x : ℤ → ℕ → Bool) (M : CyclePowerSixteenBlock.Geometry h x) (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true) (p : ℤ) (t s : ℕ) (hts : t < s) (hsq : s < 2*h) (hA : x p t = true) (hC : x p (2*h+t) = true) (hm : x p s = false) : False := by obtain ⟨r,a,b,ha,hb,hbq,hA0,hC0,hm0,hA1,hC1,hm1,hA2,hC2,hm2⟩ := cycle_power_eight_block_overlap_stabilizes h M.pos x M.lowMono M.parent6 M.exact6 M.exact7 M.cover nov (fun p r a b hpr ha hb hpA hpB hrA hrB => M.sep hpr ⟨a,ha,hpA,hpB⟩ ⟨b,hb,hrA,hrB⟩) p t s hts hsq hA hC hm have a0 : CyclePowerSixteenBlock.Active h x r := ⟨a,by omega,hA0,M.childZ r a (by omega) hC0⟩ have a1 : CyclePowerSixteenBlock.Active h x (r-(h : ℤ)) := ⟨b-h,by omega,hA1,M.childZ _ (b-h) (by omega) hC1⟩ have a2 : CyclePowerSixteenBlock.Active h x (r-(2*h : ℕ)) := ⟨a,by omega,hA2,M.childZ _ a (by omega) hC2⟩ have cc := M.maxChildOfThree r a0 a1 a2 (M.missLast hbq hm0) (M.missLast (by omega) hm1) (M.missLast hbq hm2) obtain ⟨c0,c1,c2⟩ := M.canonicalTriple nov cc exact M.chainImpossible nov (r-(2*h : ℕ)) (M.canonicalChain c0 c1 c2)