AFTD Auto-Formalizing Theoretical Domains

group_is_dci

def

For 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 bijection f : G ≃ G such that for all x y : G, (x⁻¹ * y ∈ S ↔ (f x)⁻¹ * f y ∈ T) -- an isomorphism of the Cayley digraphs Cay(G,S) and Cay(G,T), where x → y is an arc when x⁻¹ * y lies in the connection set -- then there exists a group automorphism σ : G ≃* G with σ '' S = T (the image of S under σ is T).

Statement

def group_is_dci (G : Type*) [Group G] : Prop
Defined in
arXiv:2610.33692 (On the isomorphism problem of Cayley digraphs), Sec. 1, definition of a DCI-group
Verified
30 Oct 2026
Axioms
none listed
Used by 1

Read back from the Lean

For a group G, group_is_dci G asserts that for any two subsets S and T of G, if there exists a bijection f : G ≃ G such that for all x, y ∈ G, x⁻¹ * y ∈ S if and only if (f x)⁻¹ * f y ∈ T, then there exists a group automorphism σ : G ≃* G such that the image of S under σ is T (σ '' S = T).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- `G` is a DCI-group: whenever the Cayley digraphs `Cay(G,S)` and `Cay(G,T)` (arc `x → y` iff `x⁻¹ * y` lies in the connection set) are isomorphic via a bijection `f : G ≃ G`, some group automorphism `σ : G ≃* G` maps `S` onto `T`. -/
def group_is_dci (G : Type*) [Group G] : Prop :=
  ∀ S T : Set G, (∃ f : G ≃ G, ∀ x y : G, (x⁻¹ * y ∈ S ↔ (f x)⁻¹ * f y ∈ T)) →
    ∃ σ : G ≃* G, σ '' S = T
See it in the graphDiscuss this resultChallenge it