AFTD Auto-Formalizing Theoretical Domains

circulant_1_3_three_colorable

theoremverifiedformalization

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.

  1. 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.

    lines 5–25

    uses SimpleGraph.circulantGraph_adj, Set.mem_insert_iff, Set.mem_singleton_iff

      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).symm
  2. 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.

    lines 29–58

    uses ZMod.castHom, Fin.castLE_injective, map_add, map_ofNat

      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.symm
  3. 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.

    line 69

      dsimp [circulant_1_3_three_colorable_c_val]; split_ifs <;> omega
  4. 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.

    lines 73–101

    uses lt_or_ge, Nat.mod_eq_of_lt, Nat.mod_self

      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]; decide
  5. 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.

    lines 105–145

    uses lt_or_ge, Nat.mod_eq_of_lt, Nat.mod_self, Nat.add_mod_left

      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]; decide
  6. 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, ·).

    lines 152–160

    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_step1

      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) heq
  7. 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, ·).

    lines 164–172

    uses congrArg, Fin.val, ZMod.val_add, ZMod.val_cast_of_lt, ZMod.val_lt, circulant_1_3_three_colorable_c_val_step3

      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
  8. 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.

    lines 177–184

    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_step3

      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)⟩
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.

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 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)⟩
See it in the graphDiscuss this resultChallenge it