cycle_power_class_half_shift_ne_of_central_occurrence
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
- cycle_power_dyadic_model_dvd_of_label_periodA finite-period tight dyadic class model with proper labels, exact dyadic edges, neighbour coverage, and full-radius label period has…
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.
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.
obtain ⟨p, hp | hp⟩ := hcentralIn 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.
· 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
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.
uses
sub_add_cancelrefine ⟨p-(H : ℤ), ?_⟩ simpa only [sub_add_cancel] using hs.symm
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.
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
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).
uses
Nat.cast_zero,sub_zerorefine ⟨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.
- Casting natural numbers (such as offsets 0, H, and 2H - 1) to integers requires routine rewrites like Nat.cast_zero and sub_zero to identify v - (0 : ℤ) with v, which are silent on paper.
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.
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