AFTD Auto-Formalizing Theoretical Domains

order_eight_hankel_not_circulant

theoremverified

Any simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} is not a circulant graph on ZMod 8.

Statement

theorem order_eight_hankel_not_circulant
    (G : SimpleGraph (ZMod 8))
    (hG : ∀ x y : ZMod 8, G.Adj x y ↔ (x + y).val = 1 ∨ (x + y).val = 3 ∨ (x + y).val = 5) :
    ¬ is_circulant_graph 8 G
Source
step towards exists_non_circulant_sharp_cyclic_graph_order_eight
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_circulant_graphA simple graph G on N vertices is circulant if it is isomorphic to the Cayley graph of ZMod N with respect to some connection set s.
Used by 1

The proof, explained

The Hankel graph on ZMod 8 with adjacency (x + y).val ∈ {1, 3, 5} connects only vertices of different parity, so reducing modulo 2 gives a proper 2-colouring. If this graph were isomorphic to a circulant graph, the neighborhood of 0 would determine a 3-element negation-closed circulant difference set T in ZMod 8 \ {0}, which must contain 4 and another nonzero element a ≠ 4. In the circulant graph, translation by any element of T must flip the 2-colouring, so translation by 2a must preserve it; but every residue a ∉ {0, 4} satisfies 2a = 4 or 4a = 4, which would force translation by 4 to preserve the colouring, contradicting that 4 ∈ T flips it.

  1. Define the reduction homomorphism from ZMod 8 to ZMod 2. automation

    The canonical reduction map is constructed using `ZMod.castHom`, with the divisibility condition 2 ∣ 8 verified by `norm_num`.

    lines 1–4

    uses ZMod.castHom

    /-- The reduction of `ZMod 8` modulo `2`, used as a 2-colouring of the Hankel graph. -/
    private def order_eight_hankel_not_circulant_cast : ZMod 8 →+* ZMod 2 :=
      ZMod.castHom (by norm_num) (ZMod 2)
    
  2. In ZMod 2, every element is its own additive inverse. automation

    Exhaustive evaluation by `decide` proves that x + x = 0 for all x ∈ ZMod 2.

    lines 5–8

    /-- In `ZMod 2` every element is its own negative. -/
    private lemma order_eight_hankel_not_circulant_zmod2_add_self :
        ∀ x : ZMod 2, x + x = 0 := by decide
    
  3. Any negation-closed 3-element subset of nonzero residues modulo 8 contains 4. automation

    Exhaustive search by `decide` verifies that every 3-element subset T ⊆ ZMod 8 that is closed under negation and avoids 0 contains 4.

    lines 9–13

    /-- A negation-closed set of three nonzero residues modulo 8 contains `4`. -/
    private lemma order_eight_hankel_not_circulant_four_mem :
        ∀ T : Finset (ZMod 8), T.card = 3 → (∀ t ∈ T, -t ∈ T) → (0 : ZMod 8) ∉ T →
          (4 : ZMod 8) ∈ T := by decide
    
  4. Any 3-element subset of ZMod 8 contains an element other than 4. automation

    Exhaustive evaluation by `decide` confirms that any subset of size 3 has an element distinct from 4.

    lines 14–17

    /-- A set of three residues modulo 8 has an element different from `4`. -/
    private lemma order_eight_hankel_not_circulant_exists_ne_four :
        ∀ T : Finset (ZMod 8), T.card = 3 → ∃ a ∈ T, a ≠ 4 := by decide
    
  5. Every residue modulo 8 other than 0 and 4 satisfies 2a = 4 or 4a = 4. automation

    Exhaustive evaluation by `decide` checks that each of the six nonzero residues other than 4 satisfies 2a = 4 or 4a = 4.

    lines 18–21

    /-- Every residue modulo 8 other than `0` and `4` satisfies `2a = 4` or `4a = 4`. -/
    private lemma order_eight_hankel_not_circulant_two_mul_or_four_mul :
        ∀ a : ZMod 8, a ≠ 0 → a ≠ 4 → 2 * a = 4 ∨ 4 * a = 4 := by decide
    
  6. In ZMod 2, two distinct elements differ by 1. automation

    Exhaustive evaluation by `decide` confirms that if y ≠ x in ZMod 2, then y = x + 1.

    lines 22–25

    /-- In `ZMod 2` two distinct elements differ by `1`. -/
    private lemma order_eight_hankel_not_circulant_zmod2_ne :
        ∀ x y : ZMod 2, y ≠ x → y = x + 1 := by decide
    
  7. In ZMod 2, adding 1 twice is the identity. automation

    Exhaustive evaluation by `decide` checks that x + 1 + 1 = x for all x ∈ ZMod 2.

    lines 26–29

    /-- In `ZMod 2` adding `1` twice is the identity. -/
    private lemma order_eight_hankel_not_circulant_zmod2_add_one_add_one :
        ∀ x : ZMod 2, x + 1 + 1 = x := by decide
    
  8. Assume for contradiction that G is a circulant graph on ZMod 8.

    We introduce the circulant connection set s ⊆ ZMod 8 and the graph isomorphism e : G ≃g circulantGraph s.

    lines 30–36

    /-- Any simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} is not a circulant graph on ZMod 8. -/
    theorem order_eight_hankel_not_circulant
        (G : SimpleGraph (ZMod 8))
        (hG : ∀ x y : ZMod 8, G.Adj x y ↔ (x + y).val = 1 ∨ (x + y).val = 3 ∨ (x + y).val = 5) :
        ¬ is_circulant_graph 8 G := by
      rintro ⟨s, ⟨e⟩⟩
      classical
  9. The reduction modulo 2 is a proper 2-colouring of G.

    Adjacency between x and y in G means that (x + y).val ∈ {1, 3, 5}, so x + y is odd. The canonical homomorphism modulo 2 maps odd residues to 1, so by `map_add` we have (x mod 2) + (y mod 2) = 1. If x and y had the same colour in ZMod 2, their sum would be 0 by `order_eight_hankel_not_circulant_zmod2_add_self`, contradicting `zero_ne_one`.

    lines 37–51

    uses map_add, order_eight_hankel_not_circulant_zmod2_add_self, zero_ne_one

      have hval : ∀ z : ZMod 8, (z.val = 1 ∨ z.val = 3 ∨ z.val = 5) ↔ (z = 1 ∨ z = 3 ∨ z = 5) := by
        decide
      have hcast1 : ∀ z : ZMod 8, (z.val = 1 ∨ z.val = 3 ∨ z.val = 5) →
          order_eight_hankel_not_circulant_cast z = 1 := by decide
      have hcolorG : ∀ x y : ZMod 8, G.Adj x y →
          order_eight_hankel_not_circulant_cast x ≠ order_eight_hankel_not_circulant_cast y := by
        intro x y hxy
        have hsum : order_eight_hankel_not_circulant_cast x +
            order_eight_hankel_not_circulant_cast y = 1 := by
          have h := hcast1 (x + y) ((hG x y).mp hxy)
          rwa [map_add] at h
        intro heq
        rw [heq] at hsum
        rw [order_eight_hankel_not_circulant_zmod2_add_self] at hsum
        exact zero_ne_one hsum
  10. The neighbors of 0 in G are precisely 1, 3, and 5.

    Since 0 + y = y by `zero_add`, the adjacency condition (0 + y).val ∈ {1, 3, 5} simplifies directly to y = 1 ∨ y = 3 ∨ y = 5.

    lines 52–56

    uses zero_add

      have hAdj0 : ∀ y : ZMod 8, G.Adj 0 y ↔ (y = 1 ∨ y = 3 ∨ y = 5) := by
        intro y
        have h := hG 0 y
        rw [zero_add] at h
        exact h.trans (hval y)
  11. Define the difference set T of the circulant graph.

    We define T as the set of all nonzero residues t such that t ∈ s or -t ∈ s. Characterizing membership in T unfolds Finset.filter over Finset.univ using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`.

    lines 57–60

    uses Finset.mem_filter, Finset.mem_univ, true_and

      let T : Finset (ZMod 8) := Finset.univ.filter (fun t => t ≠ 0 ∧ (t ∈ s ∨ -t ∈ s))
      have hTmem : ∀ t : ZMod 8, t ∈ T ↔ t ≠ 0 ∧ (t ∈ s ∨ -t ∈ s) := by
        intro t
        simp only [T, Finset.mem_filter, Finset.mem_univ, true_and]
  12. The neighbors of u = e 0 in the circulant graph are e 1, e 3, and e 5.

    Because e is a graph isomorphism, u is adjacent to w in the circulant graph iff 0 is adjacent to e.symm w in G. By `Equiv.apply_symm_apply` and the neighborhood of 0 in G, this holds iff e.symm w ∈ {1, 3, 5}, which by `Equiv.symm_apply_eq` means w ∈ {e 1, e 3, e 5}.

    lines 61–72

    uses Equiv.apply_symm_apply, Equiv.symm_apply_eq

      let u : ZMod 8 := e 0
      have hAdjU : ∀ w : ZMod 8,
          (SimpleGraph.circulantGraph s).Adj u w ↔ (w = e 1 ∨ w = e 3 ∨ w = e 5) := by
        intro w
        have key : (SimpleGraph.circulantGraph s).Adj (e 0) w ↔ G.Adj 0 (e.symm w) := by
          conv_lhs => rw [show w = e (e.symm w) from (Equiv.apply_symm_apply _ w).symm]
          exact e.map_adj_iff
        rw [show u = e 0 from rfl, key, hAdj0]
        have h1 : e.symm w = 1 ↔ w = e 1 := Equiv.symm_apply_eq e.toEquiv
        have h3 : e.symm w = 3 ↔ w = e 3 := Equiv.symm_apply_eq e.toEquiv
        have h5 : e.symm w = 5 ↔ w = e 5 := Equiv.symm_apply_eq e.toEquiv
        simp only [h1, h3, h5]
  13. In the circulant graph, u is adjacent to w if and only if w - u ∈ T.

    By the definition of circulant adjacency, u ~ w means u ≠ w and (u - w ∈ s ∨ w - u ∈ s). Rewriting u ≠ w via `sub_ne_zero` and `ne_comm` gives w - u ≠ 0, and rewriting u - w via `neg_sub` and `or_comm` gives w - u ∈ s ∨ -(w - u) ∈ s, which matches the definition of w - u ∈ T.

    lines 73–80

    uses sub_ne_zero, ne_comm, neg_sub, or_comm

      have hadj_iff : ∀ w : ZMod 8, (SimpleGraph.circulantGraph s).Adj u w ↔ w - u ∈ T := by
        intro w
        rw [hTmem]
        show u ≠ w ∧ (u - w ∈ s ∨ w - u ∈ s) ↔ w - u ≠ 0 ∧ (w - u ∈ s ∨ -(w - u) ∈ s)
        have hA : (u ≠ w) ↔ (w - u ≠ 0) := by rw [sub_ne_zero, ne_comm]
        have hB : (u - w ∈ s ∨ w - u ∈ s) ↔ (w - u ∈ s ∨ -(w - u) ∈ s) := by
          rw [neg_sub]; exact or_comm
        rw [hA, hB]
  14. The difference set T equals {e 1 - u, e 3 - u, e 5 - u}.

    An element t belongs to T iff u is adjacent to u + t (using `add_sub_cancel_left`), which means u + t ∈ {e 1, e 3, e 5}. Using `eq_sub_iff_add_eq'` and expanding finset membership via `Finset.mem_insert` and `Finset.mem_singleton`, this is equivalent to t being one of e 1 - u, e 3 - u, or e 5 - u.

    lines 81–87

    uses Finset.mem_insert, Finset.mem_singleton, add_sub_cancel_left, eq_sub_iff_add_eq'

      have hTeq : T = ({e 1 - u, e 3 - u, e 5 - u} : Finset (ZMod 8)) := by
        ext t
        rw [Finset.mem_insert, Finset.mem_insert, Finset.mem_singleton]
        have step1 : t ∈ T ↔ (SimpleGraph.circulantGraph s).Adj u (u + t) := by
          rw [hadj_iff (u + t), add_sub_cancel_left]
        rw [step1, hAdjU]
        simp only [eq_sub_iff_add_eq']
  15. The cardinality of T is 3.

    Since the isomorphism e is injective, the images e 1, e 3, and e 5 are pairwise distinct. Since subtraction is injective (`sub_left_inj.mp`), the three elements e 1 - u, e 3 - u, and e 5 - u are pairwise distinct, so T has exactly 3 elements.

    lines 88–102

    uses sub_left_inj.mp

      have hTcard : T.card = 3 := by
        rw [hTeq]
        have h13 : e 1 ≠ e 3 := by
          intro hh
          exact absurd (e.injective hh) (by decide)
        have h15 : e 1 ≠ e 5 := by
          intro hh
          exact absurd (e.injective hh) (by decide)
        have h35 : e 3 ≠ e 5 := by
          intro hh
          exact absurd (e.injective hh) (by decide)
        have h12 : e 1 - u ≠ e 3 - u := fun hh => h13 (sub_left_inj.mp hh)
        have h13' : e 1 - u ≠ e 5 - u := fun hh => h15 (sub_left_inj.mp hh)
        have h23 : e 3 - u ≠ e 5 - u := fun hh => h35 (sub_left_inj.mp hh)
        simp [h12, h13', h23]
  16. T is closed under negation, and 0 ∉ T.

    If t ∈ T, then t ≠ 0 and t ∈ s ∨ -t ∈ s. Then -t ≠ 0 by `neg_ne_zero`, and -t ∈ s ∨ -(-t) ∈ s holds symmetrically, so -t ∈ T. The condition 0 ∉ T is immediate from the definition of T.

    lines 103–113

    uses neg_ne_zero

      have hTneg : ∀ t : ZMod 8, t ∈ T → -t ∈ T := by
        intro t ht
        rw [hTmem] at ht ⊢
        obtain ⟨h0, hs⟩ := ht
        refine ⟨?_, ?_⟩
        · rwa [neg_ne_zero]
        · rcases hs with hs | hs
          · right; simpa using hs
          · left; exact hs
      have hT0 : (0 : ZMod 8) ∉ T := by
        rw [hTmem]; simp
  17. 4 ∈ T, and there exists an element a ∈ T with a ≠ 0 and a ≠ 4.

    By `order_eight_hankel_not_circulant_four_mem`, any negation-closed 3-element subset of nonzero residues modulo 8 must contain the unique element of order 2, which is 4. By `order_eight_hankel_not_circulant_exists_ne_four`, since |T| = 3, there exists an element a ∈ T distinct from 4, which is nonzero since 0 ∉ T.

    lines 114–117

    uses order_eight_hankel_not_circulant_four_mem, order_eight_hankel_not_circulant_exists_ne_four

      have h4 : (4 : ZMod 8) ∈ T :=
        order_eight_hankel_not_circulant_four_mem T hTcard hTneg hT0
      obtain ⟨a, haT, ha4⟩ := order_eight_hankel_not_circulant_exists_ne_four T hTcard
      have ha0 : a ≠ 0 := ((hTmem a).mp haT).1
  18. The pullback map F w = (e.symm w mod 2) is a proper 2-colouring of the circulant graph.

    If v is adjacent to w in the circulant graph, then their preimages e.symm v and e.symm w are adjacent in G under the isomorphism e. Since reduction modulo 2 is a proper 2-colouring of G, F v ≠ F w.

    lines 118–123

      let F : ZMod 8 → ZMod 2 := fun w => order_eight_hankel_not_circulant_cast (e.symm w)
      have hproper : ∀ v w : ZMod 8, (SimpleGraph.circulantGraph s).Adj v w → F v ≠ F w := by
        intro v w hv
        have hadj' : (SimpleGraph.circulantGraph s).Adj (e (e.symm v)) (e (e.symm w)) := by
          simpa using hv
        exact hcolorG (e.symm v) (e.symm w) ((e.map_adj_iff).mp hadj')
  19. Translating by any element of T inverts the colour F: in particular, F (w + 4) ≠ F w and F (w + a) ≠ F w.

    For any t ∈ T, w and w + t are adjacent in the circulant graph because (w + t) - w = t ∈ T (using `sub_self`). Since adjacent vertices must have different colours under F, F (w + t) ≠ F w by `Ne.symm`. Specializing to 4 and a gives the claims.

    lines 124–141

    uses sub_self, Ne.symm

      have hflip : ∀ t : ZMod 8, t ∈ T → ∀ w : ZMod 8, F (w + t) ≠ F w := by
        intro t ht w
        rw [hTmem] at ht
        obtain ⟨ht0, hts⟩ := ht
        have e1 : w - (w + t) = -t := by ring
        have e2 : w + t - w = t := by ring
        have hadj : (SimpleGraph.circulantGraph s).Adj w (w + t) := by
          show w ≠ w + t ∧ (w - (w + t) ∈ s ∨ w + t - w ∈ s)
          refine ⟨?_, ?_⟩
          · intro h
            apply ht0
            have h3 : w + t - w = 0 := by rw [← h, sub_self]
            rwa [e2] at h3
          · rw [e1, e2]
            exact hts.symm
        exact Ne.symm (hproper w (w + t) hadj)
      have hflip4 : ∀ w : ZMod 8, F (w + 4) ≠ F w := hflip 4 h4
      have hflipa : ∀ w : ZMod 8, F (w + a) ≠ F w := hflip a haT
  20. Translating by 2a preserves the colour: F (w + 2 * a) = F w for all w.

    In ZMod 2, two distinct elements differ by 1 (`order_eight_hankel_not_circulant_zmod2_ne`). Since shifting by a flips the colour at each step, shifting twice adds 1 twice, which is the identity in ZMod 2 by `order_eight_hankel_not_circulant_zmod2_add_one_add_one`.

    lines 142–151

    uses order_eight_hankel_not_circulant_zmod2_ne, order_eight_hankel_not_circulant_zmod2_add_one_add_one

      have hpres2 : ∀ w : ZMod 8, F (w + 2 * a) = F w := by
        intro w
        have h1 : F (w + a) ≠ F w := hflipa w
        have h2 : F (w + a + a) ≠ F (w + a) := hflipa (w + a)
        have hy : F (w + a) = F w + 1 := order_eight_hankel_not_circulant_zmod2_ne _ _ h1
        have hz : F (w + a + a) = F (w + a) + 1 := order_eight_hankel_not_circulant_zmod2_ne _ _ h2
        have harg : w + a + a = w + 2 * a := by ring
        rw [harg] at hz
        rw [hz, hy]
        exact order_eight_hankel_not_circulant_zmod2_add_one_add_one (F w)
  21. Both cases 2a = 4 and 4a = 4 contradict F (0 + 4) ≠ F 0.

    By `order_eight_hankel_not_circulant_two_mul_or_four_mul`, every residue a ∉ {0, 4} satisfies 2a = 4 or 4a = 4. If 2a = 4, then F (0 + 4) = F (0 + 2a) = F 0, which contradicts F (0 + 4) ≠ F 0. If 4a = 4, applying the colour-preserving shift by 2a twice yields F (0 + 4) = F (0 + 4a) = F 0, again contradicting F (0 + 4) ≠ F 0.

    lines 152–166

    uses order_eight_hankel_not_circulant_two_mul_or_four_mul

      have hab : 2 * a = 4 ∨ 4 * a = 4 :=
        order_eight_hankel_not_circulant_two_mul_or_four_mul a ha0 ha4
      rcases hab with h | h
      · have hp : F (0 + 4) = F 0 := by
          have hq := hpres2 0
          rwa [h] at hq
        exact hflip4 0 hp
      · have h4a : F (0 + 4 * a) = F 0 := by
          have hp1 := hpres2 0
          have hp2 := hpres2 (0 + 2 * a)
          have harg : (0 : ZMod 8) + 2 * a + 2 * a = 0 + 4 * a := by ring
          rw [harg] at hp2
          rw [hp2, hp1]
        rw [h] at h4a
        exact hflip4 0 h4a
ZMod.castHom
The canonical ring homomorphism from ZMod n to a ring of characteristic m, given that m divides n.
map_add
A group or ring homomorphism preserves addition: f(x + y) = f(x) + f(y).
order_eight_hankel_not_circulant_zmod2_add_self
In ZMod 2, every element is its own additive inverse: x + x = 0.
zero_ne_one
Zero is not equal to one.
zero_add
Zero is the additive identity: 0 + a = a.
Finset.mem_filter
An element belongs to Finset.filter p s if and only if it belongs to s and satisfies predicate p.
Finset.mem_univ
Every element of a finite type belongs to its universal finset Finset.univ.
true_and
True ∧ p is equivalent to p.
Equiv.apply_symm_apply
Applying an equivalence to its inverse image gives the identity: e (e.symm x) = x.
Equiv.symm_apply_eq
e.symm x = y is equivalent to x = e y.
sub_ne_zero
The difference a - b is nonzero if and only if a ≠ b.
ne_comm
Inequality is symmetric: a ≠ b ↔ b ≠ a.
neg_sub
Negating a difference reverses the order of subtraction: -(a - b) = b - a.
or_comm
Disjunction is commutative: a ∨ b ↔ b ∨ a.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
add_sub_cancel_left
Adding and subtracting the same element cancels: a + b - a = b.
eq_sub_iff_add_eq'
a = b - c is equivalent to c + a = b.
sub_left_inj.mp
Subtracting a fixed element is injective: if b - a = c - a then b = c.
neg_ne_zero
-a ≠ 0 is equivalent to a ≠ 0.
order_eight_hankel_not_circulant_four_mem
Any negation-closed 3-element subset of nonzero residues modulo 8 contains 4.
order_eight_hankel_not_circulant_exists_ne_four
Any 3-element subset of residues modulo 8 contains an element other than 4.
sub_self
Subtracting an element from itself gives zero: a - a = 0.
Ne.symm
Inequality is symmetric: a ≠ b implies b ≠ a.
order_eight_hankel_not_circulant_zmod2_ne
In ZMod 2, two distinct elements differ by 1: if y ≠ x then y = x + 1.
order_eight_hankel_not_circulant_zmod2_add_one_add_one
In ZMod 2, adding 1 twice is the identity: x + 1 + 1 = x.
order_eight_hankel_not_circulant_two_mul_or_four_mul
Every residue modulo 8 other than 0 and 4 satisfies 2a = 4 or 4a = 4.

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

/-- The reduction of `ZMod 8` modulo `2`, used as a 2-colouring of the Hankel graph. -/private def order_eight_hankel_not_circulant_cast : ZMod 8 →+* ZMod 2 :=  ZMod.castHom (by norm_num) (ZMod 2)/-- In `ZMod 2` every element is its own negative. -/private lemma order_eight_hankel_not_circulant_zmod2_add_self :    ∀ x : ZMod 2, x + x = 0 := by decide/-- A negation-closed set of three nonzero residues modulo 8 contains `4`. -/private lemma order_eight_hankel_not_circulant_four_mem :    ∀ T : Finset (ZMod 8), T.card = 3 → (∀ t ∈ T, -t ∈ T) → (0 : ZMod 8) ∉ T →      (4 : ZMod 8) ∈ T := by decide/-- A set of three residues modulo 8 has an element different from `4`. -/private lemma order_eight_hankel_not_circulant_exists_ne_four :    ∀ T : Finset (ZMod 8), T.card = 3 → ∃ a ∈ T, a ≠ 4 := by decide/-- Every residue modulo 8 other than `0` and `4` satisfies `2a = 4` or `4a = 4`. -/private lemma order_eight_hankel_not_circulant_two_mul_or_four_mul :    ∀ a : ZMod 8, a ≠ 0 → a ≠ 4 → 2 * a = 4 ∨ 4 * a = 4 := by decide/-- In `ZMod 2` two distinct elements differ by `1`. -/private lemma order_eight_hankel_not_circulant_zmod2_ne :    ∀ x y : ZMod 2, y ≠ x → y = x + 1 := by decide/-- In `ZMod 2` adding `1` twice is the identity. -/private lemma order_eight_hankel_not_circulant_zmod2_add_one_add_one :    ∀ x : ZMod 2, x + 1 + 1 = x := by decide/-- Any simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} is not a circulant graph on ZMod 8. -/theorem order_eight_hankel_not_circulant    (G : SimpleGraph (ZMod 8))    (hG : ∀ x y : ZMod 8, G.Adj x y ↔ (x + y).val = 1 ∨ (x + y).val = 3 ∨ (x + y).val = 5) :    ¬ is_circulant_graph 8 G := by  rintro ⟨s, ⟨e⟩⟩  classical  have hval : ∀ z : ZMod 8, (z.val = 1 ∨ z.val = 3 ∨ z.val = 5) ↔ (z = 1 ∨ z = 3 ∨ z = 5) := by    decide  have hcast1 : ∀ z : ZMod 8, (z.val = 1 ∨ z.val = 3 ∨ z.val = 5) →      order_eight_hankel_not_circulant_cast z = 1 := by decide  have hcolorG : ∀ x y : ZMod 8, G.Adj x y →      order_eight_hankel_not_circulant_cast x ≠ order_eight_hankel_not_circulant_cast y := by    intro x y hxy    have hsum : order_eight_hankel_not_circulant_cast x +        order_eight_hankel_not_circulant_cast y = 1 := by      have h := hcast1 (x + y) ((hG x y).mp hxy)      rwa [map_add] at h    intro heq    rw [heq] at hsum    rw [order_eight_hankel_not_circulant_zmod2_add_self] at hsum    exact zero_ne_one hsum  have hAdj0 : ∀ y : ZMod 8, G.Adj 0 y ↔ (y = 1 ∨ y = 3 ∨ y = 5) := by    intro y    have h := hG 0 y    rw [zero_add] at h    exact h.trans (hval y)  let T : Finset (ZMod 8) := Finset.univ.filter (fun t => t ≠ 0 ∧ (t ∈ s ∨ -t ∈ s))  have hTmem : ∀ t : ZMod 8, t ∈ T ↔ t ≠ 0 ∧ (t ∈ s ∨ -t ∈ s) := by    intro t    simp only [T, Finset.mem_filter, Finset.mem_univ, true_and]  let u : ZMod 8 := e 0  have hAdjU : ∀ w : ZMod 8,      (SimpleGraph.circulantGraph s).Adj u w ↔ (w = e 1 ∨ w = e 3 ∨ w = e 5) := by    intro w    have key : (SimpleGraph.circulantGraph s).Adj (e 0) w ↔ G.Adj 0 (e.symm w) := by      conv_lhs => rw [show w = e (e.symm w) from (Equiv.apply_symm_apply _ w).symm]      exact e.map_adj_iff    rw [show u = e 0 from rfl, key, hAdj0]    have h1 : e.symm w = 1 ↔ w = e 1 := Equiv.symm_apply_eq e.toEquiv    have h3 : e.symm w = 3 ↔ w = e 3 := Equiv.symm_apply_eq e.toEquiv    have h5 : e.symm w = 5 ↔ w = e 5 := Equiv.symm_apply_eq e.toEquiv    simp only [h1, h3, h5]  have hadj_iff : ∀ w : ZMod 8, (SimpleGraph.circulantGraph s).Adj u w ↔ w - u ∈ T := by    intro w    rw [hTmem]    show u ≠ w ∧ (u - w ∈ s ∨ w - u ∈ s) ↔ w - u ≠ 0 ∧ (w - u ∈ s ∨ -(w - u) ∈ s)    have hA : (u ≠ w) ↔ (w - u ≠ 0) := by rw [sub_ne_zero, ne_comm]    have hB : (u - w ∈ s ∨ w - u ∈ s) ↔ (w - u ∈ s ∨ -(w - u) ∈ s) := by      rw [neg_sub]; exact or_comm    rw [hA, hB]  have hTeq : T = ({e 1 - u, e 3 - u, e 5 - u} : Finset (ZMod 8)) := by    ext t    rw [Finset.mem_insert, Finset.mem_insert, Finset.mem_singleton]    have step1 : t ∈ T ↔ (SimpleGraph.circulantGraph s).Adj u (u + t) := by      rw [hadj_iff (u + t), add_sub_cancel_left]    rw [step1, hAdjU]    simp only [eq_sub_iff_add_eq']  have hTcard : T.card = 3 := by    rw [hTeq]    have h13 : e 1 ≠ e 3 := by      intro hh      exact absurd (e.injective hh) (by decide)    have h15 : e 1 ≠ e 5 := by      intro hh      exact absurd (e.injective hh) (by decide)    have h35 : e 3 ≠ e 5 := by      intro hh      exact absurd (e.injective hh) (by decide)    have h12 : e 1 - u ≠ e 3 - u := fun hh => h13 (sub_left_inj.mp hh)    have h13' : e 1 - u ≠ e 5 - u := fun hh => h15 (sub_left_inj.mp hh)    have h23 : e 3 - u ≠ e 5 - u := fun hh => h35 (sub_left_inj.mp hh)    simp [h12, h13', h23]  have hTneg : ∀ t : ZMod 8, t ∈ T → -t ∈ T := by    intro t ht    rw [hTmem] at ht ⊢    obtain ⟨h0, hs⟩ := ht    refine ⟨?_, ?_⟩    · rwa [neg_ne_zero]    · rcases hs with hs | hs      · right; simpa using hs      · left; exact hs  have hT0 : (0 : ZMod 8) ∉ T := by    rw [hTmem]; simp  have h4 : (4 : ZMod 8) ∈ T :=    order_eight_hankel_not_circulant_four_mem T hTcard hTneg hT0  obtain ⟨a, haT, ha4⟩ := order_eight_hankel_not_circulant_exists_ne_four T hTcard  have ha0 : a ≠ 0 := ((hTmem a).mp haT).1  let F : ZMod 8 → ZMod 2 := fun w => order_eight_hankel_not_circulant_cast (e.symm w)  have hproper : ∀ v w : ZMod 8, (SimpleGraph.circulantGraph s).Adj v w → F v ≠ F w := by    intro v w hv    have hadj' : (SimpleGraph.circulantGraph s).Adj (e (e.symm v)) (e (e.symm w)) := by      simpa using hv    exact hcolorG (e.symm v) (e.symm w) ((e.map_adj_iff).mp hadj')  have hflip : ∀ t : ZMod 8, t ∈ T → ∀ w : ZMod 8, F (w + t) ≠ F w := by    intro t ht w    rw [hTmem] at ht    obtain ⟨ht0, hts⟩ := ht    have e1 : w - (w + t) = -t := by ring    have e2 : w + t - w = t := by ring    have hadj : (SimpleGraph.circulantGraph s).Adj w (w + t) := by      show w ≠ w + t ∧ (w - (w + t) ∈ s ∨ w + t - w ∈ s)      refine ⟨?_, ?_⟩      · intro h        apply ht0        have h3 : w + t - w = 0 := by rw [← h, sub_self]        rwa [e2] at h3      · rw [e1, e2]        exact hts.symm    exact Ne.symm (hproper w (w + t) hadj)  have hflip4 : ∀ w : ZMod 8, F (w + 4) ≠ F w := hflip 4 h4  have hflipa : ∀ w : ZMod 8, F (w + a) ≠ F w := hflip a haT  have hpres2 : ∀ w : ZMod 8, F (w + 2 * a) = F w := by    intro w    have h1 : F (w + a) ≠ F w := hflipa w    have h2 : F (w + a + a) ≠ F (w + a) := hflipa (w + a)    have hy : F (w + a) = F w + 1 := order_eight_hankel_not_circulant_zmod2_ne _ _ h1    have hz : F (w + a + a) = F (w + a) + 1 := order_eight_hankel_not_circulant_zmod2_ne _ _ h2    have harg : w + a + a = w + 2 * a := by ring    rw [harg] at hz    rw [hz, hy]    exact order_eight_hankel_not_circulant_zmod2_add_one_add_one (F w)  have hab : 2 * a = 4 ∨ 4 * a = 4 :=    order_eight_hankel_not_circulant_two_mul_or_four_mul a ha0 ha4  rcases hab with h | h  · have hp : F (0 + 4) = F 0 := by      have hq := hpres2 0      rwa [h] at hq    exact hflip4 0 hp  · have h4a : F (0 + 4 * a) = F 0 := by      have hp1 := hpres2 0      have hp2 := hpres2 (0 + 2 * a)      have harg : (0 : ZMod 8) + 2 * a + 2 * a = 0 + 4 * a := by ring      rw [harg] at hp2      rw [hp2, hp1]    rw [h] at h4a    exact hflip4 0 h4a
See it in the graphDiscuss this resultChallenge it