order_eight_hankel_not_circulant
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
- exists_non_circulant_sharp_cyclic_graph_order_eightThere exists a simple graph G on ZMod 8 with at least one edge that admits a sharp cyclic labeling and is not a circulant graph on ZMod 8.
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.
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`.
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)
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.
/-- 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
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.
/-- 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
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.
/-- 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. automation
Exhaustive evaluation by `decide` checks that each of the six nonzero residues other than 4 satisfies 2a = 4 or 4a = 4.
/-- 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. automation
Exhaustive evaluation by `decide` confirms that if y ≠ x in ZMod 2, then y = x + 1.
/-- 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. automation
Exhaustive evaluation by `decide` checks that x + 1 + 1 = x for all x ∈ ZMod 2.
/-- 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
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.
/-- 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
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`.
uses
map_add,order_eight_hankel_not_circulant_zmod2_add_self,zero_ne_onehave 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
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.
uses
zero_addhave 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)
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`.
uses
Finset.mem_filter,Finset.mem_univ,true_andlet 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]
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}.
uses
Equiv.apply_symm_apply,Equiv.symm_apply_eqlet 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]
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.
uses
sub_ne_zero,ne_comm,neg_sub,or_commhave 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]
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.
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']
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.
uses
sub_left_inj.mphave 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]
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.
uses
neg_ne_zerohave 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
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.
uses
order_eight_hankel_not_circulant_four_mem,order_eight_hankel_not_circulant_exists_ne_fourhave 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
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.
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')
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.
uses
sub_self,Ne.symmhave 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
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`.
uses
order_eight_hankel_not_circulant_zmod2_ne,order_eight_hankel_not_circulant_zmod2_add_one_add_onehave 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)
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.
uses
order_eight_hankel_not_circulant_two_mul_or_four_mulhave 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.
- The preparatory lemmas on `ZMod 8` and `ZMod 2` are verified by exhaustive finite check using `decide`.
- The divisibility condition `2 ∣ 8` in the definition of the reduction homomorphism is closed by `norm_num`.
- Basic ring-algebraic simplifications in `ZMod 8` are handled by `ring`.
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.
/-- 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