AFTD Auto-Formalizing Theoretical Domains

cycle_power_fifteen_endpoint_layer_period_sixteen

theoremverified

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.

  1. 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.

    line 8

          x p ⟨2 * a.val, by omega⟩ = x p ⟨2 * a.val + 1, by omega⟩)
  2. 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.

    lines 16–30

      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
  3. 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.

    lines 31–45

    uses congrArg

      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]
  4. 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.

    lines 46–52

    uses Finset.mem_filter.mp

      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
  5. 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.

    lines 53–58

    uses Finset.eq_univ_of_card, Finset.card_image_of_injOn, Fintype.card_fin, Finset.mem_image.mp, Finset.mem_univ, Finset.mem_filter.mp

      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
  6. 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).

    lines 59–60

      by_cases hj15 : j.val = 15
      · simpa [f, v, hj15] using hlabel.symm
  7. 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.

    lines 61–78

    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]
  8. 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.

    lines 79–97

    uses Fin.ext, congrArg

        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
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

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
See it in the graphDiscuss this resultChallenge it