AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_three_cover_three_tight_dvd

theoremverified

If three labellings with clique classes satisfy the tight structure (each distance-3 pair and each distance-2 pair in exactly one layer, every class spanned by a distance-3 pair), then 4 divides n.

Statement

theorem simple_graph_cycle_power_three_cover_three_tight_dvd (n : ℕ) [NeZero n] (hn : 10 ≤ n)
    (c : Fin 3 → ZMod n → ZMod n)
    (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n 3).Adj u v)
    (h3 : ∀ i, ∃! s, c s i = c s (i + 3)) (h2 : ∀ i, ∃! s, c s i = c s (i + 2))
    (hspan : ∀ s i, ∃ d : ℕ, d ≤ 3 ∧ c s (i - d) = c s (i - d + 3) ∧ c s (i - d) = c s i) :
    4 ∣ n
Source
Step toward simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd (the k = 3 case of OP-205, arXiv:2610.15635): the double-counting proof found in thread RT-1.
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 1

The proof, explained

The proof analyzes the structure of monochromatic cliques in the cube of the cycle $C_n$ ($n \ge 10$) partitioned across three layers. Each distance-3 chord $(i, i+3)$ belongs to a unique layer $L(i)$, defining a window of length 3 whose internal connectivity is captured by the predicate $W(k, t)$ (indicating that $k$ and $k+t$ share a label in layer $L(k)$). The distance-2 uniqueness and clique-spanning hypotheses force a strict alternation of the offset-1 predicate $W(k, 1)$, which implies that $n$ must be even ($n = 2N$). A 5-variable pigeonhole argument then establishes that shifting by 4 preserves the window layer ($L(q+4) = L(q)$) while shifting by 2 changes it ($L(q+2) \ne L(q)$), so that $L$ has period 4 on the cycle; since $L$ is also $n$-periodic, $n$ cannot be congruent to 2 modulo 4, and therefore 4 divides $n$.

  1. Three combinatorial lemmas on 3-element sets are introduced, and classical logic is enabled.

    The proof brings into scope three pigeonhole principles for `Fin 3`: four elements cannot be pairwise distinct (`fin_three_false_of_four_pairwise_ne`), two elements cannot cover all three elements (`fin_three_not_forall_eq_or_eq`), and five elements with seven specified inequalities force the fifth to equal the first (`fin_three_eq_of_five_ne`). Classical reasoning is then enabled.

    lines 7–10

    uses fin_three_false_of_four_pairwise_ne, fin_three_not_forall_eq_or_eq, fin_three_eq_of_five_ne

      have fin3_four := fin_three_false_of_four_pairwise_ne
      have fin3_two := fin_three_not_forall_eq_or_eq
      have fin3_five := fin_three_eq_of_five_ne
      classical
  2. Integer projection to $\mathbb{Z}/n\mathbb{Z}$ is injective on differences of absolute value less than $n$, and $n \ge 10$ is cast to $\mathbb{Z}$.

    By `zmod_intCast_eq_intCast_iff_of_abs_sub_lt`, two integers whose difference has absolute value strictly less than $n$ project to the same residue modulo $n$ if and only if they are equal as integers (`cinj`). The bound $n \ge 10$ is cast to the integers as `hn'`.

    lines 11–14

    uses zmod_intCast_eq_intCast_iff_of_abs_sub_lt

      -- integers as positions
      have cinj : ∀ a b : ℤ, |a - b| < n → (((a : ℤ) : ZMod n) = ((b : ℤ) : ZMod n) ↔ a = b) :=
        fun a b h => zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b h
      have hn' : (10 : ℤ) ≤ n := by exact_mod_cast hn
  3. Any vertex sharing a label with $k$ in layer $s$ lies at integer offset at most 3 from $k$.

    If $z = k$, the offset is 0. If $z \ne k$, hypothesis `hc` implies that $k$ and $z$ are adjacent in the cube of the cycle $C_n^3$. Lemma `simple_graph_cycle_power_three_adj_iff` then guarantees $z = k + e$ with $|e| \le 3$.

    lines 15–22

    uses simple_graph_cycle_power_three_adj_iff

      -- members of a class are within offset 3
      have hmem : ∀ s (k : ℤ) (z : ZMod n), c s (k : ZMod n) = c s z →
          ∃ e : ℤ, |e| ≤ 3 ∧ z = ((k + e : ℤ) : ZMod n) := by
        intro s k z h
        by_cases hz : (k : ZMod n) = z
        · exact ⟨0, by simp, by simp [hz]⟩
        · obtain ⟨e, -, he, rfl⟩ := (simple_graph_cycle_power_three_adj_iff n hn _ _).mp (hc s _ _ hz h)
          exact ⟨e, he, by push_cast; ring⟩
  4. If two integer positions differ by at most 6 and share a label in layer $s$, their difference is at most 3.

    By `hmem`, the second position must equal $k + e'$ for some $|e'| \le 3$. Since $|e| \le 6$ and $|e'| \le 3$, their difference $|e - e'| \le 9 < 10 \le n$. Injectivity modulo $n$ (`cinj`) then forces $e = e'$, so $|e| \le 3$. Linear bounds are checked using `abs_lt` and `abs_le`.

    lines 23–30

    uses abs_lt, abs_le

      -- two positions in one class differ by at most 3
      have hnear : ∀ s (k e : ℤ), |e| ≤ 6 → c s (k : ZMod n) = c s ((k + e : ℤ) : ZMod n) → |e| ≤ 3 := by
        intro s k e he h
        obtain ⟨e', he', hz⟩ := hmem s k _ h
        have := (cinj (k + e) (k + e') (by
          rw [show k + e - (k + e') = e - e' by ring, abs_lt]
          rw [abs_le] at he he'; constructor <;> omega)).mp hz
        rw [abs_le] at he' ⊢; omega
  5. Each distance-3 chord determines a unique layer $L(k)$, defining the window predicate $W(k, t)$.

    Hypothesis `h3` uniquely assigns a layer $\lambda(i) \in \text{Fin } 3$ to each distance-3 pair $(i, i+3)$. Lifting to integers gives $L(k) = \lambda(k \bmod n)$. The window predicate $W(k, t)$ states that $k$ and $k+t$ share the same label in layer $L(k)$. By definition, $W(k, 0)$ and $W(k, 3)$ always hold, and any layer covering $(k, k+3)$ must be $L(k)$.

    lines 31–43

      -- the window of k in its layer
      set lam : ZMod n → Fin 3 := fun i => (h3 i).exists.choose with hlamdef
      have hlam : ∀ i, c (lam i) i = c (lam i) (i + 3) := fun i => (h3 i).exists.choose_spec
      have hlamu : ∀ i s, c s i = c s (i + 3) → s = lam i := fun i s h => (h3 i).unique h (hlam i)
      -- integer positions
      set L : ℤ → Fin 3 := fun k => lam (k : ZMod n) with hLdef
      set W : ℤ → ℤ → Prop := fun k t => c (L k) (k : ZMod n) = c (L k) ((k + t : ℤ) : ZMod n) with hWdef
      have hW3 : ∀ k, W k 3 := fun k => by
        simp only [hWdef, hLdef]; rw [hlam (k : ZMod n)]; push_cast; rfl
      have hW0 : ∀ k, W k 0 := fun k => by simp [hWdef]
      have hLu : ∀ (k : ℤ) s, c s (k : ZMod n) = c s ((k + 3 : ℤ) : ZMod n) → s = L k := by
        intro k s h; apply hlamu; push_cast at h; exact h
      -- offsets inside a window lie in [0, 3]
  6. Any offset $t$ with $|t| \le 6$ satisfying $W(k, t)$ must lie in $[0, 3]$.

    Lemma `hnear` gives $|t| \le 3$, so $t \le 3$. If $t < 0$, then $k+t$ and $k+3$ would have the same label in layer $L(k)$ with difference $3 - t > 3$. Since $3 - t \le 6$, `hnear` would force $3 - t \le 3$, implying $t \ge 0$, a contradiction.

    lines 44–53

    uses abs_le

      have hwin : ∀ k t, |t| ≤ 6 → W k t → 0 ≤ t ∧ t ≤ 3 := by
        intro k t ht h
        have h1 := hnear (L k) k t ht h
        rw [abs_le] at h1
        refine ⟨?_, h1.2⟩
        by_contra hneg
        have h2 : c (L k) ((k + t : ℤ) : ZMod n) = c (L k) (((k + t) + (3 - t) : ℤ) : ZMod n) := by
          rw [show k + t + (3 - t) = k + 3 by ring, ← h, hW3 k]
        have := hnear (L k) (k + t) (3 - t) (by rw [abs_le]; constructor <;> omega) h2
        rw [abs_le] at this; omega
  7. Two windows in the same layer that share a vertex must coincide ($d = 0$), and $L$ and $W$ are $n$-periodic.

    If windows $k$ and $k+d$ (with $|d| \le 3$) have $L(k) = L(k+d)$ and share a vertex, then $d$ is a valid offset in window $k$ and $-d$ is a valid offset in window $k+d$. Lemma `hwin` requires both $d \ge 0$ and $-d \ge 0$, so $d = 0$ (`hshare`). Periodicity modulo $n$ holds because the cycle vertices live in $\mathbb{Z}/n\mathbb{Z}$.

    lines 54–67

    uses abs_le, abs_neg

      -- two windows of one layer sharing a vertex coincide
      have hshare : ∀ k d t t', |d| ≤ 3 → |t| ≤ 3 → |t'| ≤ 3 → L k = L (k + d) → W k t →
          W (k + d) t' → t = d + t' → d = 0 := by
        intro k d t t' hd ht ht' hL h h' htt
        have e1 : c (L k) (k : ZMod n) = c (L k) ((k + d : ℤ) : ZMod n) := by
          rw [h, show k + t = k + d + t' by rw [htt]; ring, hL]; exact h'.symm
        have w1 := hwin k d (by rw [abs_le] at hd ⊢; constructor <;> omega) e1
        have e2 : W (k + d) (-d) := by
          simp only [hWdef]; rw [show k + d + -d = k by ring, ← hL]; exact e1.symm
        have w2 := hwin (k + d) (-d) (by rw [abs_neg]; rw [abs_le] at hd ⊢; constructor <;> omega) e2
        omega
      have hL_period : ∀ k, L (k + n) = L k := fun k => by simp [hLdef]
      have hW_period : ∀ k t, W (k + n) t ↔ W k t := fun k t => by
        simp only [hWdef, hL_period]; push_cast; simp
  8. The distance-2 pair $(k, k+2)$ is monochromatic in window $k-1$ (at offset 1) if and only if it is not monochromatic in window $k$ (at offset 2): $W(k-1, 1) \iff \neg W(k, 2)$.

    By hypothesis `h2`, the pair $(k, k+2)$ is monochromatic in exactly one layer. By `hspan`, that layer must span a distance-3 chord $(k-d, k-d+3)$ containing both $k$ and $k+2$, which forces $d \in \{0, 1\}$. If both windows were monochromatic, they would belong to the same layer and share vertices, contradicting `hshare`. Hence exactly one of $W(k-1, 1)$ or $W(k, 2)$ holds.

    lines 68–102

    uses abs_le

      -- (1) the pair (k, k+2) lies in exactly one of the windows k-1 (offsets 1, 3) and k (offsets 0, 2)
      have step1 : ∀ k, W (k - 1) 1 ↔ ¬ W k 2 := by
        intro k
        constructor
        · intro ha hb
          have e1 : c (L (k - 1)) (k : ZMod n) = c (L (k - 1)) (((k : ℤ) + 2 : ℤ) : ZMod n) := by
            have := hW3 (k - 1); simp only [hWdef] at ha this
            rw [show k - 1 + 1 = k by ring] at ha; rw [show k - 1 + 3 = k + 2 by ring] at this
            rw [← ha, this]
          have e2 : c (L k) (k : ZMod n) = c (L k) (((k : ℤ) + 2 : ℤ) : ZMod n) := hb
          have hs : L (k - 1) = L k := by
            have := (h2 (k : ZMod n)).unique (y₁ := L (k - 1)) (y₂ := L k) (by push_cast at e1; exact e1)
              (by push_cast at e2; exact e2)
            exact this
          have := hshare (k - 1) 1 3 2 (by norm_num) (by norm_num) (by norm_num)
            (by rw [show k - 1 + 1 = k by ring]; exact hs) (hW3 _)
            (by rw [show k - 1 + 1 = k by ring]; exact hb) (by norm_num)
          norm_num at this
        · intro hb
          obtain ⟨s, hs, -⟩ := h2 (k : ZMod n)
          obtain ⟨d, hd, hd3, hdk⟩ := hspan s (k : ZMod n)
          have cast1 : (k : ZMod n) - (d : ℕ) = ((k - d : ℤ) : ZMod n) := by push_cast; ring
          rw [cast1] at hd3 hdk
          have hsL : s = L (k - d) := hLu _ _ (by push_cast at hd3 ⊢; rw [hd3])
          subst hsL
          have hmemd : W (k - d) (d + 2) := by
            simp only [hWdef]; rw [show k - d + (d + 2) = k + 2 by ring, hdk]
            push_cast at hs ⊢; exact hs
          have := hwin (k - d) (d + 2) (by rw [abs_le]; constructor <;> omega) hmemd
          have hd1 : d = 0 ∨ d = 1 := by omega
          rcases hd1 with rfl | rfl
          · exact absurd (by simpa [hWdef] using hmemd) hb
          · simp only [hWdef]; push_cast at hdk ⊢
            rw [show (k : ZMod n) - 1 + 1 = k by ring]; exact hdk
      -- windows of one layer cannot share a vertex
  9. Distinct overlapping windows cannot share the same layer, and every layer meets every vertex in some window.

    Lemma `hne` shows that if $1 \le d \le 3$ and windows $k$ and $k+d$ share a vertex, then $L(k) \ne L(k+d)$ by `hshare`. Lemma `hspanZ` lifts `hspan` to integers: for every layer $s$ and vertex $v$, there exists $0 \le d \le 3$ such that $s = L(v-d)$ and $W(v-d, d)$ holds.

    lines 103–118

    uses abs_le

      have hne : ∀ k d t t', 1 ≤ d → d ≤ 3 → 0 ≤ t → t ≤ 3 → 0 ≤ t' → t' ≤ 3 → W k t →
          W (k + d) t' → t = d + t' → L k ≠ L (k + d) := by
        intro k d t t' h1 h2 h3 h4 h5 h6 hW hW' htt hL
        have := hshare k d t t' (by rw [abs_le]; constructor <;> omega) (by rw [abs_le]; constructor <;> omega)
          (by rw [abs_le]; constructor <;> omega) hL hW hW' htt
        omega
      -- every layer meets v in a window
      have hspanZ : ∀ s (v : ℤ), ∃ d : ℤ, 0 ≤ d ∧ d ≤ 3 ∧ s = L (v - d) ∧ W (v - d) d := by
        intro s v
        obtain ⟨d, hd, hd3, hdk⟩ := hspan s (v : ZMod n)
        have cast1 : (v : ZMod n) - (d : ℕ) = ((v - d : ℤ) : ZMod n) := by push_cast; ring
        rw [cast1] at hd3 hdk
        have hsL : s = L (v - d) := hLu _ _ (by push_cast at hd3 ⊢; rw [hd3])
        refine ⟨d, by omega, by omega, hsL, ?_⟩
        simp only [hWdef]; rw [← hsL, show v - (d : ℤ) + d = v by ring, hdk]
      -- (2) at each vertex exactly one of the windows v-1 (offset 1) and v-2 (offset 2) contains v
  10. At each vertex $v$, exactly one of window $v-1$ (offset 1) and window $v-2$ (offset 2) contains $v$: $W(v-1, 1) \iff \neg W(v-2, 2)$.

    If both windows contained $v$, then the four windows $v, v-1, v-2, v-3$ would all contain $v$. By `hne`, their layers $L(v), L(v-1), L(v-2), L(v-3)$ would be pairwise distinct, contradicting `fin3_four`. If neither contained $v$, only windows $v$ and $v-3$ could contain $v$, meaning only 2 layers could meet $v$, contradicting `fin3_two` via `hspanZ`.

    lines 119–151

      have step2 : ∀ v, W (v - 1) 1 ↔ ¬ W (v - 2) 2 := by
        intro v
        constructor
        · intro ha hb
          have e01 := hne (v - 1) 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            ha (by rw [show v - 1 + 1 = v by ring]; exact hW0 v) (by norm_num)
          have e02 := hne (v - 2) 2 2 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) hb (by rw [show v - 2 + 2 = v by ring]; exact hW0 v) (by norm_num)
          have e03 := hne (v - 3) 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (hW3 _) (by rw [show v - 3 + 3 = v by ring]; exact hW0 v) (by norm_num)
          have e12 := hne (v - 2) 1 2 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) hb (by rw [show v - 2 + 1 = v - 1 by ring]; exact ha) (by norm_num)
          have e13 := hne (v - 3) 2 3 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (hW3 _) (by rw [show v - 3 + 2 = v - 1 by ring]; exact ha) (by norm_num)
          have e23 := hne (v - 3) 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (hW3 _) (by rw [show v - 3 + 1 = v - 2 by ring]; exact hb) (by norm_num)
          simp only [show v - 1 + 1 = v by ring, show v - 2 + 2 = v by ring, show v - 3 + 3 = v by ring,
            show v - 2 + 1 = v - 1 by ring, show v - 3 + 2 = v - 1 by ring,
            show v - 3 + 1 = v - 2 by ring] at e01 e02 e03 e12 e13 e23
          exact fin3_four (L v) (L (v - 1)) (L (v - 2)) (L (v - 3)) e01.symm e02.symm e03.symm e12.symm
            e13.symm e23.symm
        · intro hb
          by_contra ha
          apply fin3_two (L v) (L (v - 3))
          intro s
          obtain ⟨d, hd0, hd3, hs, hw⟩ := hspanZ s v
          have : d = 0 ∨ d = 1 ∨ d = 2 ∨ d = 3 := by omega
          rcases this with rfl | rfl | rfl | rfl
          · left; simpa using hs
          · exact absurd hw ha
          · exact absurd hw hb
          · right; exact hs
      -- (3) the offset-1 pattern is 2-periodic
  11. The offset-1 predicate is 2-periodic: $W(k+1, 1) \iff W(k-1, 1)$, and $W(j, 2) \iff \neg W(j-1, 1)$.

    Combining `step1` at $k$ ($W(k-1, 1) \iff \neg W(k, 2)$) with `step2` at $k+2$ ($W(k+1, 1) \iff \neg W(k, 2)$) yields $W(k+1, 1) \iff W(k-1, 1)$ (`hper2`). Rewriting `step1` with double negation elimination (`not_not`) gives $W(j, 2) \iff \neg W(j-1, 1)$ (`hb`).

    lines 152–158

    uses not_not

      have hper2 : ∀ k, W (k + 1) 1 ↔ W (k - 1) 1 := by
        intro k
        have h1 := step1 k
        have h2' := step2 (k + 2)
        rw [show k + 2 - 1 = k + 1 by ring, show k + 2 - 2 = k by ring] at h2'
        rw [h1, h2']
      have hb : ∀ j, W j 2 ↔ ¬ W (j - 1) 1 := fun j => by rw [step1 j, not_not]
  12. The predicate $W(k, 1)$ cannot have the same truth value at adjacent positions.

    Suppose for contradiction that $W(k, 1) \iff W(k+1, 1)$ for some $k$. By 2-periodicity, $W(k+t, 1)$ has the same truth value for all $t \in \{0, 1, 2, 3\}$. If this truth value is true, windows $k, k+1, k+2, k+3$ share vertices at offset 1 or 3, so `hne` makes all 4 of their layers pairwise distinct, contradicting `fin3_four`. If false, then by `hb`, $W(k+t, 2)$ are all true, which again forces all 4 layers to be pairwise distinct via `hne`, another contradiction.

    lines 159–204

      by_cases hA : ∃ k, (W k 1 ↔ W (k + 1) 1)
      · exfalso
        obtain ⟨k, hk⟩ := hA
        have a2 : W (k + 2) 1 ↔ W k 1 := by
          have := hper2 (k + 1)
          rw [show k + 1 + 1 = k + 2 by ring, show k + 1 - 1 = k by ring] at this; exact this
        have a3 : W (k + 3) 1 ↔ W k 1 := by
          have := hper2 (k + 2)
          rw [show k + 2 + 1 = k + 3 by ring, show k + 2 - 1 = k + 1 by ring] at this; rw [this, hk]
        have am1 : W (k - 1) 1 ↔ W k 1 := by rw [← hper2 k, hk]
        have b0 : W k 2 ↔ ¬ W k 1 := by rw [hb, am1]
        have b1 : W (k + 1) 2 ↔ ¬ W k 1 := by rw [hb, show k + 1 - 1 = k by ring]
        have b2 : W (k + 2) 2 ↔ ¬ W k 1 := by rw [hb, show k + 2 - 1 = k + 1 by ring, ← hk]
        have b3 : W (k + 3) 2 ↔ ¬ W k 1 := by rw [hb, show k + 3 - 1 = k + 2 by ring, a2]
        have e3 : ∀ j : ℤ, k + 1 + j = k + (1 + j) := fun j => by ring
        by_cases hα : W k 1
        · have e01 := hne k 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) hα
            (hW0 _) (by norm_num)
          have e02 := hne k 2 3 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (hW3 k) (a2.mpr hα) (by norm_num)
          have e03 := hne k 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (hW3 k) (hW0 _) (by norm_num)
          have e12 := hne (k + 1) 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (hk.mp hα) (hW0 _) (by norm_num)
          have e13 := hne (k + 1) 2 3 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (hW3 _) (by rw [show k + 1 + 2 = k + 3 by ring]; exact a3.mpr hα) (by norm_num)
          have e23 := hne (k + 2) 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (a2.mpr hα) (hW0 _) (by norm_num)
          simp only [show k + 1 + 1 = k + 2 by ring, show k + 1 + 2 = k + 3 by ring,
            show k + 2 + 1 = k + 3 by ring] at e12 e13 e23
          exact fin3_four _ _ _ _ e01 e02 e03 e12 e13 e23
        · have e01 := hne k 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (hW3 k) (b1.mpr hα) (by norm_num)
          have e02 := hne k 2 2 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (b0.mpr hα) (hW0 _) (by norm_num)
          have e03 := hne k 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (hW3 k) (hW0 _) (by norm_num)
          have e12 := hne (k + 1) 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (hW3 _) (by rw [show k + 1 + 1 = k + 2 by ring]; exact b2.mpr hα) (by norm_num)
          have e13 := hne (k + 1) 2 2 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (b1.mpr hα) (hW0 _) (by norm_num)
          have e23 := hne (k + 2) 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (hW3 _) (by rw [show k + 2 + 1 = k + 3 by ring]; exact b3.mpr hα) (by norm_num)
          simp only [show k + 1 + 1 = k + 2 by ring, show k + 1 + 2 = k + 3 by ring,
            show k + 2 + 1 = k + 3 by ring] at e12 e13 e23
          exact fin3_four _ _ _ _ e01 e02 e03 e12 e13 e23
  13. The predicate $W(k, 1)$ strictly alternates with parity, $n$ is even ($n = 2N$), and there is a base index $p$ with $W(p, 1)$.

    Having eliminated adjacent agreement, $W(k+1, 1) \iff \neg W(k, 1)$ for all $k$ (`hB`). By induction (`Nat.even_add_one`), $W(j, 1)$ strictly alternates with the parity of $j$ (`hpar`). Since the cycle is $n$-periodic (`zero_add`), shifting by $n$ must preserve truth value, which requires $n$ to be even (`hEven`). Writing $n = 2N$, a base integer $p \in \{0, 1\}$ with $W(p, 1)$ is chosen.

    lines 205–225

    uses Nat.even_add_one, zero_add

      · push Not at hA
        have hB : ∀ k, W (k + 1) 1 ↔ ¬ W k 1 := fun k => by
          have := hA k; tauto
        -- n is even
        have hpar : ∀ j : ℕ, (W (j : ℤ) 1 ↔ (W 0 1 ↔ Even j)) := by
          intro j
          induction j with
          | zero => simp
          | succ j ih =>
            rw [show ((j + 1 : ℕ) : ℤ) = (j : ℤ) + 1 by push_cast; ring, hB, ih, Nat.even_add_one]
            tauto
        have hEven : Even n := by
          have h1 := hpar n
          have h2 := hW_period 0 1
          rw [zero_add] at h2
          tauto
        obtain ⟨N, hN⟩ := hEven
        obtain ⟨p, hp⟩ : ∃ p : ℤ, W p 1 := by
          by_cases h0 : W 0 1
          · exact ⟨0, h0⟩
          · exact ⟨0 + 1, (hB 0).mpr h0⟩
  14. For any $q$ with $W(q, 1)$, shifting by 4 preserves the layer ($L(q+4) = L(q)$) and shifting by 2 changes it ($L(q+2) \ne L(q)$).

    From $W(q, 1)$, alternation implies $\neg W(q+1, 1)$ and $W(q+2, 1)$, whence $W(q+2, 2)$ holds. Applying `hne` between windows $q, q+1, q+2, q+3, q+4$ yields seven pairwise distinctness relations between their layers. Lemma `fin_three_eq_of_five_ne` then forces $L(q+4) = L(q)$, while $L(q+2) \ne L(q)$ follows from `Ne.symm` on the relation between $q$ and $q+2$.

    lines 226–248

    uses Ne.symm

        have key : ∀ q : ℤ, W q 1 → L (q + 4) = L q ∧ L (q + 2) ≠ L q := by
          intro q hq
          have hq1 : ¬ W (q + 1) 1 := fun h => ((hB q).mp h) hq
          have hq2 : W (q + 2) 1 := by
            have := (hB (q + 1)).mpr hq1; rwa [show q + 1 + 1 = q + 2 by ring] at this
          have hb2 : W (q + 2) 2 := (hb _).mpr (by rw [show q + 2 - 1 = q + 1 by ring]; exact hq1)
          have x02 := hne q 2 3 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (hW3 q) hq2 (by norm_num)
          have x03 := hne q 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (hW3 q) (hW0 _) (by norm_num)
          have x23 := hne (q + 2) 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            hq2 (hW0 _) (by norm_num)
          have y12 := hne (q + 1) 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) (hW3 _) (by rw [show q + 1 + 1 = q + 2 by ring]; exact hb2) (by norm_num)
          have y14 := hne (q + 1) 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (hW3 _) (hW0 _) (by norm_num)
          have y24 := hne (q + 2) 2 2 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
            (by norm_num) hb2 (hW0 _) (by norm_num)
          have z01 := hne q 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) hq
            (hW0 _) (by norm_num)
          simp only [show q + 2 + 1 = q + 3 by ring, show q + 1 + 1 = q + 2 by ring,
            show q + 1 + 3 = q + 4 by ring, show q + 2 + 2 = q + 4 by ring] at x23 y12 y14 y24
          exact ⟨fin3_five _ _ _ _ _ x02 x03 x23 y12 y14 y24 z01, Ne.symm x02⟩
  15. By induction, $L(p + 4j) = L(p)$ and $L(p + 4j + 2) \ne L(p)$ for all $j \in \mathbb{N}$.

    First, $W(p + 2j, 1)$ holds for all $j$ by two-step induction using the alternation rule `hB` (`hEv`). Then, applying `key` inductively gives $L(p + 4(j+1)) = L(p + 4j + 4) = L(p + 4j) = L(p)$, while $L(p + 4j + 2) \ne L(p)$ holds at every step (`hL2`).

    lines 249–270

        have hEv : ∀ j : ℕ, W (p + 2 * j) 1 := by
          intro j
          induction j with
          | zero => simpa using hp
          | succ j ih =>
            have h1 : ¬ W (p + 2 * j + 1) 1 := fun h => ((hB _).mp h) ih
            have := (hB (p + 2 * j + 1)).mpr h1
            rwa [show p + 2 * j + 1 + 1 = p + 2 * ((j + 1 : ℕ) : ℤ) by push_cast; ring] at this
        have hL2 : ∀ j : ℕ, L (p + 2 * (2 * j : ℕ)) = L p ∧ L (p + 2 * (2 * j + 1 : ℕ)) ≠ L p := by
          intro j
          induction j with
          | zero =>
            refine ⟨by simp, ?_⟩
            have := (key p hp).2; simpa using this
          | succ j ih =>
            have k1 := key _ (hEv (2 * j))
            have k2 := key _ (hEv (2 * j + 1))
            refine ⟨?_, ?_⟩
            · rw [← ih.1, ← k1.1]; congr 1; push_cast; ring
            · rw [show p + 2 * ((2 * (j + 1) + 1 : ℕ) : ℤ) = p + 2 * ((2 * j + 1 : ℕ) : ℤ) + 4 by
                push_cast; ring, k2.1]
              exact ih.2
  16. $N = n/2$ must be even, and therefore 4 divides $n$.

    By `Nat.even_or_odd`, $N$ is either even ($N = 2j$) or odd ($N = 2j+1$). If $N$ were odd, then $n = 2(2j+1) = 4j + 2$. By `hL2`, $L(p + n) = L(p + 4j + 2) \ne L(p)$. But $L$ is $n$-periodic (`hL_period`), so $L(p + n) = L(p)$, a contradiction. Thus $N$ is even, so $n = 4j$, which proves $4 \mid n$.

    lines 271–278

    uses Nat.even_or_odd

        rcases Nat.even_or_odd N with ⟨j, hj⟩ | ⟨j, hj⟩
        · exact ⟨j, by omega⟩
        · exfalso
          have h1 := (hL2 j).2
          apply h1
          have : p + 2 * ((2 * j + 1 : ℕ) : ℤ) = p + n := by
            rw [hN, ← hj]; push_cast; ring
          rw [this, hL_period]
fin_three_false_of_four_pairwise_ne
In a 3-element set, no four elements can be pairwise distinct (pigeonhole principle).
fin_three_not_forall_eq_or_eq
A 3-element set cannot be covered by at most two values.
fin_three_eq_of_five_ne
Given five elements in a 3-element set with seven specified distinctness relations ($a \ne c$, $a \ne d$, $c \ne d$, $b \ne c$, $b \ne e$, $c \ne e$, $a \ne b$), the fifth element must equal the first ($e = a$).
zmod_intCast_eq_intCast_iff_of_abs_sub_lt
Two integers whose difference has absolute value strictly less than $n$ are congruent modulo $n$ if and only if they are equal as integers.
simple_graph_cycle_power_three_adj_iff
In the cube of the cycle graph $C_n$ with $n \ge 10$, two vertices are adjacent if and only if they are distinct and their cyclic difference is at most 3 in absolute value.
abs_lt
The absolute value of $a$ is strictly less than $b$ if and only if $-b < a < b$.
abs_le
The absolute value of $a$ is at most $b$ if and only if $-b \le a \le b$.
abs_neg
The absolute value of $-a$ equals the absolute value of $a$.
not_not
Double negation elimination: $\neg\neg a \leftrightarrow a$.
Nat.even_add_one
A natural number $n + 1$ is even if and only if $n$ is not even.
zero_add
Adding zero on the left leaves an element unchanged: $0 + a = a$.
Ne.symm
Inequality is symmetric: if $a \ne b$, then $b \ne a$.
Nat.even_or_odd
Every natural number is either even or odd.

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

Lean’s trace was cut to the first 400 of 572 tactics.

theorem simple_graph_cycle_power_three_cover_three_tight_dvd (n : ℕ) [NeZero n] (hn : 10 ≤ n)    (c : Fin 3 → ZMod n → ZMod n)    (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n 3).Adj u v)    (h3 : ∀ i, ∃! s, c s i = c s (i + 3)) (h2 : ∀ i, ∃! s, c s i = c s (i + 2))    (hspan : ∀ s i, ∃ d : ℕ, d ≤ 3 ∧ c s (i - d) = c s (i - d + 3) ∧ c s (i - d) = c s i) :    4 ∣ n := by  have fin3_four := fin_three_false_of_four_pairwise_ne  have fin3_two := fin_three_not_forall_eq_or_eq  have fin3_five := fin_three_eq_of_five_ne  classical  -- integers as positions  have cinj : ∀ a b : ℤ, |a - b| < n → (((a : ℤ) : ZMod n) = ((b : ℤ) : ZMod n) ↔ a = b) :=    fun a b h => zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b h  have hn' : (10 : ℤ) ≤ n := by exact_mod_cast hn  -- members of a class are within offset 3  have hmem : ∀ s (k : ℤ) (z : ZMod n), c s (k : ZMod n) = c s z →      ∃ e : ℤ, |e| ≤ 3 ∧ z = ((k + e : ℤ) : ZMod n) := by    intro s k z h    by_cases hz : (k : ZMod n) = z    · exact ⟨0, by simp, by simp [hz]⟩    · obtain ⟨e, -, he, rfl⟩ := (simple_graph_cycle_power_three_adj_iff n hn _ _).mp (hc s _ _ hz h)      exact ⟨e, he, by push_cast; ring⟩  -- two positions in one class differ by at most 3  have hnear : ∀ s (k e : ℤ), |e| ≤ 6 → c s (k : ZMod n) = c s ((k + e : ℤ) : ZMod n) → |e| ≤ 3 := by    intro s k e he h    obtain ⟨e', he', hz⟩ := hmem s k _ h    have := (cinj (k + e) (k + e') (by      rw [show k + e - (k + e') = e - e' by ring, abs_lt]      rw [abs_le] at he he'; constructor <;> omega)).mp hz    rw [abs_le] at he' ⊢; omega  -- the window of k in its layer  set lam : ZMod n → Fin 3 := fun i => (h3 i).exists.choose with hlamdef  have hlam : ∀ i, c (lam i) i = c (lam i) (i + 3) := fun i => (h3 i).exists.choose_spec  have hlamu : ∀ i s, c s i = c s (i + 3) → s = lam i := fun i s h => (h3 i).unique h (hlam i)  -- integer positions  set L : ℤ → Fin 3 := fun k => lam (k : ZMod n) with hLdef  set W : ℤ → ℤ → Prop := fun k t => c (L k) (k : ZMod n) = c (L k) ((k + t : ℤ) : ZMod n) with hWdef  have hW3 : ∀ k, W k 3 := fun k => by    simp only [hWdef, hLdef]; rw [hlam (k : ZMod n)]; push_cast; rfl  have hW0 : ∀ k, W k 0 := fun k => by simp [hWdef]  have hLu : ∀ (k : ℤ) s, c s (k : ZMod n) = c s ((k + 3 : ℤ) : ZMod n) → s = L k := by    intro k s h; apply hlamu; push_cast at h; exact h  -- offsets inside a window lie in [0, 3]  have hwin : ∀ k t, |t| ≤ 6 → W k t → 0 ≤ t ∧ t ≤ 3 := by    intro k t ht h    have h1 := hnear (L k) k t ht h    rw [abs_le] at h1    refine ⟨?_, h1.2⟩    by_contra hneg    have h2 : c (L k) ((k + t : ℤ) : ZMod n) = c (L k) (((k + t) + (3 - t) : ℤ) : ZMod n) := by      rw [show k + t + (3 - t) = k + 3 by ring, ← h, hW3 k]    have := hnear (L k) (k + t) (3 - t) (by rw [abs_le]; constructor <;> omega) h2    rw [abs_le] at this; omega  -- two windows of one layer sharing a vertex coincide  have hshare : ∀ k d t t', |d| ≤ 3 → |t| ≤ 3 → |t'| ≤ 3 → L k = L (k + d) → W k t →      W (k + d) t' → t = d + t' → d = 0 := by    intro k d t t' hd ht ht' hL h h' htt    have e1 : c (L k) (k : ZMod n) = c (L k) ((k + d : ℤ) : ZMod n) := by      rw [h, show k + t = k + d + t' by rw [htt]; ring, hL]; exact h'.symm    have w1 := hwin k d (by rw [abs_le] at hd ⊢; constructor <;> omega) e1    have e2 : W (k + d) (-d) := by      simp only [hWdef]; rw [show k + d + -d = k by ring, ← hL]; exact e1.symm    have w2 := hwin (k + d) (-d) (by rw [abs_neg]; rw [abs_le] at hd ⊢; constructor <;> omega) e2    omega  have hL_period : ∀ k, L (k + n) = L k := fun k => by simp [hLdef]  have hW_period : ∀ k t, W (k + n) t ↔ W k t := fun k t => by    simp only [hWdef, hL_period]; push_cast; simp  -- (1) the pair (k, k+2) lies in exactly one of the windows k-1 (offsets 1, 3) and k (offsets 0, 2)  have step1 : ∀ k, W (k - 1) 1 ↔ ¬ W k 2 := by    intro k    constructor    · intro ha hb      have e1 : c (L (k - 1)) (k : ZMod n) = c (L (k - 1)) (((k : ℤ) + 2 : ℤ) : ZMod n) := by        have := hW3 (k - 1); simp only [hWdef] at ha this        rw [show k - 1 + 1 = k by ring] at ha; rw [show k - 1 + 3 = k + 2 by ring] at this        rw [← ha, this]      have e2 : c (L k) (k : ZMod n) = c (L k) (((k : ℤ) + 2 : ℤ) : ZMod n) := hb      have hs : L (k - 1) = L k := by        have := (h2 (k : ZMod n)).unique (y₁ := L (k - 1)) (y₂ := L k) (by push_cast at e1; exact e1)          (by push_cast at e2; exact e2)        exact this      have := hshare (k - 1) 1 3 2 (by norm_num) (by norm_num) (by norm_num)        (by rw [show k - 1 + 1 = k by ring]; exact hs) (hW3 _)        (by rw [show k - 1 + 1 = k by ring]; exact hb) (by norm_num)      norm_num at this    · intro hb      obtain ⟨s, hs, -⟩ := h2 (k : ZMod n)      obtain ⟨d, hd, hd3, hdk⟩ := hspan s (k : ZMod n)      have cast1 : (k : ZMod n) - (d : ℕ) = ((k - d : ℤ) : ZMod n) := by push_cast; ring      rw [cast1] at hd3 hdk      have hsL : s = L (k - d) := hLu _ _ (by push_cast at hd3 ⊢; rw [hd3])      subst hsL      have hmemd : W (k - d) (d + 2) := by        simp only [hWdef]; rw [show k - d + (d + 2) = k + 2 by ring, hdk]        push_cast at hs ⊢; exact hs      have := hwin (k - d) (d + 2) (by rw [abs_le]; constructor <;> omega) hmemd      have hd1 : d = 0 ∨ d = 1 := by omega      rcases hd1 with rfl | rfl      · exact absurd (by simpa [hWdef] using hmemd) hb      · simp only [hWdef]; push_cast at hdk ⊢        rw [show (k : ZMod n) - 1 + 1 = k by ring]; exact hdk  -- windows of one layer cannot share a vertex  have hne : ∀ k d t t', 1 ≤ d → d ≤ 3 → 0 ≤ t → t ≤ 3 → 0 ≤ t' → t' ≤ 3 → W k t →      W (k + d) t' → t = d + t' → L k ≠ L (k + d) := by    intro k d t t' h1 h2 h3 h4 h5 h6 hW hW' htt hL    have := hshare k d t t' (by rw [abs_le]; constructor <;> omega) (by rw [abs_le]; constructor <;> omega)      (by rw [abs_le]; constructor <;> omega) hL hW hW' htt    omega  -- every layer meets v in a window  have hspanZ : ∀ s (v : ℤ), ∃ d : ℤ, 0 ≤ d ∧ d ≤ 3 ∧ s = L (v - d) ∧ W (v - d) d := by    intro s v    obtain ⟨d, hd, hd3, hdk⟩ := hspan s (v : ZMod n)    have cast1 : (v : ZMod n) - (d : ℕ) = ((v - d : ℤ) : ZMod n) := by push_cast; ring    rw [cast1] at hd3 hdk    have hsL : s = L (v - d) := hLu _ _ (by push_cast at hd3 ⊢; rw [hd3])    refine ⟨d, by omega, by omega, hsL, ?_⟩    simp only [hWdef]; rw [← hsL, show v - (d : ℤ) + d = v by ring, hdk]  -- (2) at each vertex exactly one of the windows v-1 (offset 1) and v-2 (offset 2) contains v  have step2 : ∀ v, W (v - 1) 1 ↔ ¬ W (v - 2) 2 := by    intro v    constructor    · intro ha hb      have e01 := hne (v - 1) 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        ha (by rw [show v - 1 + 1 = v by ring]; exact hW0 v) (by norm_num)      have e02 := hne (v - 2) 2 2 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) hb (by rw [show v - 2 + 2 = v by ring]; exact hW0 v) (by norm_num)      have e03 := hne (v - 3) 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (hW3 _) (by rw [show v - 3 + 3 = v by ring]; exact hW0 v) (by norm_num)      have e12 := hne (v - 2) 1 2 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) hb (by rw [show v - 2 + 1 = v - 1 by ring]; exact ha) (by norm_num)      have e13 := hne (v - 3) 2 3 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (hW3 _) (by rw [show v - 3 + 2 = v - 1 by ring]; exact ha) (by norm_num)      have e23 := hne (v - 3) 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (hW3 _) (by rw [show v - 3 + 1 = v - 2 by ring]; exact hb) (by norm_num)      simp only [show v - 1 + 1 = v by ring, show v - 2 + 2 = v by ring, show v - 3 + 3 = v by ring,        show v - 2 + 1 = v - 1 by ring, show v - 3 + 2 = v - 1 by ring,        show v - 3 + 1 = v - 2 by ring] at e01 e02 e03 e12 e13 e23      exact fin3_four (L v) (L (v - 1)) (L (v - 2)) (L (v - 3)) e01.symm e02.symm e03.symm e12.symm        e13.symm e23.symm    · intro hb      by_contra ha      apply fin3_two (L v) (L (v - 3))      intro s      obtain ⟨d, hd0, hd3, hs, hw⟩ := hspanZ s v      have : d = 0 ∨ d = 1 ∨ d = 2 ∨ d = 3 := by omega      rcases this with rfl | rfl | rfl | rfl      · left; simpa using hs      · exact absurd hw ha      · exact absurd hw hb      · right; exact hs  -- (3) the offset-1 pattern is 2-periodic  have hper2 : ∀ k, W (k + 1) 1 ↔ W (k - 1) 1 := by    intro k    have h1 := step1 k    have h2' := step2 (k + 2)    rw [show k + 2 - 1 = k + 1 by ring, show k + 2 - 2 = k by ring] at h2'    rw [h1, h2']  have hb : ∀ j, W j 2 ↔ ¬ W (j - 1) 1 := fun j => by rw [step1 j, not_not]  by_cases hA : ∃ k, (W k 1 ↔ W (k + 1) 1)  · exfalso    obtain ⟨k, hk⟩ := hA    have a2 : W (k + 2) 1 ↔ W k 1 := by      have := hper2 (k + 1)      rw [show k + 1 + 1 = k + 2 by ring, show k + 1 - 1 = k by ring] at this; exact this    have a3 : W (k + 3) 1 ↔ W k 1 := by      have := hper2 (k + 2)      rw [show k + 2 + 1 = k + 3 by ring, show k + 2 - 1 = k + 1 by ring] at this; rw [this, hk]    have am1 : W (k - 1) 1 ↔ W k 1 := by rw [← hper2 k, hk]    have b0 : W k 2 ↔ ¬ W k 1 := by rw [hb, am1]    have b1 : W (k + 1) 2 ↔ ¬ W k 1 := by rw [hb, show k + 1 - 1 = k by ring]    have b2 : W (k + 2) 2 ↔ ¬ W k 1 := by rw [hb, show k + 2 - 1 = k + 1 by ring, ← hk]    have b3 : W (k + 3) 2 ↔ ¬ W k 1 := by rw [hb, show k + 3 - 1 = k + 2 by ring, a2]    have e3 : ∀ j : ℤ, k + 1 + j = k + (1 + j) := fun j => by ring    by_cases hα : W k 1    · have e01 := hne k 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) hα        (hW0 _) (by norm_num)      have e02 := hne k 2 3 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (hW3 k) (a2.mpr hα) (by norm_num)      have e03 := hne k 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (hW3 k) (hW0 _) (by norm_num)      have e12 := hne (k + 1) 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (hk.mp hα) (hW0 _) (by norm_num)      have e13 := hne (k + 1) 2 3 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (hW3 _) (by rw [show k + 1 + 2 = k + 3 by ring]; exact a3.mpr hα) (by norm_num)      have e23 := hne (k + 2) 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (a2.mpr hα) (hW0 _) (by norm_num)      simp only [show k + 1 + 1 = k + 2 by ring, show k + 1 + 2 = k + 3 by ring,        show k + 2 + 1 = k + 3 by ring] at e12 e13 e23      exact fin3_four _ _ _ _ e01 e02 e03 e12 e13 e23    · have e01 := hne k 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (hW3 k) (b1.mpr hα) (by norm_num)      have e02 := hne k 2 2 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (b0.mpr hα) (hW0 _) (by norm_num)      have e03 := hne k 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (hW3 k) (hW0 _) (by norm_num)      have e12 := hne (k + 1) 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (hW3 _) (by rw [show k + 1 + 1 = k + 2 by ring]; exact b2.mpr hα) (by norm_num)      have e13 := hne (k + 1) 2 2 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (b1.mpr hα) (hW0 _) (by norm_num)      have e23 := hne (k + 2) 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (hW3 _) (by rw [show k + 2 + 1 = k + 3 by ring]; exact b3.mpr hα) (by norm_num)      simp only [show k + 1 + 1 = k + 2 by ring, show k + 1 + 2 = k + 3 by ring,        show k + 2 + 1 = k + 3 by ring] at e12 e13 e23      exact fin3_four _ _ _ _ e01 e02 e03 e12 e13 e23  · push Not at hA    have hB : ∀ k, W (k + 1) 1 ↔ ¬ W k 1 := fun k => by      have := hA k; tauto    -- n is even    have hpar : ∀ j : ℕ, (W (j : ℤ) 1 ↔ (W 0 1 ↔ Even j)) := by      intro j      induction j with      | zero => simp      | succ j ih =>        rw [show ((j + 1 : ℕ) : ℤ) = (j : ℤ) + 1 by push_cast; ring, hB, ih, Nat.even_add_one]        tauto    have hEven : Even n := by      have h1 := hpar n      have h2 := hW_period 0 1      rw [zero_add] at h2      tauto    obtain ⟨N, hN⟩ := hEven    obtain ⟨p, hp⟩ : ∃ p : ℤ, W p 1 := by      by_cases h0 : W 0 1      · exact ⟨0, h0⟩      · exact ⟨0 + 1, (hB 0).mpr h0⟩    have key : ∀ q : ℤ, W q 1 → L (q + 4) = L q ∧ L (q + 2) ≠ L q := by      intro q hq      have hq1 : ¬ W (q + 1) 1 := fun h => ((hB q).mp h) hq      have hq2 : W (q + 2) 1 := by        have := (hB (q + 1)).mpr hq1; rwa [show q + 1 + 1 = q + 2 by ring] at this      have hb2 : W (q + 2) 2 := (hb _).mpr (by rw [show q + 2 - 1 = q + 1 by ring]; exact hq1)      have x02 := hne q 2 3 1 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (hW3 q) hq2 (by norm_num)      have x03 := hne q 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (hW3 q) (hW0 _) (by norm_num)      have x23 := hne (q + 2) 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        hq2 (hW0 _) (by norm_num)      have y12 := hne (q + 1) 1 3 2 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) (hW3 _) (by rw [show q + 1 + 1 = q + 2 by ring]; exact hb2) (by norm_num)      have y14 := hne (q + 1) 3 3 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (hW3 _) (hW0 _) (by norm_num)      have y24 := hne (q + 2) 2 2 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num)        (by norm_num) hb2 (hW0 _) (by norm_num)      have z01 := hne q 1 1 0 (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num) hq        (hW0 _) (by norm_num)      simp only [show q + 2 + 1 = q + 3 by ring, show q + 1 + 1 = q + 2 by ring,        show q + 1 + 3 = q + 4 by ring, show q + 2 + 2 = q + 4 by ring] at x23 y12 y14 y24      exact ⟨fin3_five _ _ _ _ _ x02 x03 x23 y12 y14 y24 z01, Ne.symm x02⟩    have hEv : ∀ j : ℕ, W (p + 2 * j) 1 := by      intro j      induction j with      | zero => simpa using hp      | succ j ih =>        have h1 : ¬ W (p + 2 * j + 1) 1 := fun h => ((hB _).mp h) ih        have := (hB (p + 2 * j + 1)).mpr h1        rwa [show p + 2 * j + 1 + 1 = p + 2 * ((j + 1 : ℕ) : ℤ) by push_cast; ring] at this    have hL2 : ∀ j : ℕ, L (p + 2 * (2 * j : ℕ)) = L p ∧ L (p + 2 * (2 * j + 1 : ℕ)) ≠ L p := by      intro j      induction j with      | zero =>        refine ⟨by simp, ?_⟩        have := (key p hp).2; simpa using this      | succ j ih =>        have k1 := key _ (hEv (2 * j))        have k2 := key _ (hEv (2 * j + 1))        refine ⟨?_, ?_⟩        · rw [← ih.1, ← k1.1]; congr 1; push_cast; ring        · rw [show p + 2 * ((2 * (j + 1) + 1 : ℕ) : ℤ) = p + 2 * ((2 * j + 1 : ℕ) : ℤ) + 4 by            push_cast; ring, k2.1]          exact ih.2    rcases Nat.even_or_odd N with ⟨j, hj⟩ | ⟨j, hj⟩    · exact ⟨j, by omega⟩    · exfalso      have h1 := (hL2 j).2      apply h1      have : p + 2 * ((2 * j + 1 : ℕ) : ℤ) = p + n := by        rw [hN, ← hj]; push_cast; ring      rw [this, hL_period]
See it in the graphDiscuss this resultChallenge it