exists_non_circulant_sharp_cyclic_graph_order_eight
There 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.
Statement
theorem exists_non_circulant_sharp_cyclic_graph_order_eight :
∃ (G : SimpleGraph (ZMod 8)) (_ : DecidableRel G.Adj),
(∃ u v, G.Adj u v) ∧ admits_sharp_cyclic_labeling 8 G ∧ ¬ is_circulant_graph 8 G- Related work
- arXiv:2610.31807 Question 12.1
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- admits_sharp_cyclic_labelingA simple graph G on N vertices admits a sharp cyclic labeling if there exists a bijection π from ZMod N to V(G) such that…
- 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.
- order_eight_hankel_admits_sharp_cyclic_labelingAny simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} admits a sharp cyclic labeling.
- order_eight_hankel_not_circulantAny simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} is not a circulant graph on ZMod 8.
Read back from the Lean
There exists a simple graph $G$ on the vertex set $\mathbb{Z}/8\mathbb{Z}$ equipped with a decidability instance for its adjacency relation such that: 1. $G$ has at least one edge (there exist vertices $u, v \in \mathbb{Z}/8\mathbb{Z}$ such that $G\text{.Adj } u\ v$); 2. $G$ admits a sharp cyclic labeling of order 8; and 3. $G$ is not a circulant graph of order 8 (it is not isomorphic to any circulant graph on $\mathbb{Z}/8\mathbb{Z}$).
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
The theorem is established by providing an explicit witness: a Hankel-type graph on ZMod 8 where vertices x and y are adjacent if and only if (x + y).val ∈ {1, 3, 5}. Symmetry is immediate from the commutativity of addition in ZMod 8, while looplessness holds because 2x mod 8 is always even and thus never 1, 3, or 5. The graph has at least one edge (such as {0, 1}), and two existing theorems confirm that it admits a sharp cyclic labeling and is not a circulant graph.
The Hankel-type adjacency relation on ZMod 8, defined by x ~ y iff (x + y).val ∈ {1, 3, 5}, is symmetric.
We define the adjacency relation on ZMod 8 by requiring (x + y).val to be 1, 3, or 5. Symmetry of the relation (x ~ y ↔ y ~ x) follows immediately from the commutativity of addition (add_comm) in ZMod 8.
uses
SimpleGraph.mk,add_comm/-- The Hankel-type adjacency relation on `ZMod 8`: `x ~ y` iff `(x + y).val ∈ {1, 3, 5}`. -/ private abbrev exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel (x y : ZMod 8) : Prop := (x + y).val = 1 ∨ (x + y).val = 3 ∨ (x + y).val = 5 /-- The Hankel-type non-circulant graph on `ZMod 8` witnessing the statement. -/ private abbrev exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph : SimpleGraph (ZMod 8) := SimpleGraph.mk exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel ⟨fun x y h => by simpa only [exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel, add_comm] using h⟩
The Hankel adjacency relation is irreflexive, defining a simple graph on ZMod 8.
A loop would mean (x + x).val ∈ {1, 3, 5}. But x + x = 2x in ZMod 8, so (2x).val is always an even number in {0, 2, 4, 6} and cannot be 1, 3, or 5. Exhaustive evaluation over all 8 elements of ZMod 8 is carried out by decide to establish irreflexivity.
⟨fun x h => (by decide : ∀ x : ZMod 8, ¬ exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel x x) x h⟩
Adjacency in the Hankel-type graph is decidable.
Unfolding the definition of the Hankel adjacency relation expresses it as a disjunction of equalities between natural numbers. Typeclass inference (infer_instance) synthesizes the Decidable instance from the decidability of equality on ℕ and boolean operations.
/-- The Hankel-type graph has decidable adjacency. -/ private instance exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph_inst : DecidableRel exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph.Adj := fun x y => (by unfold exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel; infer_instance : Decidable (exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel x y))
There exists a simple graph on ZMod 8 with at least one edge that admits a sharp cyclic labeling and is not circulant.
We supply the Hankel-type graph and its decidability instance as the witness. The graph contains at least one edge because 0 and 1 are adjacent (since (0 + 1).val = 1 ∈ {1, 3, 5}, checked by decide). Finally, the previously established theorems order_eight_hankel_admits_sharp_cyclic_labeling and order_eight_hankel_not_circulant show that this graph admits a sharp cyclic labeling and is not circulant, respectively, using Iff.rfl to identify the graph's adjacency relation with the Hankel condition.
uses
order_eight_hankel_admits_sharp_cyclic_labeling,order_eight_hankel_not_circulant,Iff.rfl/-- There exists a simple graph on 8 vertices with at least one edge that admits a sharp cyclic labeling and is not circulant. -/ theorem exists_non_circulant_sharp_cyclic_graph_order_eight : ∃ (G : SimpleGraph (ZMod 8)) (_ : DecidableRel G.Adj), (∃ u v, G.Adj u v) ∧ admits_sharp_cyclic_labeling 8 G ∧ ¬ is_circulant_graph 8 G := ⟨exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph, exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph_inst, ⟨0, 1, by decide⟩, order_eight_hankel_admits_sharp_cyclic_labeling exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph (fun _ _ => Iff.rfl), order_eight_hankel_not_circulant exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph (fun _ _ => Iff.rfl)⟩
SimpleGraph.mk- Constructs a simple graph on a vertex type V from an adjacency relation, together with proofs that the relation is symmetric and irreflexive (loopless).
add_comm- Addition is commutative: a + b = b + a for all elements a, b.
order_eight_hankel_admits_sharp_cyclic_labeling- Any simple graph on ZMod 8 whose adjacency relation is (x + y).val ∈ {1, 3, 5} admits a sharp cyclic labeling.
order_eight_hankel_not_circulant- Any simple graph on ZMod 8 whose adjacency relation is (x + y).val ∈ {1, 3, 5} is not a circulant graph on ZMod 8.
Iff.rfl- Logical equivalence is reflexive: a ↔ a for every proposition a.
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 Hankel-type adjacency relation on `ZMod 8`: `x ~ y` iff `(x + y).val ∈ {1, 3, 5}`. -/private abbrev exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel (x y : ZMod 8) : Prop := (x + y).val = 1 ∨ (x + y).val = 3 ∨ (x + y).val = 5/-- The Hankel-type non-circulant graph on `ZMod 8` witnessing the statement. -/private abbrev exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph : SimpleGraph (ZMod 8) := SimpleGraph.mk exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel ⟨fun x y h => by simpa only [exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel, add_comm] using h⟩ ⟨fun x h => (by decide : ∀ x : ZMod 8, ¬ exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel x x) x h⟩/-- The Hankel-type graph has decidable adjacency. -/private instance exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph_inst : DecidableRel exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph.Adj := fun x y => (by unfold exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel; infer_instance : Decidable (exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel x y))/-- There exists a simple graph on 8 vertices with at least one edge that admits a sharp cyclic labeling and is not circulant. -/theorem exists_non_circulant_sharp_cyclic_graph_order_eight : ∃ (G : SimpleGraph (ZMod 8)) (_ : DecidableRel G.Adj), (∃ u v, G.Adj u v) ∧ admits_sharp_cyclic_labeling 8 G ∧ ¬ is_circulant_graph 8 G := ⟨exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph, exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph_inst, ⟨0, 1, by decide⟩, order_eight_hankel_admits_sharp_cyclic_labeling exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph (fun _ _ => Iff.rfl), order_eight_hankel_not_circulant exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph (fun _ _ => Iff.rfl)⟩