AFTD Auto-Formalizing Theoretical Domains

cayley_table_graph_exists_complete_mapping_of_transversal

theoremverifiedformalization

If the Cayley table graph of a finite group G contains a transversal of cardinality |G|, then G admits a complete mapping.

Statement

theorem cayley_table_graph_exists_complete_mapping_of_transversal
    (G : Type*) [Group G] [Fintype G] (s : Finset (G × G))
    (hindep : (cayley_table_graph G).IsIndepSet (s : Set (G × G)))
    (hcard : s.card = Fintype.card G) :
    ∃ θ : G → G, group_is_complete_mapping θ
Formalizes
arXiv:2611.13274 Theorem 2.12
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • cayley_table_graphThe Latin square graph of the Cayley table of a magma G is the simple graph with vertex set G × G where two distinct vertices (g₁, h₁) and…
  • group_is_complete_mappingA complete mapping of a group G is a permutation θ of G such that x ↦ xθ(x) is also a permutation of G.
Used by 1

Read back from the Lean

For any finite group $G$ and any finite subset $s \subseteq G \times G$, if $s$ is an independent set in the Cayley table graph of $G$ and the cardinality of $s$ equals the cardinality of $G$, then there exists a complete mapping $\theta : G \to G$.

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

An independent set of size |G| in the Cayley table graph cannot contain two pairs that share a row, a column, or a Cayley table product. Because no two pairs share their first coordinate, the first projection maps the set injectively—and hence bijectively by cardinality—onto G, defining a function θ : G → G whose graph is the independent set. Since elements of the set cannot share a second coordinate or a product, both θ and x ↦ x * θ(x) are injective. On a finite group, injectivity implies bijectivity, so θ is a complete mapping.

  1. No two distinct pairs in s share their first coordinate.

    Let p and q be pairs in s with p.1 = q.1. Suppose for contradiction that p ≠ q. By definition of the Cayley table graph, two distinct vertices that agree on their first coordinate are adjacent. But s is an independent set, so no two vertices in s can be adjacent, a contradiction.

    lines 7–11

    uses Or.inl

      classical
      have hfst : ∀ p ∈ s, ∀ q ∈ s, p.1 = q.1 → p = q := by
        intro p hp q hq h
        by_contra hne
        exact hindep hp hq hne ⟨hne, Or.inl h⟩
  2. No two distinct pairs in s share their second coordinate.

    Similarly, suppose p, q ∈ s have p.2 = q.2 but p ≠ q. Then p and q are adjacent in the Cayley table graph because they share their second coordinate, which contradicts s being an independent set.

    lines 12–15

    uses Or.inr, Or.inl

      have hsnd : ∀ p ∈ s, ∀ q ∈ s, p.2 = q.2 → p = q := by
        intro p hp q hq h
        by_contra hne
        exact hindep hp hq hne ⟨hne, Or.inr (Or.inl h)⟩
  3. The projection of s onto the first coordinate is the whole group G.

    Because the first projection is injective on s, the cardinality of its image equals |s| = |G| by Finset.card_image_of_injOn. Since G is finite and the image has cardinality |G|, Finset.eq_univ_of_card implies the image is all of G.

    lines 16–20

    uses Finset.eq_univ_of_card, Finset.card_image_of_injOn

      have himg : s.image (fun p : G × G => p.1) = Finset.univ := by
        apply Finset.eq_univ_of_card
        rw [Finset.card_image_of_injOn, hcard]
        intro p hp q hq h
        exact hfst p hp q hq h
  4. Every x ∈ G appears as the first component of some pair in s.

    Since the image of the first projection is all of G, any given x ∈ G lies in this image. By definition of image (Finset.mem_image), there exists a pair p ∈ s whose first component is x, which means (x, p.2) ∈ s.

    lines 21–26

    uses Finset.mem_image

      have hex : ∀ x : G, ∃ y : G, (x, y) ∈ s := by
        intro x
        have : x ∈ s.image (fun p : G × G => p.1) := by rw [himg]; simp
        rw [Finset.mem_image] at this
        obtain ⟨p, hp, hpx⟩ := this
        exact ⟨p.2, by rw [← hpx]; exact hp⟩
  5. Defining θ(x) as the second component of the pair with first component x yields (x, θ(x)) ∈ s for every x ∈ G.

    We define θ(x) by choosing the witness y such that (x, y) ∈ s. Since such a y exists for every x, the dependent conditional evaluates via dif_pos to this chosen witness, guaranteeing that (x, θ(x)) ∈ s.

    lines 27–33

    uses dif_pos

      let θ : G → G := fun x => if h : ∃ y, (x, y) ∈ s then h.choose else 1
      have hmem : ∀ x : G, (x, θ x) ∈ s := by
        intro x
        have h := hex x
        simp only [θ]
        rw [dif_pos h]
        exact h.choose_spec
  6. The map θ is injective.

    Suppose θ(x) = θ(y). The pairs (x, θ(x)) and (y, θ(y)) both lie in s and share their second coordinate. Since pairs in s with equal second coordinates are identical, (x, θ(x)) = (y, θ(y)), and taking first components yields x = y.

    lines 34–40

      have hθinj : Function.Injective θ := by
        intro x y hxy
        have hp := hmem x
        have hq := hmem y
        have hpq : (x, θ x) = (y, θ y) := hsnd _ hp _ hq hxy
        have : (x, θ x).1 = (y, θ y).1 := by rw [hpq]
        simpa using this
  7. The map x ↦ x * θ(x) is injective.

    Suppose x * θ(x) = y * θ(y), and suppose for contradiction that x ≠ y. The pairs p = (x, θ(x)) and q = (y, θ(y)) are distinct elements of s whose products p.1 * p.2 and q.1 * q.2 are equal. By definition of the Cayley table graph, two distinct vertices with the same product are adjacent, which contradicts the independence of s. Hence x = y.

    lines 41–49

    uses Prod.ext_iff.mp, Or.inr

      have hψinj : Function.Injective (fun x => x * θ x) := by
        intro x y hxy
        by_contra hne
        have hp := hmem x
        have hq := hmem y
        have hpq : (x, θ x) ≠ (y, θ y) := by
          intro h
          exact hne (Prod.ext_iff.mp h).1
        exact hindep hp hq hpq ⟨hpq, Or.inr (Or.inr hxy)⟩
  8. θ is a complete mapping of G.

    A complete mapping is a bijection θ such that x ↦ x * θ(x) is also a bijection. On a finite set, injectivity implies bijectivity; since both θ and x ↦ x * θ(x) are injective, both are bijections, completing the proof.

    line 50

      refine ⟨θ, hθinj.bijective_of_finite, hψinj.bijective_of_finite⟩
Or.inl
If a proposition a holds, then the disjunction a ∨ b holds.
Or.inr
If a proposition b holds, then the disjunction a ∨ b holds.
Finset.eq_univ_of_card
A subset of a finite type whose cardinality equals the cardinality of the type is the universal set.
Finset.card_image_of_injOn
If a function is injective on a finite set, the cardinality of its image equals the cardinality of the set.
Finset.mem_image
An element belongs to the image of a finite set under a function if and only if it is the image of some element in that set.
dif_pos
When the condition c is true, a dependent if-then-else expression evaluates to its then-branch.
Prod.ext_iff.mp
If two ordered pairs are equal, their first components are equal and their second components are equal.

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

/-- A transversal of cardinality |G| in the Cayley table graph gives a complete mapping of G. -/theorem cayley_table_graph_exists_complete_mapping_of_transversal    (G : Type*) [Group G] [Fintype G] (s : Finset (G × G))    (hindep : (cayley_table_graph G).IsIndepSet (s : Set (G × G)))    (hcard : s.card = Fintype.card G) :    ∃ θ : G → G, group_is_complete_mapping θ := by  classical  have hfst : ∀ p ∈ s, ∀ q ∈ s, p.1 = q.1 → p = q := by    intro p hp q hq h    by_contra hne    exact hindep hp hq hne ⟨hne, Or.inl h⟩  have hsnd : ∀ p ∈ s, ∀ q ∈ s, p.2 = q.2 → p = q := by    intro p hp q hq h    by_contra hne    exact hindep hp hq hne ⟨hne, Or.inr (Or.inl h)⟩  have himg : s.image (fun p : G × G => p.1) = Finset.univ := by    apply Finset.eq_univ_of_card    rw [Finset.card_image_of_injOn, hcard]    intro p hp q hq h    exact hfst p hp q hq h  have hex : ∀ x : G, ∃ y : G, (x, y) ∈ s := by    intro x    have : x ∈ s.image (fun p : G × G => p.1) := by rw [himg]; simp    rw [Finset.mem_image] at this    obtain ⟨p, hp, hpx⟩ := this    exact ⟨p.2, by rw [← hpx]; exact hp⟩  let θ : G → G := fun x => if h : ∃ y, (x, y) ∈ s then h.choose else 1  have hmem : ∀ x : G, (x, θ x) ∈ s := by    intro x    have h := hex x    simp only [θ]    rw [dif_pos h]    exact h.choose_spec  have hθinj : Function.Injective θ := by    intro x y hxy    have hp := hmem x    have hq := hmem y    have hpq : (x, θ x) = (y, θ y) := hsnd _ hp _ hq hxy    have : (x, θ x).1 = (y, θ y).1 := by rw [hpq]    simpa using this  have hψinj : Function.Injective (fun x => x * θ x) := by    intro x y hxy    by_contra hne    have hp := hmem x    have hq := hmem y    have hpq : (x, θ x) ≠ (y, θ y) := by      intro h      exact hne (Prod.ext_iff.mp h).1    exact hindep hp hq hpq ⟨hpq, Or.inr (Or.inr hxy)⟩  refine ⟨θ, hθinj.bijective_of_finite, hψinj.bijective_of_finite⟩
See it in the graphDiscuss this resultChallenge it