AFTD Auto-Formalizing Theoretical Domains

cycle_power_four_zero_defect_local_core

theoremverified

For a span-four model, the endpoint-count and top-owner equations and distance-one coverage rule out a defect.

Statement

theorem cycle_power_four_zero_defect_local_core
    (a b e : ℤ → Bool)
    (htop : ∀ v : ℤ, (b v).toNat + (a (v-1)).toNat + (e v).toNat = 1)
    (hcount : ∀ v : ℤ, (a (v-1)).toNat + (b (v-2)).toNat + (e v).toNat = 1)
    (hcover : ∀ v : ℤ, a v = true ∨ (a (v-1) = true ∧ b (v-1) = true) ∨ b (v-2) = true) :
    ∀ v : ℤ, e v = false
Source
Defective half-model reduction for research thread RT-1.
Verified
10 Nov 2026
Axioms
Quot.soundpropext
Used by 1

The proof, explained

The theorem is proved by contradiction: assuming a defect exists at vertex v (so e(v) = true), we derive a contradiction with the top-owner equation at v+1. First, comparing the top-owner and endpoint-count equations at every vertex shows that b is 2-periodic (b(u) = b(u-2) for all u). The assumption e(v) = true forces b(v) = false and a(v-1) = false, which together with 2-periodicity implies b(v-2) = false. Distance-one coverage at v-1 and v then successively forces b(v-1) = true and a(v) = true. Finally, b(v+1) = b(v-1) = true and a(v) = true overfill the top-owner sum at v+1, giving the desired contradiction.

  1. The sequence b is 2-periodic: b(v) = b(v - 2) for all v ∈ ℤ.

    For any vertex v, the top-owner equation gives b(v) + a(v-1) + e(v) = 1 and the endpoint-count equation gives a(v-1) + b(v-2) + e(v) = 1. Subtracting these two linear equations shows that (b(v)).toNat = (b(v-2)).toNat. Since b takes values in Bool, having equal natural-number conversions implies b(v) = b(v-2).

    lines 7–13

      have hper : ∀ v : ℤ, b v = b (v-2) := by
        intro v
        have heq : (b v).toNat = (b (v-2)).toNat := by
          have h₁ := htop v
          have h₂ := hcount v
          omega
        cases hv : b v <;> cases hw : b (v-2) <;> simp [hv, hw] at heq ⊢
  2. Assume for contradiction that there exists a vertex v where e(v) is not false, so e(v) = true.

    We fix a vertex v and assume for contradiction that e(v) ≠ false. Since e(v) is a Boolean, it must be true.

    lines 14–19

      intro v
      by_contra hn
      have hev : e v = true := by
        cases h : e v with
        | false => exact (hn h).elim
        | true => rfl
  3. b(v) = false.

    If b(v) were true, then since e(v) = true, the top-owner equation at v would force 1 + (a(v-1)).toNat + 1 = 1, which contradicts the non-negativity of natural numbers. Therefore, b(v) = false.

    lines 20–27

    uses Bool.toNat_true

      have hb : b v = false := by
        cases hv : b v with
        | false => rfl
        | true =>
          have h := htop v
          rw [hev, hv] at h
          simp only [Bool.toNat_true] at h
          omega
  4. a(v - 1) = false.

    Similarly, substituting e(v) = true and b(v) = false into the top-owner equation at v, if a(v-1) were true the equation would reduce to 0 + 1 + 1 = 1, which is impossible. Hence a(v-1) = false.

    lines 28–35

    uses Bool.toNat_true, Bool.toNat_false

      have ha : a (v-1) = false := by
        cases hv : a (v-1) with
        | false => rfl
        | true =>
          have h := htop v
          rw [hev, hb, hv] at h
          simp only [Bool.toNat_true, Bool.toNat_false] at h
          omega
  5. b(v - 2) = false.

    By the 2-periodicity of b, b(v-2) = b(v) = false.

    line 36

      have hb2 : b (v-2) = false := by rw [← hper v, hb]
  6. b(v - 3) = true.

    The distance-one coverage condition applied at vertex v-1 states that a(v-1) = true ∨ (a(v-2) = true ∧ b(v-2) = true) ∨ b(v-3) = true. Since a(v-1) = false and b(v-2) = false, the first two options are ruled out, leaving b(v-3) = true.

    lines 37–45

      have hb3 : b (v-3) = true := by
        have hc := hcover (v-1)
        have h₁ : v-1-1 = v-2 := by ring
        have h₂ : v-1-2 = v-3 := by ring
        rw [h₁,h₂] at hc
        rcases hc with h | ⟨_,h⟩ | h
        · rw [ha] at h; contradiction
        · rw [hb2] at h; contradiction
        · exact h
  7. b(v - 1) = true.

    Applying 2-periodicity to vertex v-1 yields b(v-1) = b((v-1)-2) = b(v-3) = true.

    lines 46–50

      have hb1 : b (v-1) = true := by
        have h := hper (v-1)
        have hi : v-1-2 = v-3 := by ring
        rw [hi,hb3] at h
        exact h
  8. a(v) = true.

    The distance-one coverage condition at vertex v states that a(v) = true ∨ (a(v-1) = true ∧ b(v-1) = true) ∨ b(v-2) = true. Because a(v-1) = false and b(v-2) = false, the second and third alternatives are false, forcing a(v) = true.

    lines 51–56

      have hav : a v = true := by
        have hc := hcover v
        rcases hc with h | ⟨h,_⟩ | h
        · exact h
        · rw [ha] at h; contradiction
        · rw [hb2] at h; contradiction
  9. The top-owner equation at v + 1 yields a contradiction.

    By 2-periodicity, b(v+1) = b((v+1)-2) = b(v-1) = true. Substituting b(v+1) = true and a(v) = true into the top-owner equation at v+1 yields 1 + 1 + (e(v+1)).toNat = 1, which is impossible since (e(v+1)).toNat ≥ 0. This contradicts the existence of a defect and completes the proof.

    lines 57–66

    uses Bool.toNat_true

      have hnext := htop (v+1)
      have hi : v+1-1 = v := by ring
      have hbnext : b (v+1) = true := by
        have h := hper (v+1)
        have hi : v+1-2 = v-1 := by ring
        rw [hi,hb1] at h
        exact h
      rw [hi,hbnext,hav] at hnext
      simp only [Bool.toNat_true] at hnext
      omega
Bool.toNat_true
The natural-number representation of the Boolean `true` is 1.
Bool.toNat_false
The natural-number representation of the Boolean `false` is 0.

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_four_zero_defect_local_core    (a b e : ℤ → Bool)    (htop : ∀ v : ℤ, (b v).toNat + (a (v-1)).toNat + (e v).toNat = 1)    (hcount : ∀ v : ℤ, (a (v-1)).toNat + (b (v-2)).toNat + (e v).toNat = 1)    (hcover : ∀ v : ℤ, a v = true ∨ (a (v-1) = true ∧ b (v-1) = true) ∨ b (v-2) = true) :    ∀ v : ℤ, e v = false := by  have hper : ∀ v : ℤ, b v = b (v-2) := by    intro v    have heq : (b v).toNat = (b (v-2)).toNat := by      have h₁ := htop v      have h₂ := hcount v      omega    cases hv : b v <;> cases hw : b (v-2) <;> simp [hv, hw] at heq ⊢  intro v  by_contra hn  have hev : e v = true := by    cases h : e v with    | false => exact (hn h).elim    | true => rfl  have hb : b v = false := by    cases hv : b v with    | false => rfl    | true =>      have h := htop v      rw [hev, hv] at h      simp only [Bool.toNat_true] at h      omega  have ha : a (v-1) = false := by    cases hv : a (v-1) with    | false => rfl    | true =>      have h := htop v      rw [hev, hb, hv] at h      simp only [Bool.toNat_true, Bool.toNat_false] at h      omega  have hb2 : b (v-2) = false := by rw [← hper v, hb]  have hb3 : b (v-3) = true := by    have hc := hcover (v-1)    have h₁ : v-1-1 = v-2 := by ring    have h₂ : v-1-2 = v-3 := by ring    rw [h₁,h₂] at hc    rcases hc with h | ⟨_,h⟩ | h    · rw [ha] at h; contradiction    · rw [hb2] at h; contradiction    · exact h  have hb1 : b (v-1) = true := by    have h := hper (v-1)    have hi : v-1-2 = v-3 := by ring    rw [hi,hb3] at h    exact h  have hav : a v = true := by    have hc := hcover v    rcases hc with h | ⟨h,_⟩ | h    · exact h    · rw [ha] at h; contradiction    · rw [hb2] at h; contradiction  have hnext := htop (v+1)  have hi : v+1-1 = v := by ring  have hbnext : b (v+1) = true := by    have h := hper (v+1)    have hi : v+1-2 = v-1 := by ring    rw [hi,hb1] at h    exact h  rw [hi,hbnext,hav] at hnext  simp only [Bool.toNat_true] at hnext  omega
See it in the graphDiscuss this resultChallenge it