AFTD Auto-Formalizing Theoretical Domains

group_cayley_digraph_iso_of_mulEquiv

theoremverified

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.

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

    line 3

      refine ⟨σ.toEquiv, fun x y => ?_⟩
  2. 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)).

    lines 4–5

    uses MulEquiv.toEquiv_eq_coe, EquivLike.coe_coe, map_inv, map_mul

      simp only [MulEquiv.toEquiv_eq_coe, EquivLike.coe_coe]
      rw [← map_inv, ← map_mul]
  3. 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.

    line 6

      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.

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

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