simple_graph_cycle_power_three_cover_three_tight_dvd
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
- simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
- fin_three_not_forall_eq_or_eqTwo elements of Fin 3 never exhaust it.
- fin_three_eq_of_five_neIn Fin 3, if a, c, d are distinct, b ∉ {c, e}, c ≠ e and a ≠ b, then e = a.
- simple_graph_cycle_power_three_adj_iffFor n ≥ 10, u and v are adjacent in C_n^3 iff v = u + e for an integer e with 0 < |e| ≤ 3.
- zmod_intCast_eq_intCast_iff_of_abs_sub_ltTwo integers a, b with |a − b| < n are equal modulo n only if they are equal.
- fin_three_false_of_four_pairwise_neFin 3 has no four pairwise distinct elements.
- Used by 1
- simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvdFor every n ≥ 10 not divisible by 4, the cube C_n^3 of the n-cycle cannot be covered by 3 equivalence subgraphs; with the lower bound eq ≥…
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$.
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.
uses
fin_three_false_of_four_pairwise_ne,fin_three_not_forall_eq_or_eq,fin_three_eq_of_five_nehave 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
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'`.
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
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$.
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⟩
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`.
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
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)$.
-- 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]
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.
uses
abs_lehave 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 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}$.
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
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.
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
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.
uses
abs_lehave 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
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`.
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
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`).
uses
not_nothave 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]
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.
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
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.
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⟩
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$.
uses
Ne.symmhave 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⟩
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`).
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
$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$.
uses
Nat.even_or_oddrcases 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.
- Automated tactics (`omega`, `norm_num`, `ring`, and `tauto`) discharge several routine integer arithmetic inequalities and propositional combinations throughout the proof, particularly when verifying that relative offsets between windows lie within the allowable range $[-3, 3]$.
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.
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]