cycle_power_fifteen_model_alternating_endpoint
At exponent 4 (bandwidth 15) every tight, exactly dyadically covered, fully covered integer Boolean class model with five active classes per vertex has alternating bit 1, and every class without bit 1 has no inner bit.
Statement
theorem cycle_power_fifteen_model_alternating_endpoint (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight 4 (x p) = (Finset.range (2^4)).sum (fun a => (x p a).toNat)) (hexact : ∀ j < 4, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^4-2^j)).toNat) = 1) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^4 → ∀ v : ℤ, ∃ a : ℕ, a < 2^4-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (hcount : ∀ v : ℤ, (Finset.range (2^4)).sum (fun a => (x (v-(a : ℤ)) a).toNat) = 4+1) : (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧ (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^4 - 1 → x p j = false)
- Source
- RT-1 / OP-205 (arXiv:2610.15635, Theorems 1.3-1.4: eq(C_n^k) for k+1 = 2^m, n even, (k+1) not dividing n). Session 2026-11-09: folding offsets modulo 2^t (experiment 19407).
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteenIn the layer-free tight-class model for bandwidth fifteen, the first inner position belongs to a class exactly when the penultimate…
- cycle_power_fifteen_model_no_islandThe no-island class shape at exponent m = 4 (bandwidth 15), in the exact form the conditional theorem…
- cycle_power_dyadic_boundary_pairing_alternatesIn an exact dyadic Boolean class model with exponent at least two, equality of the two boundary bits in every class forces the first inner…
- cycle_power_dyadic_tight_class_parentEquality in the dyadic class weight bound forces all rooted-tree parent implications at every smaller dyadic scale, uniformly in the arc…
- 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.
- Used by 1
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_fold_countConditional reduction of OP-205 to a single count identity plus a middle-bit lemma: if for every t ≥ 4 every model at exponent t+1 has…
The proof, explained
The theorem proves that any tight, dyadically exact, fully covered integer Boolean class model of bandwidth 15 with 5 active classes per vertex has alternating bit 1 along the integer line (x (p + 1) 1 = ¬ x p 1) and that any class with x p 1 = false has all internal bits false (x p j = false for 0 < j < 15). The proof first shows the boundary bits x p 0 and x p 15 are identically true, then verifies the dyadic parent relations, the inner active class count of 3, and dyadic exact coverage at distances 8, 12, 14. These enable cycle_power_fifteen_tight_type_sequence_one_iff_fourteen, establishing x p 1 = x p 14. In turn, cycle_power_dyadic_boundary_pairing_alternates proves the alternating bit 1 property, and the 'no island' lemma cycle_power_fifteen_model_no_island ensures that no intermediate bit can be true when the boundary bits 1 and 14 are false.
Every class has active boundary bits: x p 0 = true and x p 15 = true for all p.
Specializing the exact dyadic covering hypothesis hexact at scale j = 0 for vertex v produces a single-term sum of (x v 0 && x v 15) = 1. This implies that both x v 0 and x v 15 are true for every class.
have hends : ∀ v : ℤ, x v 0 = true ∧ x v 15 = true := by intro v have h := hexact 0 (by norm_num) v simp at h exact h have h0 : ∀ p, x p 0 = true := fun p => (hends p).1 have h15 : ∀ p, x p 15 = true := fun p => (hends p).2
Active bits satisfy all 14 parent-child implication edges of the dyadic tree in every class.
For each edge (u, v) in the explicit set of 14 pairs, if bit u is active in class p, then bit v must also be active. When v is 0 or 15, the claim follows from the boundary bits being unconditionally true. For all other pairs, the implication is a dyadic parent relation established by cycle_power_dyadic_tight_class_parent at dyadic levels j = 2 and j = 3.
uses
cycle_power_dyadic_tight_class_parent,Finset.mem_insert,Finset.mem_singletonhave hparent : ∀ p : ℤ, ∀ e ∈ ({(1,15),(2,14),(3,15),(4,12),(5,13),(6,14),(7,15), (8,0),(9,1),(10,2),(11,3),(12,0),(13,1),(14,0)} : Finset (ℕ × ℕ)), x p e.1 = true → x p e.2 = true := by intro p e he h have P2 := cycle_power_dyadic_tight_class_parent 4 2 (by norm_num) (by norm_num) (x p) (htight p) have P3 := cycle_power_dyadic_tight_class_parent 4 3 (by norm_num) (by norm_num) (x p) (htight p) simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl · exact h15 p · exact (P2 2 (by norm_num)).2 (by norm_num) h · exact h15 p · exact (P3 4 (by norm_num)).2 (by norm_num) h · exact (P3 5 (by norm_num)).2 (by norm_num) h · exact (P3 6 (by norm_num)).2 (by norm_num) h · exact h15 p · exact h0 p · exact (P3 1 (by norm_num)).1 (by norm_num) h · exact (P3 2 (by norm_num)).1 (by norm_num) h · exact (P3 3 (by norm_num)).1 (by norm_num) h · exact h0 p · exact (P2 1 (by norm_num)).1 (by norm_num) h · exact h0 p
For each vertex, the sum of its 14 internal bits equals 3.
By hypothesis hcount, the total number of active classes covering any vertex v across all 16 bits is 5. Splitting off the boundary terms at a = 0 (which is x v 0 = 1) and a = 15 (which is x (v - 15) 15 = 1) using Finset.sum_range_succ and Finset.sum_range_succ', linear arithmetic confirms that the sum over the 14 internal bits j ∈ {1, ..., 14} is 5 - 1 - 1 = 3.
uses
Finset.sum_range_succ,Finset.sum_range_succ'have hcount' : ∀ v : ℤ, (Finset.range 14).sum (fun j => (x (v - ((j + 1 : ℕ) : ℤ)) (j + 1)).toNat) = 3 := by intro v have h := hcount v rw [show (2:ℕ)^4 = 14 + 1 + 1 by norm_num, Finset.sum_range_succ, Finset.sum_range_succ'] at h have e0 : (x (v - ((0 : ℕ) : ℤ)) 0).toNat = 1 := by rw [h0]; rfl have e15 : (x (v - ((14 + 1 : ℕ) : ℤ)) (14 + 1)).toNat = 1 := by rw [h15]; rfl omega
Exact covering holds at distances d ∈ {8, 12, 14}.
For each distance d ∈ {8, 12, 14}, the exact covering sum is rewritten to match the dyadic covering hypothesis hexact at scales j = 3, 2, 1 respectively, because 16 - d = 2^j and a + 2^4 - 2^j = a + d.
uses
Finset.mem_insert,Finset.mem_singleton,Eq.trans,Finset.sum_congr,Nat.reducePowhave hexact' : ∀ d ∈ ({8,12,14} : Finset ℕ), ∀ v : ℤ, (Finset.range (16 - d)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + d)).toNat) = 1 := by intro d hd v simp only [Finset.mem_insert, Finset.mem_singleton] at hd rcases hd with rfl | rfl | rfl · rw [show 16 - 8 = 2^3 by norm_num] refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 3 (by norm_num) v) intro a _ rw [show a + 2^4 - 2^3 = a + 8 by simp only [Nat.reducePow]; omega] · rw [show 16 - 12 = 2^2 by norm_num] refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 2 (by norm_num) v) intro a _ rw [show a + 2^4 - 2^2 = a + 12 by simp only [Nat.reducePow]; omega] · rw [show 16 - 14 = 2^1 by norm_num] refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 1 (by norm_num) v) intro a _ rw [show a + 2^4 - 2^1 = a + 14 by simp only [Nat.reducePow]; omega]
The covering condition holds for all distances 1 ≤ d < 15.
Given 1 ≤ d < 15, the covering hypothesis hcover immediately provides a witness a < 16 - d since 2^4 = 16.
uses
Nat.reducePowhave hcover' : ∀ (d : ℕ), 1 ≤ d → d < 15 → ∀ v : ℤ, ∃ a < 16 - d, x (v - (a : ℤ)) a = true ∧ x (v - (a : ℤ)) (a + d) = true := by intro d hd1 hd v obtain ⟨a, ha, h1, h2⟩ := hcover d hd1 (by simp only [Nat.reducePow]; omega) v exact ⟨a, by simp only [Nat.reducePow] at ha; omega, h1, h2⟩
In every class p, bit 1 is active if and only if bit 14 is active: x p 1 = x p 14.
Applying the classification theorem cycle_power_fifteen_tight_type_sequence_one_iff_fourteen with the established boundary conditions, parent graph, inner sum of 3, exact covering at {8, 12, 14}, and general covering condition yields x p 1 = x p 14 for all p.
uses
cycle_power_fifteen_tight_type_sequence_one_iff_fourteenhave h114 := cycle_power_fifteen_tight_type_sequence_one_iff_fourteen x h0 h15 hparent hcount' hexact' hcover'Bit 1 alternates between consecutive classes: x (p + 1) 1 = ¬ x p 1 for all p.
Applying cycle_power_dyadic_boundary_pairing_alternates at exponent m = 4, the exact dyadic coverage together with the boundary pairing x p 1 = x p 14 (noting 2^4 - 2 = 14) implies that bit 1 strictly alternates from one class to the next along the integer line.
uses
cycle_power_dyadic_boundary_pairing_alternatesrefine ⟨cycle_power_dyadic_boundary_pairing_alternates 4 (by norm_num) x hexact ?_, ?_⟩ · intro p simpa using h114 p
If bit 1 is false in class p, then all internal bits j ∈ {1, ..., 14} are false in class p.
Suppose for contradiction that x p j = true for some 0 < j < 15 when x p 1 = false. Since x p 1 = x p 14, we also have x p 14 = false, which implies j ≠ 1 and j ≠ 14, hence 1 < j < 14. The 'no island' property cycle_power_fifteen_model_no_island applied with a = 1, b = j, and c = 14 states that x p 1 = false and x p j = true forces x p 14 = true, contradicting x p 14 = false.
uses
cycle_power_fifteen_model_no_island,Nat.reducePow· intro p hp j hj1 hj2 cases hx : x p j with | false => rfl | true => exfalso have h14 : x p 14 = false := by rw [← h114 p]; exact hp have hj3 : j ≠ 1 := fun e => by rw [e, hp] at hx; exact absurd hx (by simp) have hj4 : j ≠ 14 := fun e => by rw [e, h14] at hx; exact absurd hx (by simp) have := cycle_power_fifteen_model_no_island x htight hexact hcover hcount p 1 j 14 (by omega) (by simp only [Nat.reducePow] at hj2; omega) (by norm_num) hp hx rw [h14] at this exact absurd this (by simp)
Eq.trans- Transitivity of equality: if a = b and b = c, then a = c.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their terms agree on all elements.
Finset.sum_range_succ- Splits a sum over range (n + 1) into the sum over range n plus the term at n.
Finset.sum_range_succ'- Splits a sum over range (n + 1) into the term at 0 plus the shifted sum of f (k + 1) over range n.
Nat.reducePow- Simplification procedure that computes natural number exponentiation.
cycle_power_dyadic_boundary_pairing_alternates- In an exact dyadic covering model where the boundary bits pair up (x p 1 = x p (2^m - 2)), bit 1 strictly alternates between adjacent classes: x (p + 1) 1 = ¬ x p 1.
cycle_power_dyadic_tight_class_parent- In a tight dyadic class, if an active bit belongs to a dyadic interval, its parent bit in the dyadic hierarchy must also be active.
cycle_power_fifteen_model_no_island- In a valid model of exponent 4, an active bit cannot be strictly flanked by inactive ones: if a < b < c, x p a = false, and x p b = true, then x p c must be true.
cycle_power_fifteen_tight_type_sequence_one_iff_fourteen- Under boundary, tree-parent, inner-sum, exact dyadic coverage, and general coverage conditions at bandwidth 15, bit 1 is active if and only if bit 14 is active in every class: x p 1 = x p 14.
- The arithmetic peeling off the endpoints in step 3 to establish that the inner sum equals 3 is discharged by the `omega` decision procedure. Step 4 explicitly matches dyadic indices 2^j with the set {8, 12, 14} via congruence and rewriting.
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_fifteen_model_alternating_endpoint (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight 4 (x p) = (Finset.range (2^4)).sum (fun a => (x p a).toNat)) (hexact : ∀ j < 4, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^4-2^j)).toNat) = 1) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^4 → ∀ v : ℤ, ∃ a : ℕ, a < 2^4-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (hcount : ∀ v : ℤ, (Finset.range (2^4)).sum (fun a => (x (v-(a : ℤ)) a).toNat) = 4+1) : (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧ (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^4 - 1 → x p j = false) := by have hends : ∀ v : ℤ, x v 0 = true ∧ x v 15 = true := by intro v have h := hexact 0 (by norm_num) v simp at h exact h have h0 : ∀ p, x p 0 = true := fun p => (hends p).1 have h15 : ∀ p, x p 15 = true := fun p => (hends p).2 have hparent : ∀ p : ℤ, ∀ e ∈ ({(1,15),(2,14),(3,15),(4,12),(5,13),(6,14),(7,15), (8,0),(9,1),(10,2),(11,3),(12,0),(13,1),(14,0)} : Finset (ℕ × ℕ)), x p e.1 = true → x p e.2 = true := by intro p e he h have P2 := cycle_power_dyadic_tight_class_parent 4 2 (by norm_num) (by norm_num) (x p) (htight p) have P3 := cycle_power_dyadic_tight_class_parent 4 3 (by norm_num) (by norm_num) (x p) (htight p) simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl · exact h15 p · exact (P2 2 (by norm_num)).2 (by norm_num) h · exact h15 p · exact (P3 4 (by norm_num)).2 (by norm_num) h · exact (P3 5 (by norm_num)).2 (by norm_num) h · exact (P3 6 (by norm_num)).2 (by norm_num) h · exact h15 p · exact h0 p · exact (P3 1 (by norm_num)).1 (by norm_num) h · exact (P3 2 (by norm_num)).1 (by norm_num) h · exact (P3 3 (by norm_num)).1 (by norm_num) h · exact h0 p · exact (P2 1 (by norm_num)).1 (by norm_num) h · exact h0 p have hcount' : ∀ v : ℤ, (Finset.range 14).sum (fun j => (x (v - ((j + 1 : ℕ) : ℤ)) (j + 1)).toNat) = 3 := by intro v have h := hcount v rw [show (2:ℕ)^4 = 14 + 1 + 1 by norm_num, Finset.sum_range_succ, Finset.sum_range_succ'] at h have e0 : (x (v - ((0 : ℕ) : ℤ)) 0).toNat = 1 := by rw [h0]; rfl have e15 : (x (v - ((14 + 1 : ℕ) : ℤ)) (14 + 1)).toNat = 1 := by rw [h15]; rfl omega have hexact' : ∀ d ∈ ({8,12,14} : Finset ℕ), ∀ v : ℤ, (Finset.range (16 - d)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + d)).toNat) = 1 := by intro d hd v simp only [Finset.mem_insert, Finset.mem_singleton] at hd rcases hd with rfl | rfl | rfl · rw [show 16 - 8 = 2^3 by norm_num] refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 3 (by norm_num) v) intro a _ rw [show a + 2^4 - 2^3 = a + 8 by simp only [Nat.reducePow]; omega] · rw [show 16 - 12 = 2^2 by norm_num] refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 2 (by norm_num) v) intro a _ rw [show a + 2^4 - 2^2 = a + 12 by simp only [Nat.reducePow]; omega] · rw [show 16 - 14 = 2^1 by norm_num] refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 1 (by norm_num) v) intro a _ rw [show a + 2^4 - 2^1 = a + 14 by simp only [Nat.reducePow]; omega] have hcover' : ∀ (d : ℕ), 1 ≤ d → d < 15 → ∀ v : ℤ, ∃ a < 16 - d, x (v - (a : ℤ)) a = true ∧ x (v - (a : ℤ)) (a + d) = true := by intro d hd1 hd v obtain ⟨a, ha, h1, h2⟩ := hcover d hd1 (by simp only [Nat.reducePow]; omega) v exact ⟨a, by simp only [Nat.reducePow] at ha; omega, h1, h2⟩ have h114 := cycle_power_fifteen_tight_type_sequence_one_iff_fourteen x h0 h15 hparent hcount' hexact' hcover' refine ⟨cycle_power_dyadic_boundary_pairing_alternates 4 (by norm_num) x hexact ?_, ?_⟩ · intro p simpa using h114 p · intro p hp j hj1 hj2 cases hx : x p j with | false => rfl | true => exfalso have h14 : x p 14 = false := by rw [← h114 p]; exact hp have hj3 : j ≠ 1 := fun e => by rw [e, hp] at hx; exact absurd hx (by simp) have hj4 : j ≠ 14 := fun e => by rw [e, h14] at hx; exact absurd hx (by simp) have := cycle_power_fifteen_model_no_island x htight hexact hcover hcount p 1 j 14 (by omega) (by simp only [Nat.reducePow] at hj2; omega) (by norm_num) hp hx rw [h14] at this exact absurd this (by simp)