AFTD Auto-Formalizing Theoretical Domains

cycle_power_class_half_shift_ne_of_central_occurrence

theoremverified

A central occurrence in bounded rooted classes with proper labels forces some two root labels to differ after a half-radius shift. The left central occurrence uses the preceding class endpoint; this requires no endpoint-overlap assumption.

Statement

theorem cycle_power_class_half_shift_ne_of_central_occurrence
    {α : Type*} (H : ℕ) (hH : 0 < H)
    (x : ℤ → ℕ → Bool) (ell : ℤ → α)
    (hroot : ∀ p : ℤ, x p 0 = true ∧ x p (2*H-1) = true)
    (hsep : ∀ (v : ℤ) (a b : ℕ), a < 2*H → b < 2*H → a ≠ b →
      x (v-(a : ℤ)) a = true → x (v-(b : ℤ)) b = true →
        ell (v-(a : ℤ)) ≠ ell (v-(b : ℤ)))
    (hcentral : ∃ p : ℤ, x p (H-1) = true ∨ x p H = true) :
    ∃ p : ℤ, ell (p+(H : ℤ)) ≠ ell p
Source
Uniform helpers for OP-205 / RT-1 following arXiv:2610.15635, Section 3. The neighbour-weight induction and central occurrence are class-model helpers; they do not prove the unresolved covering number. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Quot.soundpropext
Used by 1

The proof, explained

The proof proceeds by case analysis on the central occurrence guaranteed by hcentral, splitting on whether it occurs at index H - 1 (left central) or H (right central). In each case, an appropriate reference vertex v is chosen so that the central occurrence aligns with an endpoint of another rooted class (the right endpoint 2*H - 1 of the class at p - H in the left case, or the left endpoint 0 of the class at p + H in the right case). The separation hypothesis hsep then forces the root labels to differ, producing the required half-shift inequality.

  1. There exists an integer p such that either x p (H - 1) = true or x p H = true.

    By the hypothesis hcentral, there is a root position p where either the left central index H - 1 or the right central index H has an occurrence. We split into these two cases.

    line 12

      obtain ⟨p, hp | hp⟩ := hcentral
  2. In the left central case where x p (H - 1) = true, the labels satisfy ell (p - H) ≠ ell p.

    Define the reference vertex v = p + H - 1. Shifting back by a = 2*H - 1 reaches v - a = p - H, and shifting back by b = H - 1 reaches v - b = p. Since H > 0, both offsets are strictly less than 2*H and distinct. The class rooted at p - H has an occurrence at its right endpoint a = 2*H - 1 by hroot, while the class rooted at p has an occurrence at b = H - 1 by assumption. The separation condition hsep at v implies that the root labels differ: ell (p - H) ≠ ell p.

    lines 13–18

      · let v : ℤ := p+(H : ℤ)-1
        have hv0 : v-((2*H-1 : ℕ) : ℤ)=p-(H : ℤ) := by dsimp [v]; omega
        have hv1 : v-((H-1 : ℕ) : ℤ)=p := by dsimp [v]; omega
        have hs := hsep v (2*H-1) (H-1) (by omega) (by omega) (by omega)
          (by rw [hv0]; exact (hroot (p-(H : ℤ))).2) (by rw [hv1]; exact hp)
        rw [hv0, hv1] at hs
  3. There exists an integer q such that ell (q + H) ≠ ell q in the left central case.

    We choose the witness q = p - H. Then q + H = (p - H) + H = p by sub_add_cancel, so the inequality ell (q + H) ≠ ell q simplifies to ell p ≠ ell (p - H), which is the symmetry of our separation inequality ell (p - H) ≠ ell p.

    lines 19–20

    uses sub_add_cancel

        refine ⟨p-(H : ℤ), ?_⟩
        simpa only [sub_add_cancel] using hs.symm
  4. In the right central case where x p H = true, the labels satisfy ell p ≠ ell (p + H).

    Define the reference vertex v = p + H. Shifting back by a = H reaches v - a = p, and shifting back by b = 0 reaches v - 0 = v. Since 0 < H < 2*H, the offsets are bounded by 2*H and distinct. The class rooted at p has an occurrence at a = H by assumption, and the class rooted at v has an occurrence at its left endpoint b = 0 by hroot. The separation condition hsep at v implies ell (v - H) ≠ ell (v - 0), which simplifies to ell p ≠ ell (p + H) via Nat.cast_zero and sub_zero.

    lines 21–26

    uses Nat.cast_zero, sub_zero

      · let v : ℤ := p+(H : ℤ)
        have hv0 : v-(H : ℤ)=p := by dsimp [v]; omega
        have hs := hsep v H 0 (by omega) (by omega) (by omega)
          (by rw [hv0]; exact hp)
          (by simpa only [Nat.cast_zero, sub_zero] using (hroot v).1)
        rw [hv0] at hs
  5. There exists an integer q such that ell (q + H) ≠ ell q in the right central case.

    We choose the witness q = p. Then ell (p + H) ≠ ell p follows directly by symmetry from ell p ≠ ell (p + H).

    lines 27–28

    uses Nat.cast_zero, sub_zero

        refine ⟨p, ?_⟩
        simpa only [Nat.cast_zero, sub_zero] using hs.symm
sub_add_cancel
In any additive group, subtracting b and then adding b yields the original element: (a - b) + b = a.
Nat.cast_zero
The natural number 0 casts to 0 in any additive monoid with one (such as the integers ℤ).
sub_zero
Subtracting zero leaves an element unchanged: a - 0 = a.

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

open Finsettheorem cycle_power_class_half_shift_ne_of_central_occurrence    {α : Type*} (H : ℕ) (hH : 0 < H)    (x : ℤ → ℕ → Bool) (ell : ℤ → α)    (hroot : ∀ p : ℤ, x p 0 = true ∧ x p (2*H-1) = true)    (hsep : ∀ (v : ℤ) (a b : ℕ), a < 2*H → b < 2*H → a ≠ b →      x (v-(a : ℤ)) a = true → x (v-(b : ℤ)) b = true →        ell (v-(a : ℤ)) ≠ ell (v-(b : ℤ)))    (hcentral : ∃ p : ℤ, x p (H-1) = true ∨ x p H = true) :    ∃ p : ℤ, ell (p+(H : ℤ)) ≠ ell p := by  obtain ⟨p, hp | hp⟩ := hcentral  · let v : ℤ := p+(H : ℤ)-1    have hv0 : v-((2*H-1 : ℕ) : ℤ)=p-(H : ℤ) := by dsimp [v]; omega    have hv1 : v-((H-1 : ℕ) : ℤ)=p := by dsimp [v]; omega    have hs := hsep v (2*H-1) (H-1) (by omega) (by omega) (by omega)      (by rw [hv0]; exact (hroot (p-(H : ℤ))).2) (by rw [hv1]; exact hp)    rw [hv0, hv1] at hs    refine ⟨p-(H : ℤ), ?_⟩    simpa only [sub_add_cancel] using hs.symm  · let v : ℤ := p+(H : ℤ)    have hv0 : v-(H : ℤ)=p := by dsimp [v]; omega    have hs := hsep v H 0 (by omega) (by omega) (by omega)      (by rw [hv0]; exact hp)      (by simpa only [Nat.cast_zero, sub_zero] using (hroot v).1)    rw [hv0] at hs    refine ⟨p, ?_⟩    simpa only [Nat.cast_zero, sub_zero] using hs.symm
See it in the graphDiscuss this resultChallenge it