AFTD Auto-Formalizing Theoretical Domains

cycle_power_fifteen_model_no_island

theoremverified

The no-island class shape at exponent m = 4 (bandwidth 15), in the exact form the conditional theorem simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape assumes: every tight, exactly dyadically covered, fully ordinarily covered integer Boolean class model with exactly five active classes at each vertex has classes that are an initial interval together with a terminal interval.

Statement

theorem cycle_power_fifteen_model_no_island (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 : ℤ) (a b c : ℕ), a < b → b < c → c < 2^4 →
      x p a = false → x p b = true → x p c = true
Source
Research thread RT-1, open case k = 15 (m = 4) of 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 9757: on the integer window [-24, 24] the layer-free tight-class model leaves 13 class types at the centre, none with an island; on [-32, 32] the six types {0,15}, {0,1,14,15}, {0..3,12..15}, {0..7,12..15}, {0..3,8..15}, {0..15}.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 4

The proof, explained

The proof shows that every tight, dyadically covered, fully covered Boolean class model on C_n^15 with 5 active classes per vertex has no internal islands, meaning its active classes form an initial interval combined with a terminal interval. The argument adapts the model's global hypotheses to meet the prerequisites of the classification theorem cycle_power_fifteen_tight_type_sequence_no_island. Specifically, scale j = 0 forces classes 0 and 15 to be active everywhere, tightness yields 14 parent implications, peeling the boundary classes reduces the interior active count from 5 to 3, and dyadic scales j ∈ {1, 2, 3} verify exact coverage for chord lengths 14, 12, and 8.

  1. Boundary classes 0 and 15 are active at every vertex: for all p ∈ ℤ, x(p, 0) = true and x(p, 15) = true.

    Specialising the exact dyadic coverage assumption hexact to scale j = 0 gives a single-term sum over a = 0 with chord length 2^4 - 2^0 = 15, yielding x(v, 0) ∧ x(v, 15) = 1. Consequently, both endpoints x(v, 0) and x(v, 15) must be true at every vertex v.

    lines 13–19

      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
  2. Every directed edge in the 14-element parent relation set preserves activation: if x(p, e₁) = true, then x(p, e₂) = true.

    For each of the 14 pairs (e₁, e₂) in the set, we check that truth at e₁ implies truth at e₂. When e₂ is 0 or 15, the claim holds immediately from the boundary conditions h0 and h15. For the remaining pairs, the implication follows from the dyadic tightness lemma cycle_power_dyadic_tight_class_parent evaluated at scale j = 2 (connecting class 2 to 14, and class 13 to 1) and scale j = 3 (connecting classes 4, 5, 6 to 12, 13, 14, and classes 9, 10, 11 to 1, 2, 3).

    lines 20–41

    uses cycle_power_dyadic_tight_class_parent, Finset.mem_insert, Finset.mem_singleton

      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
  3. At every vertex v, exactly 3 of the 14 interior classes j ∈ {1, ..., 14} are active.

    The vertex class count hypothesis hcount gives a total sum of 4 + 1 = 5 across all 16 classes. Decomposing the range into the first term a = 0, the last term a = 15, and the 14 interior terms using Finset.sum_range_succ and Finset.sum_range_succ', and substituting x(v, 0) = 1 and x(v - 15, 15) = 1, linear integer arithmetic reduces the interior sum to 5 - 1 - 1 = 3.

    lines 42–49

    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
  4. For each dyadic chord length d ∈ {8, 12, 14}, the coverage sum over range 16 - d equals 1.

    We split into cases for d ∈ {8, 12, 14}. When d = 8, 16 - 8 = 2^3 and a + 8 = a + 2^4 - 2^3, matching hexact at dyadic scale j = 3. When d = 12, 16 - 12 = 2^2 and a + 12 = a + 2^4 - 2^2, matching hexact at scale j = 2. When d = 14, 16 - 14 = 2^1 and a + 14 = a + 2^4 - 2^1, matching hexact at scale j = 1. In each case, Finset.sum_congr and Eq.trans establish the equality with the corresponding dyadic hypothesis.

    lines 50–67

    uses Finset.mem_insert, Finset.mem_singleton, Eq.trans, Finset.sum_congr, Nat.reducePow

      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]
  5. For every chord length 1 ≤ d < 15 and vertex v, there exists a witness a < 16 - d such that x(v - a, a) = true and x(v - a, a + d) = true.

    Since d < 15 implies d < 16 = 2^4, the general coverage hypothesis hcover directly provides a witness a < 2^4 - d = 16 - d satisfying the joint activation condition.

    lines 68–72

    uses Nat.reducePow

      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⟩
  6. The class model satisfies the no-island property: if a < b < c < 16, x(p, a) = false, and x(p, b) = true, then x(p, c) = true.

    With the boundary conditions, parent relations, 3-interior-count condition, exact dyadic coverage, and general chord coverage verified, we invoke the classification theorem cycle_power_fifteen_tight_type_sequence_no_island to conclude that active classes at each vertex cannot form isolated internal islands.

    lines 73–75

    uses cycle_power_fifteen_tight_type_sequence_no_island

      intro p a b c hab hbc hc
      exact cycle_power_fifteen_tight_type_sequence_no_island x h0 h15 hparent hcount' hexact' hcover'
        p a b c hab hbc (by simpa using hc)
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 set {a} if and only if it equals a.
Finset.sum_congr
Two finite sums are equal if their index sets coincide and their summands agree on every element of the index set.
Finset.sum_range_succ
Splits off the last term (n) from a sum over Finset.range (n + 1).
Finset.sum_range_succ'
Splits off the first term (0) from a sum over Finset.range (n + 1) and shifts the remaining indices by 1.
Nat.reducePow
A simplifier rule that reduces powers of natural number literals directly (e.g. 2^4 = 16).
cycle_power_dyadic_tight_class_parent
In a tight dyadic class configuration of exponent m at dyadic scale j, truth values are preserved along parent edges: for a < 2^(j - 1), truth at a + 2^m - 2^j implies truth at a; and for 2^(j - 1) ≤ a < 2^j, truth at a implies truth at a + 2^m - 2^j.
cycle_power_fifteen_tight_type_sequence_no_island
A Boolean class model on bandwidth 15 satisfying boundary activation at 0 and 15, the 14 specified parent implications, exactly 3 active interior classes per vertex, exact dyadic coverage at chords 8, 12, 14, and full coverage for chords up to 14 has no islands: if an active class is preceded by an inactive class, all subsequent classes remain active.

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_model_no_island (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 : ℤ) (a b c : ℕ), a < b → b < c → c < 2^4 →      x p a = false → x p b = true → x p c = true := 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⟩  intro p a b c hab hbc hc  exact cycle_power_fifteen_tight_type_sequence_no_island x h0 h15 hparent hcount' hexact' hcover'    p a b c hab hbc (by simpa using hc)
See it in the graphDiscuss this resultChallenge it