AFTD Auto-Formalizing Theoretical Domains

cayley_table_graph_chromatic_number_le_card_of_complete_mapping

theoremverifiedformalization

If a finite group G admits a complete mapping, then the chromatic number of its Cayley table graph is at most |G|.

Statement

theorem cayley_table_graph_chromatic_number_le_card_of_complete_mapping
    (G : Type*) [Group G] [Fintype G] (θ : G → G) (hθ : group_is_complete_mapping θ) :
    (cayley_table_graph G).chromaticNumber ≤ Fintype.card G
Formalizes
arXiv:2611.13274 Theorem 2.10, Theorem 2.14
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 function $\theta : G \to G$, if $\theta$ is a complete mapping of $G$, then the chromatic number of the Cayley table graph of $G$ is less than or equal to the cardinality of $G$ (Fintype.card 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

The proof exhibits an explicit |G|-coloring of the Cayley table graph by coloring each cell (x, y) with (θ(x))⁻¹ * y ∈ G. To verify this coloring is proper, we show that adjacent cells cannot receive the same color. Adjacent cells share a row, a column, or a product value; in each case, assuming the colors match forces the cells to coincide using group cancellation, the injectivity of θ, or the bijectivity of x ↦ x * θ(x).

  1. Extract the properties of the complete mapping θ and define a candidate |G|-coloring of the Cayley table.

    By definition, the complete mapping θ and the map x ↦ x * θ(x) are both bijective. We define a coloring on the cells of the Cayley table by assigning each cell p = (x, y) to (θ(x))⁻¹ * y ∈ G, identified with an element of Fin(|G|) via `Fintype.equivFin G`.

    lines 5–7

    uses Fintype.equivFin

      obtain ⟨hθbij, hprod⟩ := hθ
      -- Color the cell (x, y) by (θ x)⁻¹ * y ∈ G.
      let color : G × G → Fin (Fintype.card G) := fun p => Fintype.equivFin G ((θ p.1)⁻¹ * p.2)
  2. Two cells that have the same color and the same Cayley table product must coincide.

    Suppose p = (p₁, p₂) and q = (q₁, q₂) satisfy (θ(p₁))⁻¹ * p₂ = (θ(q₁))⁻¹ * q₂ and p₁ * p₂ = q₁ * q₂. By group arithmetic, p₁ * θ(p₁) = (p₁ * p₂) * ((θ(p₁))⁻¹ * p₂)⁻¹, which equals q₁ * θ(q₁) by substituting the shared product and color. Because x ↦ x * θ(x) is injective, this implies p₁ = q₁. Then p₂ = θ(p₁) * ((θ(p₁))⁻¹ * p₂) = θ(q₁) * ((θ(q₁))⁻¹ * q₂) = q₂. Since both components agree, p = q by `Prod.ext`.

    lines 8–21

    uses Prod.ext

      -- Cells with the same color and the same product symbol coincide.
      have hkey : ∀ p q : G × G, (θ p.1)⁻¹ * p.2 = (θ q.1)⁻¹ * q.2 →
          p.1 * p.2 = q.1 * q.2 → p = q := by
        intro p q hc hp
        have h1 : p.1 * θ p.1 = q.1 * θ q.1 := by
          have e1 : p.1 * θ p.1 = p.1 * p.2 * ((θ p.1)⁻¹ * p.2)⁻¹ := by group
          have e2 : q.1 * θ q.1 = q.1 * q.2 * ((θ q.1)⁻¹ * q.2)⁻¹ := by group
          rw [e1, e2, hc, hp]
        have hx : p.1 = q.1 := hprod.injective h1
        have hy : p.2 = q.2 := by
          have e1 : p.2 = θ p.1 * ((θ p.1)⁻¹ * p.2) := by group
          have e2 : q.2 = θ q.1 * ((θ q.1)⁻¹ * q.2) := by group
          rw [e1, e2, hc, hx]
        exact Prod.ext hx hy
  3. To bound the chromatic number by |G|, it suffices to show that any two adjacent cells with the same color are equal, split across the three adjacency relations.

    By `SimpleGraph.Colorable.chromaticNumber_le`, constructing a proper |G|-coloring bounds the chromatic number by |G|. We assume for contradiction that adjacent cells u and v have the same color. Since adjacent vertices are distinct (u ≠ v), deriving u = v produces the contradiction. Equality of colors means (θ(u₁))⁻¹ * u₂ = (θ(v₁))⁻¹ * v₂ by injectivity of `Fintype.equivFin G`. By definition of the Cayley table graph, u and v are adjacent because they share a row (u₁ = v₁), share a column (u₂ = v₂), or share a product symbol (u₁ * u₂ = v₁ * v₂).

    lines 22–26

    uses SimpleGraph.Colorable.chromaticNumber_le, Fintype.equivFin

      refine SimpleGraph.Colorable.chromaticNumber_le ⟨⟨color, ?_⟩⟩
      intro u v hadj hcol
      apply hadj.1
      have hcu : (θ u.1)⁻¹ * u.2 = (θ v.1)⁻¹ * v.2 := (Fintype.equivFin G).injective hcol
      rcases hadj.2 with h | h | h
  4. Adjacent cells in the same row cannot share the same color.

    If u and v share a row, then u₁ = v₁. Expressing u₂ = θ(u₁) * ((θ(u₁))⁻¹ * u₂) and v₂ = θ(v₁) * ((θ(v₁))⁻¹ * v₂), substituting u₁ = v₁ and the equal color values yields u₂ = v₂. Combining the two coordinates via `Prod.ext` gives u = v.

    lines 27–32

    uses Prod.ext

      · -- common row: u.1 = v.1, cancel (θ u.1)⁻¹
        have hy : u.2 = v.2 := by
          have e1 : u.2 = θ u.1 * ((θ u.1)⁻¹ * u.2) := by group
          have e2 : v.2 = θ v.1 * ((θ v.1)⁻¹ * v.2) := by group
          rw [e1, e2, hcu, h]
        exact Prod.ext h hy
  5. Adjacent cells in the same column cannot share the same color.

    If u and v share a column, then u₂ = v₂. Substituting this into the color equation gives (θ(u₁))⁻¹ * u₂ = (θ(v₁))⁻¹ * u₂. Canceling u₂ on the right with `mul_right_cancel` yields (θ(u₁))⁻¹ = (θ(v₁))⁻¹. Inversion is injective (`inv_injective`) and θ is injective, so u₁ = v₁. Thus u = v by `Prod.ext`.

    lines 33–39

    uses mul_right_cancel, inv_injective, Prod.ext

      · -- common column: u.2 = v.2, cancel u.2 on the right, then use injectivity of θ
        have hx : u.1 = v.1 := by
          have h2 : (θ u.1)⁻¹ = (θ v.1)⁻¹ := by
            rw [← h] at hcu
            exact mul_right_cancel hcu
          exact hθbij.injective (inv_injective h2)
        exact Prod.ext hx h
  6. Adjacent cells with the same product symbol cannot share the same color, completing the proof.

    If u and v share a product symbol (u₁ * u₂ = v₁ * v₂), they share both color and product, so the key lemma established earlier directly yields u = v, finishing the last case.

    lines 40–41

      · -- common product symbol
        exact hkey u v hcu h
Fintype.equivFin
A bijection between any finite type α and `Fin (Fintype.card α)`.
Prod.ext
Two pairs (x₁, x₂) and (y₁, y₂) are equal if and only if x₁ = y₁ and x₂ = y₂.
SimpleGraph.Colorable.chromaticNumber_le
If a simple graph admits a proper n-coloring, then its chromatic number is at most n.
mul_right_cancel
Right multiplication in a group is cancellative: if a * b = c * b, then a = c.
inv_injective
Group inversion is injective: if x⁻¹ = y⁻¹, then x = 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

/-- A complete mapping yields a proper |G|-coloring of the Cayley table graph. -/theorem cayley_table_graph_chromatic_number_le_card_of_complete_mapping    (G : Type*) [Group G] [Fintype G] (θ : G → G) (hθ : group_is_complete_mapping θ) :    (cayley_table_graph G).chromaticNumber ≤ Fintype.card G := by  obtain ⟨hθbij, hprod⟩ := hθ  -- Color the cell (x, y) by (θ x)⁻¹ * y ∈ G.  let color : G × G → Fin (Fintype.card G) := fun p => Fintype.equivFin G ((θ p.1)⁻¹ * p.2)  -- Cells with the same color and the same product symbol coincide.  have hkey : ∀ p q : G × G, (θ p.1)⁻¹ * p.2 = (θ q.1)⁻¹ * q.2 →      p.1 * p.2 = q.1 * q.2 → p = q := by    intro p q hc hp    have h1 : p.1 * θ p.1 = q.1 * θ q.1 := by      have e1 : p.1 * θ p.1 = p.1 * p.2 * ((θ p.1)⁻¹ * p.2)⁻¹ := by group      have e2 : q.1 * θ q.1 = q.1 * q.2 * ((θ q.1)⁻¹ * q.2)⁻¹ := by group      rw [e1, e2, hc, hp]    have hx : p.1 = q.1 := hprod.injective h1    have hy : p.2 = q.2 := by      have e1 : p.2 = θ p.1 * ((θ p.1)⁻¹ * p.2) := by group      have e2 : q.2 = θ q.1 * ((θ q.1)⁻¹ * q.2) := by group      rw [e1, e2, hc, hx]    exact Prod.ext hx hy  refine SimpleGraph.Colorable.chromaticNumber_le ⟨⟨color, ?_⟩⟩  intro u v hadj hcol  apply hadj.1  have hcu : (θ u.1)⁻¹ * u.2 = (θ v.1)⁻¹ * v.2 := (Fintype.equivFin G).injective hcol  rcases hadj.2 with h | h | h  · -- common row: u.1 = v.1, cancel (θ u.1)⁻¹    have hy : u.2 = v.2 := by      have e1 : u.2 = θ u.1 * ((θ u.1)⁻¹ * u.2) := by group      have e2 : v.2 = θ v.1 * ((θ v.1)⁻¹ * v.2) := by group      rw [e1, e2, hcu, h]    exact Prod.ext h hy  · -- common column: u.2 = v.2, cancel u.2 on the right, then use injectivity of θ    have hx : u.1 = v.1 := by      have h2 : (θ u.1)⁻¹ = (θ v.1)⁻¹ := by        rw [← h] at hcu        exact mul_right_cancel hcu      exact hθbij.injective (inv_injective h2)    exact Prod.ext hx h  · -- common product symbol    exact hkey u v hcu h
See it in the graphDiscuss this resultChallenge it