circulant_1_3_three_colorable
For every integer n ≥ 8, the circulant graph C_n(1,3) has a proper vertex 3-colouring, so N_3(C_n(1,3)) > 0.
Statement
theorem circulant_1_3_three_colorable (n : ℕ) [NeZero n] (hn : 8 ≤ n) :
0 < Fintype.card ((circulant_1_3 n).Coloring (Fin 3))- Formalizes
- arXiv:2610.41820 Section 2.3
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- circulant_1_3The 4-regular circulant graph C_n(1,3) on vertex set ZMod n with connection set {1, -1, 3, -3}.
Read back from the Lean
For every natural number $n$ such that $n \neq 0$ (via [NeZero n]) and $8 \le n$, the number of valid 3-colorings (with colors in Fin 3) of the circulant graph circulant_1_3 n is strictly greater than 0 (i.e., the graph admits at least one proper 3-coloring).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the circulant graph C_n(1,3) is 3-colourable for all n ≥ 8, the proof first reduces proper colouring to verifying that adjacent vertices along steps of length 1 and 3 receive distinct colours. When n is even, projecting ℤ/nℤ onto ℤ/2ℤ yields a 2-colouring that alternates parity, which immediately handles steps of length 1 and 3 since both numbers are odd. When n is odd (hence n ≥ 9), an explicit 3-colouring is constructed by alternating colours 0 and 1 along the cycle and patching the last five positions with the sequence (2, 1, 2, 0, 2), which prevents monochromatic edges at the boundaries for both step 1 and step 3.
Any vertex assignment f : ℤ/nℤ → Fin 3 satisfying f(u) ≠ f(u + 1) and f(u) ≠ f(u + 3) for all u defines a proper 3-colouring of C_n(1,3).
By definition of the circulant graph C_n(1,3), vertices u and v are adjacent if and only if u ≠ v and their difference u - v or v - u belongs to {1, -1, 3, -3}. In each of the resulting eight cases, one vertex is obtained from the other by adding 1 or 3. The step hypotheses ensure that f(u) ≠ f(v), so adjacent vertices always receive distinct colours.
uses
SimpleGraph.circulantGraph_adj,Set.mem_insert_iff,Set.mem_singleton_iffrefine ⟨f, ?_⟩ intro u v huv simp only [circulant_1_3, SimpleGraph.circulantGraph_adj, Set.mem_insert_iff, Set.mem_singleton_iff] at huv rcases huv with ⟨hne, hstep⟩ rcases hstep with (h | h) <;> rcases h with (h | h | h | h) · have : u = v + 1 := by linear_combination h rw [this]; exact (h1 v).symm · have : v = u + 1 := by linear_combination -h rw [this]; exact h1 u · have : u = v + 3 := by linear_combination h rw [this]; exact (h3 v).symm · have : v = u + 3 := by linear_combination -h rw [this]; exact h3 u · have : v = u + 1 := by linear_combination h rw [this]; exact h1 u · have : u = v + 1 := by linear_combination -h rw [this]; exact (h1 v).symm · have : v = u + 3 := by linear_combination h rw [this]; exact h3 u · have : u = v + 3 := by linear_combination -h rw [this]; exact (h3 v).symm
When n is even, there exists a 3-colouring of ℤ/nℤ that differs under additions of 1 and 3.
Because 2 divides n, there is a canonical quotient ring homomorphism φ : ℤ/nℤ → ℤ/2ℤ. Composing φ with the inclusion Fin 2 ↪ Fin 3 gives a 3-colouring f. Since φ(u + 1) = φ(u) + 1 and φ(u + 3) = φ(u) + 3 = φ(u) + 1 in ℤ/2ℤ, and 1 ≠ 0 in ℤ/2ℤ, the colour must change under steps of length 1 or 3.
uses
ZMod.castHom,Fin.castLE_injective,map_add,map_ofNatlet phi : ZMod n →+* ZMod 2 := ZMod.castHom h2 (ZMod 2) let f : ZMod n → Fin 3 := fun u => (phi u).castLE (by decide) have hinj : Function.Injective (Fin.castLE (by decide : 2 ≤ 3)) := Fin.castLE_injective (by decide) refine ⟨f, ?_, ?_⟩ · intro u hu apply hinj at hu have h1 : phi (u + 1) = phi u + 1 := by simp have hne : phi (u + 1) ≠ phi u := by rw [h1] intro heq have : (1 : ZMod 2) = 0 := by calc (1 : ZMod 2) = (phi u + 1) - phi u := by ring _ = phi u - phi u := by rw [heq] _ = 0 := by ring revert this; decide exact hne hu.symm · intro u hu apply hinj at hu have h3 : phi (u + 3) = phi u + 1 := by rw [map_add, map_ofNat] rw [show (3 : ZMod 2) = 1 by decide] have hne : phi (u + 3) ≠ phi u := by rw [h3] intro heq have : (1 : ZMod 2) = 0 := by calc (1 : ZMod 2) = (phi u + 1) - phi u := by ring _ = phi u - phi u := by rw [heq] _ = 0 := by ring revert this; decide exact hne hu.symm
The piecewise candidate colouring c(n, i) takes values strictly less than 3 for all indices i. automation
Unfolding the definition of c(n, i), the five patch values at n - 5 through n - 1 are explicitly 2, 1, 2, 0, and 2, while all other indices take the value i % 2 ∈ {0, 1}. In all branches, the value is strictly less than 3.
dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega
For odd n ≥ 9, the colouring values at index i and (i + 1) % n are distinct for all i < n.
The values of c(n, ·) are precomputed at 0 and at the boundary indices n - 6, ..., n - 1. If i < n - 6, then (i + 1) % n = i + 1 lies outside the patch, so the values are i % 2 and (i + 1) % 2, which differ by parity. If i ≥ n - 6, i is one of the six boundary values; checking each case against the precomputed patch values verifies that adjacent indices always have distinct colours.
uses
lt_or_ge,Nat.mod_eq_of_lt,Nat.mod_selfhave h0 : circulant_1_3_three_colorable_c_val n 0 = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn6 : circulant_1_3_three_colorable_c_val n (n - 6) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn5 : circulant_1_3_three_colorable_c_val n (n - 5) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn4 : circulant_1_3_three_colorable_c_val n (n - 4) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn3 : circulant_1_3_three_colorable_c_val n (n - 3) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn2 : circulant_1_3_three_colorable_c_val n (n - 2) = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn1 : circulant_1_3_three_colorable_c_val n (n - 1) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega rcases lt_or_ge i (n - 6) with hlt | hge · have hi1 : (i + 1) % n = i + 1 := Nat.mod_eq_of_lt (by omega) rw [hi1] have hci : circulant_1_3_three_colorable_c_val n i = i % 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hci1 : circulant_1_3_three_colorable_c_val n (i + 1) = (i + 1) % 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega rw [hci, hci1]; omega · have : i = n - 6 ∨ i = n - 5 ∨ i = n - 4 ∨ i = n - 3 ∨ i = n - 2 ∨ i = n - 1 := by omega rcases this with rfl | rfl | rfl | rfl | rfl | rfl · have : (n - 6 + 1) % n = n - 5 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn6, hn5]; decide · have : (n - 5 + 1) % n = n - 4 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn5, hn4]; decide · have : (n - 4 + 1) % n = n - 3 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn4, hn3]; decide · have : (n - 3 + 1) % n = n - 2 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn3, hn2]; decide · have : (n - 2 + 1) % n = n - 1 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn2, hn1]; decide · have : (n - 1 + 1) % n = 0 := by have : n - 1 + 1 = n := by omega rw [this, Nat.mod_self] rw [this, hn1, h0]; decide
For odd n ≥ 9, the colouring values at index i and (i + 3) % n are distinct for all i < n.
The values of c(n, ·) are precomputed at 0, 1, 2 and n - 8, ..., n - 1. For i < n - 8, both i and i + 3 lie outside the patch, so their colours are i % 2 and (i + 3) % 2, which differ because 3 is odd. For i ≥ n - 8, i is one of the eight boundary values; checking each transition explicitly, including wrap-around modulo n, verifies that the colours never match.
uses
lt_or_ge,Nat.mod_eq_of_lt,Nat.mod_self,Nat.add_mod_lefthave h0 : circulant_1_3_three_colorable_c_val n 0 = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have h1 : circulant_1_3_three_colorable_c_val n 1 = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have h2 : circulant_1_3_three_colorable_c_val n 2 = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn8 : circulant_1_3_three_colorable_c_val n (n - 8) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn7 : circulant_1_3_three_colorable_c_val n (n - 7) = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn6 : circulant_1_3_three_colorable_c_val n (n - 6) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn5 : circulant_1_3_three_colorable_c_val n (n - 5) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn4 : circulant_1_3_three_colorable_c_val n (n - 4) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn3 : circulant_1_3_three_colorable_c_val n (n - 3) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn2 : circulant_1_3_three_colorable_c_val n (n - 2) = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn1 : circulant_1_3_three_colorable_c_val n (n - 1) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega rcases lt_or_ge i (n - 8) with hlt | hge · have hi3 : (i + 3) % n = i + 3 := Nat.mod_eq_of_lt (by omega) rw [hi3] have hci : circulant_1_3_three_colorable_c_val n i = i % 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hci3 : circulant_1_3_three_colorable_c_val n (i + 3) = (i + 3) % 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega rw [hci, hci3]; omega · have : i = n - 8 ∨ i = n - 7 ∨ i = n - 6 ∨ i = n - 5 ∨ i = n - 4 ∨ i = n - 3 ∨ i = n - 2 ∨ i = n - 1 := by omega rcases this with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl · have : (n - 8 + 3) % n = n - 5 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn8, hn5]; decide · have : (n - 7 + 3) % n = n - 4 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn7, hn4]; decide · have : (n - 6 + 3) % n = n - 3 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn6, hn3]; decide · have : (n - 5 + 3) % n = n - 2 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn5, hn2]; decide · have : (n - 4 + 3) % n = n - 1 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn4, hn1]; decide · have : (n - 3 + 3) % n = 0 := by have : n - 3 + 3 = n := by omega rw [this, Nat.mod_self] rw [this, hn3, h0]; decide · have : (n - 2 + 3) % n = 1 := by have : n - 2 + 3 = n + 1 := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] rw [this, hn2, h1]; decide · have : (n - 1 + 3) % n = 2 := by have : n - 1 + 3 = n + 2 := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] rw [this, hn1, h2]; decide
For odd n ≥ 9, the lifted colouring on ℤ/nℤ satisfies f(u) ≠ f(u + 1) for all vertices u.
The representative of u + 1 in ℤ/nℤ is (u.val + 1) % n. If f(u) = f(u + 1), their underlying values would be equal, contradicting the step-1 difference property of c(n, ·).
uses
congrArg,Fin.val,ZMod.val_add,Nat.cast_one,ZMod.val_cast_of_lt,ZMod.val_lt,circulant_1_3_three_colorable_c_val_step1intro h have heq : circulant_1_3_three_colorable_c_val n u.val = circulant_1_3_three_colorable_c_val n (u + 1).val := congrArg Fin.val h have hu1 : (u + 1).val = (u.val + 1) % n := by have := ZMod.val_add u 1 have h1 : (1 : ZMod n).val = 1 := by rw [← Nat.cast_one, ZMod.val_cast_of_lt (by omega)] rw [h1] at this; exact this rw [hu1] at heq exact circulant_1_3_three_colorable_c_val_step1 n hn hodd u.val (ZMod.val_lt u) heq
For odd n ≥ 9, the lifted colouring on ℤ/nℤ satisfies f(u) ≠ f(u + 3) for all vertices u.
The representative of u + 3 in ℤ/nℤ is (u.val + 3) % n. Equality of colours would contradict the step-3 difference property of c(n, ·).
uses
congrArg,Fin.val,ZMod.val_add,ZMod.val_cast_of_lt,ZMod.val_lt,circulant_1_3_three_colorable_c_val_step3intro h have heq : circulant_1_3_three_colorable_c_val n u.val = circulant_1_3_three_colorable_c_val n (u + 3).val := congrArg Fin.val h have hu3 : (u + 3).val = (u.val + 3) % n := by have := ZMod.val_add u 3 have h3 : (3 : ZMod n).val = 3 := by rw [show (3 : ZMod n) = ((3 : ℕ) : ZMod n) by rfl, ZMod.val_cast_of_lt (by omega)] rw [h3] at this; exact this rw [hu3] at heq exact circulant_1_3_three_colorable_c_val_step3 n hn hodd u.val (ZMod.val_lt u) heq
For every n ≥ 8, the circulant graph C_n(1,3) has a proper 3-colouring, so N_3(C_n(1,3)) > 0.
Having positive cardinality of colourings is equivalent to nonemptiness. We split on the parity of n: if n is even, the mod-2 homomorphism gives a valid colouring; if n is odd, then n ≥ 9 and n % 2 = 1, so the patched colouring provides a valid colouring. In both cases, the step reduction ensures that the resulting colouring is proper.
uses
Fintype.card_pos_iff,circulant_1_3_three_colorable_even,circulant_1_3_three_colorable_coloring_of_steps,circulant_1_3_three_colorable_odd_step1,circulant_1_3_three_colorable_odd_step3rw [Fintype.card_pos_iff] by_cases h2 : 2 ∣ n · rcases circulant_1_3_three_colorable_even n h2 with ⟨f, h1, h3⟩ exact ⟨circulant_1_3_three_colorable_coloring_of_steps n f h1 h3⟩ · have hodd : n % 2 = 1 := by omega have hn9 : 9 ≤ n := by omega exact ⟨circulant_1_3_three_colorable_coloring_of_steps n (circulant_1_3_three_colorable_odd_fn n) (circulant_1_3_three_colorable_odd_step1 n hn9 hodd) (circulant_1_3_three_colorable_odd_step3 n hn9 hodd)⟩
SimpleGraph.circulantGraph_adj- In a circulant graph with generator set s, two vertices a and b are adjacent if and only if a ≠ b and either a - b ∈ s or b - a ∈ s.
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element belongs to the singleton {b} if and only if it equals b.
ZMod.castHom- The canonical ring homomorphism from ℤ/nℤ to a ring R of characteristic m when m divides n.
Fin.castLE_injective- The canonical embedding Fin m → Fin n for m ≤ n is injective.
map_add- A homomorphism preserves addition: f(x + y) = f(x) + f(y).
map_ofNat- A ring homomorphism preserves natural number numerals.
lt_or_ge- In any linear order, either a < b or b ≤ a.
Nat.mod_eq_of_lt- If a < b, then the remainder a % b is equal to a.
Nat.mod_self- For any natural number n, n % n = 0.
Nat.add_mod_left- Adding a multiple of x preserves the remainder modulo x: (x + z) % x = z % x.
congrArg- Applying a function to equal inputs yields equal outputs.
Fin.val- The underlying natural number value of an element of Fin n.
ZMod.val_add- The integer representative of a sum in ℤ/nℤ is (a.val + b.val) % n.
Nat.cast_one- The natural number 1 cast to a ring equals 1.
ZMod.val_cast_of_lt- If a < n, the integer representative of the cast of a into ℤ/nℤ is a.
ZMod.val_lt- The integer representative of any element of ℤ/nℤ is strictly less than n.
circulant_1_3_three_colorable_c_val_step1- For odd n ≥ 9, the coloring function c satisfies c(n, i) ≠ c(n, (i + 1) % n) for all i < n.
circulant_1_3_three_colorable_c_val_step3- For odd n ≥ 9, the coloring function c satisfies c(n, i) ≠ c(n, (i + 3) % n) for all i < n.
Fintype.card_pos_iff- A finite type has cardinality greater than zero if and only if it is nonempty.
circulant_1_3_three_colorable_even- When n is even, there exists a 3-colouring of ℤ/nℤ that changes value across steps of size 1 and 3.
circulant_1_3_three_colorable_coloring_of_steps- Any map f : ℤ/nℤ → Fin 3 satisfying f(u) ≠ f(u + 1) and f(u) ≠ f(u + 3) defines a proper 3-colouring of C_n(1,3).
circulant_1_3_three_colorable_odd_step1- For odd n ≥ 9, the induced coloring on ℤ/nℤ satisfies f(u) ≠ f(u + 1) for all u.
circulant_1_3_three_colorable_odd_step3- For odd n ≥ 9, the induced coloring on ℤ/nℤ satisfies f(u) ≠ f(u + 3) for all u.
- Steps 3, 4, and 5 rely on the omega and decide tactics to verify linear inequalities and finite case splits over the boundary indices of the patched coloring.
- In Lean, graph colourings are formalized as graph homomorphisms to the complete graph on the colour set, and the strictly positive count N_3(G) > 0 is represented as 0 < Fintype.card (G.Coloring (Fin 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 422 tactics.
def circulant_1_3_three_colorable_coloring_of_steps (n : ℕ) [NeZero n] (f : ZMod n → Fin 3) (h1 : ∀ u : ZMod n, f u ≠ f (u + 1)) (h3 : ∀ u : ZMod n, f u ≠ f (u + 3)) : (circulant_1_3 n).Coloring (Fin 3) := by refine ⟨f, ?_⟩ intro u v huv simp only [circulant_1_3, SimpleGraph.circulantGraph_adj, Set.mem_insert_iff, Set.mem_singleton_iff] at huv rcases huv with ⟨hne, hstep⟩ rcases hstep with (h | h) <;> rcases h with (h | h | h | h) · have : u = v + 1 := by linear_combination h rw [this]; exact (h1 v).symm · have : v = u + 1 := by linear_combination -h rw [this]; exact h1 u · have : u = v + 3 := by linear_combination h rw [this]; exact (h3 v).symm · have : v = u + 3 := by linear_combination -h rw [this]; exact h3 u · have : v = u + 1 := by linear_combination h rw [this]; exact h1 u · have : u = v + 1 := by linear_combination -h rw [this]; exact (h1 v).symm · have : v = u + 3 := by linear_combination h rw [this]; exact h3 u · have : u = v + 3 := by linear_combination -h rw [this]; exact (h3 v).symmtheorem circulant_1_3_three_colorable_even (n : ℕ) [NeZero n] (h2 : 2 ∣ n) : ∃ f : ZMod n → Fin 3, (∀ u, f u ≠ f (u + 1)) ∧ (∀ u, f u ≠ f (u + 3)) := by let phi : ZMod n →+* ZMod 2 := ZMod.castHom h2 (ZMod 2) let f : ZMod n → Fin 3 := fun u => (phi u).castLE (by decide) have hinj : Function.Injective (Fin.castLE (by decide : 2 ≤ 3)) := Fin.castLE_injective (by decide) refine ⟨f, ?_, ?_⟩ · intro u hu apply hinj at hu have h1 : phi (u + 1) = phi u + 1 := by simp have hne : phi (u + 1) ≠ phi u := by rw [h1] intro heq have : (1 : ZMod 2) = 0 := by calc (1 : ZMod 2) = (phi u + 1) - phi u := by ring _ = phi u - phi u := by rw [heq] _ = 0 := by ring revert this; decide exact hne hu.symm · intro u hu apply hinj at hu have h3 : phi (u + 3) = phi u + 1 := by rw [map_add, map_ofNat] rw [show (3 : ZMod 2) = 1 by decide] have hne : phi (u + 3) ≠ phi u := by rw [h3] intro heq have : (1 : ZMod 2) = 0 := by calc (1 : ZMod 2) = (phi u + 1) - phi u := by ring _ = phi u - phi u := by rw [heq] _ = 0 := by ring revert this; decide exact hne hu.symmdef circulant_1_3_three_colorable_c_val (n i : ℕ) : ℕ := if i = n - 5 then 2 else if i = n - 4 then 1 else if i = n - 3 then 2 else if i = n - 2 then 0 else if i = n - 1 then 2 else i % 2lemma circulant_1_3_three_colorable_c_val_lt (n i : ℕ) : circulant_1_3_three_colorable_c_val n i < 3 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omegalemma circulant_1_3_three_colorable_c_val_step1 (n : ℕ) (hn : 9 ≤ n) (hodd : n % 2 = 1) (i : ℕ) (hi : i < n) : circulant_1_3_three_colorable_c_val n i ≠ circulant_1_3_three_colorable_c_val n ((i + 1) % n) := by have h0 : circulant_1_3_three_colorable_c_val n 0 = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn6 : circulant_1_3_three_colorable_c_val n (n - 6) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn5 : circulant_1_3_three_colorable_c_val n (n - 5) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn4 : circulant_1_3_three_colorable_c_val n (n - 4) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn3 : circulant_1_3_three_colorable_c_val n (n - 3) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn2 : circulant_1_3_three_colorable_c_val n (n - 2) = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn1 : circulant_1_3_three_colorable_c_val n (n - 1) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega rcases lt_or_ge i (n - 6) with hlt | hge · have hi1 : (i + 1) % n = i + 1 := Nat.mod_eq_of_lt (by omega) rw [hi1] have hci : circulant_1_3_three_colorable_c_val n i = i % 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hci1 : circulant_1_3_three_colorable_c_val n (i + 1) = (i + 1) % 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega rw [hci, hci1]; omega · have : i = n - 6 ∨ i = n - 5 ∨ i = n - 4 ∨ i = n - 3 ∨ i = n - 2 ∨ i = n - 1 := by omega rcases this with rfl | rfl | rfl | rfl | rfl | rfl · have : (n - 6 + 1) % n = n - 5 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn6, hn5]; decide · have : (n - 5 + 1) % n = n - 4 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn5, hn4]; decide · have : (n - 4 + 1) % n = n - 3 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn4, hn3]; decide · have : (n - 3 + 1) % n = n - 2 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn3, hn2]; decide · have : (n - 2 + 1) % n = n - 1 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn2, hn1]; decide · have : (n - 1 + 1) % n = 0 := by have : n - 1 + 1 = n := by omega rw [this, Nat.mod_self] rw [this, hn1, h0]; decidelemma circulant_1_3_three_colorable_c_val_step3 (n : ℕ) (hn : 9 ≤ n) (hodd : n % 2 = 1) (i : ℕ) (hi : i < n) : circulant_1_3_three_colorable_c_val n i ≠ circulant_1_3_three_colorable_c_val n ((i + 3) % n) := by have h0 : circulant_1_3_three_colorable_c_val n 0 = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have h1 : circulant_1_3_three_colorable_c_val n 1 = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have h2 : circulant_1_3_three_colorable_c_val n 2 = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn8 : circulant_1_3_three_colorable_c_val n (n - 8) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn7 : circulant_1_3_three_colorable_c_val n (n - 7) = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn6 : circulant_1_3_three_colorable_c_val n (n - 6) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn5 : circulant_1_3_three_colorable_c_val n (n - 5) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn4 : circulant_1_3_three_colorable_c_val n (n - 4) = 1 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn3 : circulant_1_3_three_colorable_c_val n (n - 3) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn2 : circulant_1_3_three_colorable_c_val n (n - 2) = 0 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hn1 : circulant_1_3_three_colorable_c_val n (n - 1) = 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega rcases lt_or_ge i (n - 8) with hlt | hge · have hi3 : (i + 3) % n = i + 3 := Nat.mod_eq_of_lt (by omega) rw [hi3] have hci : circulant_1_3_three_colorable_c_val n i = i % 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega have hci3 : circulant_1_3_three_colorable_c_val n (i + 3) = (i + 3) % 2 := by dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega rw [hci, hci3]; omega · have : i = n - 8 ∨ i = n - 7 ∨ i = n - 6 ∨ i = n - 5 ∨ i = n - 4 ∨ i = n - 3 ∨ i = n - 2 ∨ i = n - 1 := by omega rcases this with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl · have : (n - 8 + 3) % n = n - 5 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn8, hn5]; decide · have : (n - 7 + 3) % n = n - 4 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn7, hn4]; decide · have : (n - 6 + 3) % n = n - 3 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn6, hn3]; decide · have : (n - 5 + 3) % n = n - 2 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn5, hn2]; decide · have : (n - 4 + 3) % n = n - 1 := by rw [Nat.mod_eq_of_lt (by omega)]; omega rw [this, hn4, hn1]; decide · have : (n - 3 + 3) % n = 0 := by have : n - 3 + 3 = n := by omega rw [this, Nat.mod_self] rw [this, hn3, h0]; decide · have : (n - 2 + 3) % n = 1 := by have : n - 2 + 3 = n + 1 := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] rw [this, hn2, h1]; decide · have : (n - 1 + 3) % n = 2 := by have : n - 1 + 3 = n + 2 := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] rw [this, hn1, h2]; decidedef circulant_1_3_three_colorable_odd_fn (n : ℕ) (u : ZMod n) : Fin 3 := ⟨circulant_1_3_three_colorable_c_val n u.val, circulant_1_3_three_colorable_c_val_lt n u.val⟩lemma circulant_1_3_three_colorable_odd_step1 (n : ℕ) [NeZero n] (hn : 9 ≤ n) (hodd : n % 2 = 1) (u : ZMod n) : circulant_1_3_three_colorable_odd_fn n u ≠ circulant_1_3_three_colorable_odd_fn n (u + 1) := by intro h have heq : circulant_1_3_three_colorable_c_val n u.val = circulant_1_3_three_colorable_c_val n (u + 1).val := congrArg Fin.val h have hu1 : (u + 1).val = (u.val + 1) % n := by have := ZMod.val_add u 1 have h1 : (1 : ZMod n).val = 1 := by rw [← Nat.cast_one, ZMod.val_cast_of_lt (by omega)] rw [h1] at this; exact this rw [hu1] at heq exact circulant_1_3_three_colorable_c_val_step1 n hn hodd u.val (ZMod.val_lt u) heqlemma circulant_1_3_three_colorable_odd_step3 (n : ℕ) [NeZero n] (hn : 9 ≤ n) (hodd : n % 2 = 1) (u : ZMod n) : circulant_1_3_three_colorable_odd_fn n u ≠ circulant_1_3_three_colorable_odd_fn n (u + 3) := by intro h have heq : circulant_1_3_three_colorable_c_val n u.val = circulant_1_3_three_colorable_c_val n (u + 3).val := congrArg Fin.val h have hu3 : (u + 3).val = (u.val + 3) % n := by have := ZMod.val_add u 3 have h3 : (3 : ZMod n).val = 3 := by rw [show (3 : ZMod n) = ((3 : ℕ) : ZMod n) by rfl, ZMod.val_cast_of_lt (by omega)] rw [h3] at this; exact this rw [hu3] at heq exact circulant_1_3_three_colorable_c_val_step3 n hn hodd u.val (ZMod.val_lt u) heq/-- Existence of proper 3-colourings for C_n(1,3) for every n ≥ 8. -/theorem circulant_1_3_three_colorable (n : ℕ) [NeZero n] (hn : 8 ≤ n) : 0 < Fintype.card ((circulant_1_3 n).Coloring (Fin 3)) := by rw [Fintype.card_pos_iff] by_cases h2 : 2 ∣ n · rcases circulant_1_3_three_colorable_even n h2 with ⟨f, h1, h3⟩ exact ⟨circulant_1_3_three_colorable_coloring_of_steps n f h1 h3⟩ · have hodd : n % 2 = 1 := by omega have hn9 : 9 ≤ n := by omega exact ⟨circulant_1_3_three_colorable_coloring_of_steps n (circulant_1_3_three_colorable_odd_fn n) (circulant_1_3_three_colorable_odd_step1 n hn9 hodd) (circulant_1_3_three_colorable_odd_step3 n hn9 hodd)⟩