cycle_power_fifteen_endpoint_layer_period_sixteen
For sixteen-position cyclic class types alternating between endpoint-only types {0,15} and types with equal consecutive membership bits, assume every vertex is active in exactly five classes, the active classes have distinct labels in Fin 5, and every class contains its start. Then the label at every endpoint-only start repeats after sixteen positions. Classification of actual graph-cover classes and label periods at other starts are not conclusions of this helper.
Statement
theorem cycle_power_fifteen_endpoint_layer_period_sixteen (n : ℕ) [NeZero n] (σ : ZMod n → Fin 5) (x : ZMod n → Fin 16 → Bool) (P : ZMod n → Bool) (halt : ∀ p, P (p + 1) = !(P p)) (hend : ∀ p, P p = true → ∀ j : Fin 16, x p j = true ↔ j.val = 0 ∨ j.val = 15) (hpair : ∀ p, P p = false → ∀ a : Fin 8, x p ⟨2 * a.val, by omega⟩ = x p ⟨2 * a.val + 1, by omega⟩) (hzero : ∀ p, x p 0 = true) (hcount : ∀ v : ZMod n, (Finset.univ.filter (fun j : Fin 16 => x (v - (j.val : ZMod n)) j = true)).card = 5) (hsep : ∀ (p q : ZMod n) (j k : Fin 16), p + (j.val : ZMod n) = q + (k.val : ZMod n) → x p j = true → x q k = true → σ p = σ q → j = k) : ∀ p, P p = true → σ (p + 16) = σ p
- Source
- Conditional helper for RT-1 / OP-205, arXiv:2610.15635, the unresolved k=15 case following Theorem 1.3. The slot-exchange route is the latest RT-1 journal next step and was motivated by experiment 4369. It assumes endpoint/paired alternation, exact active counts and layer separation; it does not prove the six-type classification or a new graph covering bound.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof shows that the class label σ repeats after 16 positions at any endpoint-only start p with P(p) = true. First, the alternation hypothesis implies that P has period 2, so the value of P(p + d) is governed entirely by the parity of d. Next, at vertex v = p + 15, exactly five classes are active with pairwise distinct labels in Fin 5, so by a cardinality argument their labels exhaust Fin 5 and some active offset j has label σ(v - j) = σ(p + 16). Finally, if j = 15 then v - 15 = p and the labels match immediately; if j < 15, parity forces j to be even and P(v - j) = false, so bit pairing makes offset k = j + 1 active at vertex p + 16, which contradicts the separation hypothesis since k ≥ 1 but must equal offset 0.
In the paired-bit hypothesis hpair, the offsets 2a and 2a + 1 are valid indices in Fin 16 for any a : Fin 8.
Linear integer arithmetic (omega) proves that if a < 8, then 2a < 16 and 2a + 1 < 16, establishing the range bounds needed to form the indices of Fin 16 in the statement of hpair.
x p ⟨2 * a.val, by omega⟩ = x p ⟨2 * a.val + 1, by omega⟩)
The predicate P has period 2, and more generally P(q + 2a) = P(q) for all q ∈ ℤ/nℤ and a ∈ ℕ.
Using classical logic, shifting by 2 negates the boolean value twice: P(q + 2) = P((q + 1) + 1) = ¬P(q + 1) = ¬(¬P(q)) = P(q), using the alternation hypothesis (halt). By induction on a, shifting by any even offset 2a decomposes into a successive shifts by 2, preserving the value of P.
classical have htwo : ∀ q, P (q + 2) = P q := by intro q calc P (q + 2) = P ((q + 1) + 1) := by congr 1; ring _ = !P (q + 1) := halt _ _ = P q := by rw [halt]; simp have heven : ∀ (q : ZMod n) (a : ℕ), P (q + ((2 * a : ℕ) : ZMod n)) = P q := by intro q a induction a with | zero => simp | succ a ih => calc P (q + ((2 * (a + 1) : ℕ) : ZMod n)) = P ((q + ((2 * a : ℕ) : ZMod n)) + 2) := by congr 1; push_cast; ring _ = P (q + ((2 * a : ℕ) : ZMod n)) := htwo _ _ = P q := ih
For a vertex p with P(p) = true, P(p + d) is true when d is even and false when d is odd.
We fix p such that P(p) = true (hp). For any natural offset d, we split into cases based on the parity of d: if d is even, d = 2(d/2), so p + d = p + 2(d/2) and P(p + d) = P(p) = true by the even-shift invariance lemma heven. If d is odd, d = 2(d/2) + 1, so p + d = (p + 1) + 2(d/2); applying heven from p + 1 and then the alternation hypothesis (halt) yields P(p + d) = P(p + 1) = ¬P(p) = false. The equality between d and 2(d/2) + 1 in ℤ/nℤ is transported via congrArg.
uses
congrArgintro p hp have hoff : ∀ d : ℕ, P (p + (d : ZMod n)) = if d % 2 = 0 then true else false := by intro d by_cases hd : d % 2 = 0 · have he : 2 * (d / 2) = d := by omega simpa [he, hp, hd] using heven p (d / 2) · have he : 2 * (d / 2) + 1 = d := by omega have hq : p + (d : ZMod n) = (p + 1) + ((2 * (d / 2) : ℕ) : ZMod n) := by have hc : ((2 * (d / 2) + 1 : ℕ) : ZMod n) = (d : ZMod n) := by exact congrArg (fun z : ℕ => (z : ZMod n)) he calc p + (d : ZMod n) = p + ((2 * (d / 2) + 1 : ℕ) : ZMod n) := congrArg (fun z : ZMod n => p + z) hc.symm _ = _ := by push_cast; ring rw [hq, heven, halt, hp] simp [hd]
At vertex v = p + 15, exactly five classes are active, and the labeling function f : j ↦ σ(v - j) is injective on the set A of active offsets.
Let v = p + 15, and let A ⊆ Fin 16 be the set of offsets j such that class v - j is active at position j (meaning x(v - j, j) = true). By the vertex degree hypothesis (hcount), |A| = 5. Define f(j) = σ(v - j). If two active offsets j, k ∈ A share the same label f(j) = f(k), then because (v - j) + j = (v - k) + k = v, the separation hypothesis (hsep) forces j = k. Thus f is injective on A.
uses
Finset.mem_filter.mplet v := p + 15 let A : Finset (Fin 16) := Finset.univ.filter (fun j => x (v - (j.val : ZMod n)) j = true) let f : Fin 16 → Fin 5 := fun j => σ (v - (j.val : ZMod n)) have hAcard : A.card = 5 := hcount v have hfinj : Set.InjOn f (↑A : Set (Fin 16)) := by intro j hj k hk heq exact hsep _ _ j k (by ring) (Finset.mem_filter.mp hj).2 (Finset.mem_filter.mp hk).2 heq
The image of A under f is all of Fin 5, so there exists an active offset j ∈ A with σ(v - j) = σ(p + 16).
Since f is injective on A and |A| = 5, the image f(A) has cardinality 5 (by Finset.card_image_of_injOn). Because Fin 5 has cardinality 5 (Fintype.card_fin), any 5-element subset must be all of Fin 5 (Finset.eq_univ_of_card). Consequently, the label σ(p + 16) ∈ Fin 5 must lie in the image, meaning there exists j ∈ A such that f(j) = σ(v - j) = σ(p + 16) and x(v - j, j) = true.
uses
Finset.eq_univ_of_card,Finset.card_image_of_injOn,Fintype.card_fin,Finset.mem_image.mp,Finset.mem_univ,Finset.mem_filter.mphave hfull : A.image f = Finset.univ := by apply Finset.eq_univ_of_card rw [Finset.card_image_of_injOn hfinj, hAcard, Fintype.card_fin] obtain ⟨j, hjA, hlabel⟩ := Finset.mem_image.mp (show σ (p + 16) ∈ A.image f by rw [hfull]; exact Finset.mem_univ _) have hjx : x (v - (j.val : ZMod n)) j = true := (Finset.mem_filter.mp hjA).2
If j = 15, then σ(p + 16) = σ(p).
When j = 15, the class is v - j = (p + 15) - 15 = p. Substituting this into σ(v - j) = σ(p + 16) immediately gives σ(p) = σ(p + 16).
by_cases hj15 : j.val = 15 · simpa [f, v, hj15] using hlabel.symm
If j < 15, then j must be even, which implies that class q = v - j satisfies P(q) = false.
Assuming j < 15, let q = v - j = p + (15 - j). Rewriting the subtraction with Nat.cast_sub, we see that if j were odd, 15 - j would be even, which by the parity lemma hoff would imply P(q) = true. By the endpoint hypothesis (hend), active bits in an endpoint-only class must be 0 or 15; but j is odd (so j ≠ 0) and j < 15, a contradiction. Hence j must be even, which implies 15 - j is odd, so P(q) = false by hoff.
uses
Nat.cast_sub· have hjlt : j.val < 15 := by omega let q := v - (j.val : ZMod n) have hq : q = p + ((15 - j.val : ℕ) : ZMod n) := by dsimp [q, v] rw [Nat.cast_sub (by omega : j.val ≤ 15)] norm_num <;> ring have hjEven : j.val % 2 = 0 := by by_contra hodd have hd : (15 - j.val) % 2 = 0 := by omega have hPq : P q = true := by rw [hq, hoff]; simp [hd] have he := (hend q hPq j).mp hjx rcases he with he | he · omega · exact hj15 he have hPq : P q = false := by have hd : (15 - j.val) % 2 ≠ 0 := by omega rw [hq, hoff] simp [hd]
The case j < 15 leads to a contradiction, concluding the proof.
Because j is even and P(q) = false, the consecutive-bit pairing hypothesis (hpair) applies to q: bits 2a and 2a + 1 have the same truth value for a = j / 2. Since offset j = 2a is active, the adjacent offset k = j + 1 is also active in class q. But vertex q + k = (v - j) + (j + 1) = v + 1 = p + 16 is also the start of class p + 16 (offset 0), which is active by hzero. Both classes share vertex p + 16 and the label σ(q) = σ(p + 16). The separation hypothesis (hsep) then forces k = 0. Comparing numerical values via congrArg Fin.val contradicts k = j + 1 ≥ 1.
uses
Fin.ext,congrArglet a : Fin 8 := ⟨j.val / 2, by omega⟩ let k : Fin 16 := ⟨j.val + 1, by omega⟩ have hevenj : (⟨2 * a.val, by omega⟩ : Fin 16) = j := by apply Fin.ext dsimp [a] omega have hoddj : (⟨2 * a.val + 1, by omega⟩ : Fin 16) = k := by apply Fin.ext dsimp [a, k] omega have hkx : x q k = true := by have h := hpair q hPq a rw [hevenj, hoddj] at h exact h.symm.trans hjx have hpos := hsep q (p + 16) k 0 (by dsimp [q, v, k]; push_cast; ring) hkx (hzero _) hlabel have hval := congrArg Fin.val hpos dsimp [k] at hval omega
congrArg- Equal inputs to a function yield equal outputs: if a₁ = a₂, then f a₁ = f a₂.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Finset.card_image_of_injOn- The image of a finite set under an injective function has the same cardinality as the original set.
Finset.eq_univ_of_card- A subset of a finite type with the same cardinality as the entire type is the universal set.
Finset.mem_filter.mp- If an element belongs to a filtered set, then it belongs to the underlying set and satisfies the filter predicate.
Finset.mem_image.mp- If an element belongs to the image of a set under a function, then it is the image of some element in that set.
Finset.mem_univ- Every element of a finite type belongs to the universal set of that type.
Fintype.card_fin- The standard finite set Fin n has cardinality n.
Nat.cast_sub- For natural numbers m ≤ n, the difference n - m cast into an additive group with one equals the difference of their casts.
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_endpoint_layer_period_sixteen (n : ℕ) [NeZero n] (σ : ZMod n → Fin 5) (x : ZMod n → Fin 16 → Bool) (P : ZMod n → Bool) (halt : ∀ p, P (p + 1) = !(P p)) (hend : ∀ p, P p = true → ∀ j : Fin 16, x p j = true ↔ j.val = 0 ∨ j.val = 15) (hpair : ∀ p, P p = false → ∀ a : Fin 8, x p ⟨2 * a.val, by omega⟩ = x p ⟨2 * a.val + 1, by omega⟩) (hzero : ∀ p, x p 0 = true) (hcount : ∀ v : ZMod n, (Finset.univ.filter (fun j : Fin 16 => x (v - (j.val : ZMod n)) j = true)).card = 5) (hsep : ∀ (p q : ZMod n) (j k : Fin 16), p + (j.val : ZMod n) = q + (k.val : ZMod n) → x p j = true → x q k = true → σ p = σ q → j = k) : ∀ p, P p = true → σ (p + 16) = σ p := by classical have htwo : ∀ q, P (q + 2) = P q := by intro q calc P (q + 2) = P ((q + 1) + 1) := by congr 1; ring _ = !P (q + 1) := halt _ _ = P q := by rw [halt]; simp have heven : ∀ (q : ZMod n) (a : ℕ), P (q + ((2 * a : ℕ) : ZMod n)) = P q := by intro q a induction a with | zero => simp | succ a ih => calc P (q + ((2 * (a + 1) : ℕ) : ZMod n)) = P ((q + ((2 * a : ℕ) : ZMod n)) + 2) := by congr 1; push_cast; ring _ = P (q + ((2 * a : ℕ) : ZMod n)) := htwo _ _ = P q := ih intro p hp have hoff : ∀ d : ℕ, P (p + (d : ZMod n)) = if d % 2 = 0 then true else false := by intro d by_cases hd : d % 2 = 0 · have he : 2 * (d / 2) = d := by omega simpa [he, hp, hd] using heven p (d / 2) · have he : 2 * (d / 2) + 1 = d := by omega have hq : p + (d : ZMod n) = (p + 1) + ((2 * (d / 2) : ℕ) : ZMod n) := by have hc : ((2 * (d / 2) + 1 : ℕ) : ZMod n) = (d : ZMod n) := by exact congrArg (fun z : ℕ => (z : ZMod n)) he calc p + (d : ZMod n) = p + ((2 * (d / 2) + 1 : ℕ) : ZMod n) := congrArg (fun z : ZMod n => p + z) hc.symm _ = _ := by push_cast; ring rw [hq, heven, halt, hp] simp [hd] let v := p + 15 let A : Finset (Fin 16) := Finset.univ.filter (fun j => x (v - (j.val : ZMod n)) j = true) let f : Fin 16 → Fin 5 := fun j => σ (v - (j.val : ZMod n)) have hAcard : A.card = 5 := hcount v have hfinj : Set.InjOn f (↑A : Set (Fin 16)) := by intro j hj k hk heq exact hsep _ _ j k (by ring) (Finset.mem_filter.mp hj).2 (Finset.mem_filter.mp hk).2 heq have hfull : A.image f = Finset.univ := by apply Finset.eq_univ_of_card rw [Finset.card_image_of_injOn hfinj, hAcard, Fintype.card_fin] obtain ⟨j, hjA, hlabel⟩ := Finset.mem_image.mp (show σ (p + 16) ∈ A.image f by rw [hfull]; exact Finset.mem_univ _) have hjx : x (v - (j.val : ZMod n)) j = true := (Finset.mem_filter.mp hjA).2 by_cases hj15 : j.val = 15 · simpa [f, v, hj15] using hlabel.symm · have hjlt : j.val < 15 := by omega let q := v - (j.val : ZMod n) have hq : q = p + ((15 - j.val : ℕ) : ZMod n) := by dsimp [q, v] rw [Nat.cast_sub (by omega : j.val ≤ 15)] norm_num <;> ring have hjEven : j.val % 2 = 0 := by by_contra hodd have hd : (15 - j.val) % 2 = 0 := by omega have hPq : P q = true := by rw [hq, hoff]; simp [hd] have he := (hend q hPq j).mp hjx rcases he with he | he · omega · exact hj15 he have hPq : P q = false := by have hd : (15 - j.val) % 2 ≠ 0 := by omega rw [hq, hoff] simp [hd] let a : Fin 8 := ⟨j.val / 2, by omega⟩ let k : Fin 16 := ⟨j.val + 1, by omega⟩ have hevenj : (⟨2 * a.val, by omega⟩ : Fin 16) = j := by apply Fin.ext dsimp [a] omega have hoddj : (⟨2 * a.val + 1, by omega⟩ : Fin 16) = k := by apply Fin.ext dsimp [a, k] omega have hkx : x q k = true := by have h := hpair q hPq a rw [hevenj, hoddj] at h exact h.symm.trans hjx have hpos := hsep q (p + 16) k 0 (by dsimp [q, v, k]; push_cast; ring) hkx (hzero _) hlabel have hval := congrArg Fin.val hpos dsimp [k] at hval omega