group_cayley_digraph_iso_of_mulEquiv
For any group G, subset S of G and group automorphism σ of G, the Cayley digraphs Cay(G,S) and Cay(G,σ(S)) are isomorphic: there is a bijection f : G ≃ G (namely σ) with x⁻¹ * y ∈ S iff (f x)⁻¹ * f y ∈ σ '' S for all x y.
Statement
theorem group_cayley_digraph_iso_of_mulEquiv {G : Type*} [Group G] (S : Set G) (σ : G ≃* G) : ∃ f : G ≃ G, ∀ x y : G, (x⁻¹ * y ∈ S ↔ (f x)⁻¹ * f y ∈ σ '' S)
- Source
- arXiv:2610.33692, Sec. 1 (the obvious direction of the DCI property)
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- group_is_dciFor a group G (any type with a Group instance; G explicit), group_is_dci G is the Prop: for all subsets S T : Set G, if there exists a…
The proof, explained
The proof exhibits the underlying bijection of the group automorphism σ as the digraph isomorphism. Because σ is a group homomorphism, (σ x)⁻¹ * σ y equals σ (x⁻¹ * y). Because σ is injective, an element x⁻¹ * y belongs to S if and only if its image σ (x⁻¹ * y) belongs to the image subset σ '' S.
The underlying equivalence of σ serves as the candidate bijection, reducing the goal to showing that for all x, y ∈ G, x⁻¹ * y ∈ S ↔ (σ x)⁻¹ * σ y ∈ σ '' S.
We provide the underlying bijection σ.toEquiv of the group automorphism σ as the witness for the existential quantifier, and introduce arbitrary vertices x, y ∈ G.
refine ⟨σ.toEquiv, fun x y => ?_⟩
The adjacency condition in the target Cayley graph, (σ x)⁻¹ * σ y ∈ σ '' S, is equivalent to σ (x⁻¹ * y) ∈ σ '' S.
After simplifying the coercions from the equivalence to the function σ, we rewrite using the homomorphism properties of σ: it preserves inverses ((σ x)⁻¹ = σ (x⁻¹)) and products (σ (x⁻¹) * σ y = σ (x⁻¹ * y)).
uses
MulEquiv.toEquiv_eq_coe,EquivLike.coe_coe,map_inv,map_mulsimp only [MulEquiv.toEquiv_eq_coe, EquivLike.coe_coe] rw [← map_inv, ← map_mul]
The equivalence x⁻¹ * y ∈ S ↔ σ (x⁻¹ * y) ∈ σ '' S holds, which completes the proof.
Because σ is an automorphism, it is an injective map. For any injective map and subset S, an element z lies in S if and only if σ z lies in the image σ '' S. Applying this to z = x⁻¹ * y yields the required equivalence.
exact σ.injective.mem_set_image.symm
MulEquiv.toEquiv_eq_coe- The underlying equivalence of a multiplicative equivalence equals its coercion to an equivalence: f.toEquiv = ↑f.
EquivLike.coe_coe- Coercing an equivalence-like map to an equivalence and then to a function is the same as coercing it directly to a function: ⇑↑e = ⇑e.
map_inv- A group homomorphism preserves inverses: f (a⁻¹) = (f a)⁻¹.
map_mul- A homomorphism preserves products: f (x * y) = f x * f y.
- Line 4 is a formal detail that simplifies coercions between multiplicative equivalences, plain equivalences, and functions, which has no mathematical content on paper.
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.
theorem group_cayley_digraph_iso_of_mulEquiv {G : Type*} [Group G] (S : Set G) (σ : G ≃* G) : ∃ f : G ≃ G, ∀ x y : G, (x⁻¹ * y ∈ S ↔ (f x)⁻¹ * f y ∈ σ '' S) := by refine ⟨σ.toEquiv, fun x y => ?_⟩ simp only [MulEquiv.toEquiv_eq_coe, EquivLike.coe_coe] rw [← map_inv, ← map_mul] exact σ.injective.mem_set_image.symm