AFTD Auto-Formalizing Theoretical Domains

cayley_table_graph_quaternion_chromatic_number_ge

theoremverifiedformalization

For every integer n ≥ 1, the chromatic number of the Cayley table graph of the generalized quaternion group QuaternionGroup (2 * n + 1) is at least 8 * n + 6.

Statement

theorem cayley_table_graph_quaternion_chromatic_number_ge (n : ℕ) (hn : 1 ≤ n) :
    (8 * n + 6 : ℕ∞) ≤ (cayley_table_graph (QuaternionGroup (2 * n + 1))).chromaticNumber
Formalizes
arXiv:2611.13274 Sec. 6
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • quaternion_odd_has_no_complete_mappingFor every natural number n, the generalized quaternion group QuaternionGroup (2 * n + 1) has no complete mapping.
  • quaternion_group_cardFor every natural number n, the cardinality of the generalized quaternion group QuaternionGroup (2 * n + 1) is 8 * n + 4.

Read back from the Lean

For any natural number $n \ge 1$, the chromatic number of the Cayley table graph of the quaternion group $\mathrm{QuaternionGroup}(2n + 1)$ is at least $8n + 6$ (as an extended natural number in $\mathbb{N}_\infty$).

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 establishes that the chromatic number of the Cayley table graph of QuaternionGroup (2 * n + 1) is at least 8 * n + 6 using a counting argument on color classes. Any color class is an independent set in the graph, which corresponds to a partial transversal of the group's Cayley table. Because generalized quaternion groups of order 8 * n + 4 admit no complete mapping, no full transversal exists, bounding each color class to size at most 8 * n + 3. Summing across all m colors gives (8 * n + 4)² ≤ m * (8 * n + 3), which algebraically forces m ≥ 8 * n + 6.

  1. Any partial transversal S in the Cayley table has size at most 8 * n + 4.

    The group QuaternionGroup (2 * n + 1) has order 8 * n + 4 by quaternion_group_card. Because distinct pairs in S have distinct first coordinates (by hypothesis hS), the projection map (x, y) ↦ x is injective on S. Hence |S| equals the size of its image under this projection (Finset.card_image_of_injOn), which is at most the total number of elements in the group (Finset.card_le_univ).

    lines 9–17

    uses quaternion_group_card, Finset.card_image_of_injOn, Finset.card_le_univ

      have hcard : Fintype.card (QuaternionGroup (2 * n + 1)) = 8 * n + 4 := quaternion_group_card n
      have hinjfst : Set.InjOn (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => p.1) ↑S := by
        intro p hp q hq hpq
        by_contra hne
        exact (hS p hp q hq hne).1 hpq
      have hSle : S.card ≤ Fintype.card (QuaternionGroup (2 * n + 1)) := by
        calc S.card = (S.image (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => p.1)).card :=
              (Finset.card_image_of_injOn hinjfst).symm
          _ ≤ Fintype.card (QuaternionGroup (2 * n + 1)) := Finset.card_le_univ _
  2. No partial transversal S can achieve the maximum size 8 * n + 4.

    Suppose for contradiction that |S| = 8 * n + 4. Then the projection of S onto the first component covers the entire group (Finset.eq_univ_of_card), so every element x has some y such that (x, y) ∈ S. Choosing such a y for each x defines a function θ. Since pairs in S have pairwise distinct second components and pairwise distinct products, both θ and x ↦ x * θ(x) are injective. By Finite.injective_iff_surjective.1, both are bijections, meaning θ is a complete mapping on QuaternionGroup (2 * n + 1). This contradicts quaternion_odd_has_no_complete_mapping, which states that no such complete mapping exists.

    lines 18–50

    uses Finset.eq_univ_of_card, Finite.injective_iff_surjective.1, quaternion_odd_has_no_complete_mapping

      have key : S.card ≠ 8 * n + 4 := by
        intro hseq
        have huniv : S.image (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => p.1) = Finset.univ := by
          apply Finset.eq_univ_of_card
          rw [Finset.card_image_of_injOn hinjfst, hseq, hcard]
        have hex : ∀ x : QuaternionGroup (2 * n + 1), ∃ y, (x, y) ∈ S := by
          intro x
          have hx : x ∈ S.image (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => p.1) := by
            rw [huniv]; exact Finset.mem_univ x
          obtain ⟨p, hp, hpx⟩ := Finset.mem_image.1 hx
          exact ⟨p.2, by simpa [← hpx] using hp⟩
        let θ : QuaternionGroup (2 * n + 1) → QuaternionGroup (2 * n + 1) :=
          fun x => if h : ∃ y, (x, y) ∈ S then h.choose else 1
        have hθ : ∀ x : QuaternionGroup (2 * n + 1), (x, θ x) ∈ S := by
          intro x
          have h := hex x
          simp only [θ, dif_pos h]
          exact h.choose_spec
        have hne_pair : ∀ x y : QuaternionGroup (2 * n + 1), x ≠ y → (x, θ x) ≠ (y, θ y) := by
          intro x y hxy hcon
          exact hxy (by simpa using congrArg Prod.fst hcon)
        have hinj : Function.Injective θ := by
          intro x y hxy
          by_contra hne
          exact (hS _ (hθ x) _ (hθ y) (hne_pair x y hne)).2.1 hxy
        have hbijθ : Function.Bijective θ := ⟨hinj, Finite.injective_iff_surjective.1 hinj⟩
        have hinjmul : Function.Injective (fun x : QuaternionGroup (2 * n + 1) => x * θ x) := by
          intro x y hxy
          by_contra hne
          exact (hS _ (hθ x) _ (hθ y) (hne_pair x y hne)).2.2 hxy
        have hbijmul : Function.Bijective (fun x : QuaternionGroup (2 * n + 1) => x * θ x) :=
          ⟨hinjmul, Finite.injective_iff_surjective.1 hinjmul⟩
        exact quaternion_odd_has_no_complete_mapping n ⟨θ, hbijθ, hbijmul⟩
  3. Every partial transversal S has size at most 8 * n + 3.

    Since |S| ≤ 8 * n + 4 and |S| ≠ 8 * n + 4, linear integer arithmetic (omega) concludes |S| ≤ 8 * n + 3.

    line 51

      omega
  4. Each color class of a coloring C of the Cayley table graph has size at most 8 * n + 3.

    In the Cayley table graph, two distinct vertices (x, y) and (u, v) are connected by an edge if x = u, y = v, or x * y = u * v. In a valid graph coloring C, monochromatic vertices cannot be adjacent. Therefore, each color class (the fiber C⁻¹(i)) is a partial transversal, so cayley_table_graph_quaternion_chromatic_number_ge_pt_card_le applies to show its cardinality is at most 8 * n + 3.

    lines 58–73

    uses quaternion_group_card, cayley_table_graph_quaternion_chromatic_number_ge_pt_card_le

      have hcard : Fintype.card (QuaternionGroup (2 * n + 1)) = 8 * n + 4 := quaternion_group_card n
      have hfiber : ∀ i : Fin m,
          (Finset.univ.filter (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) =>
            C p = i)).card ≤ 8 * n + 3 := by
        intro i
        apply cayley_table_graph_quaternion_chromatic_number_ge_pt_card_le n
        intro p hp q hq hpq
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp hq
        have hCpq : C p = C q := by rw [hp, hq]
        refine ⟨?_, ?_, ?_⟩
        · intro h
          exact C.valid ⟨hpq, Or.inl h⟩ hCpq
        · intro h
          exact C.valid ⟨hpq, Or.inr (Or.inl h)⟩ hCpq
        · intro h
          exact C.valid ⟨hpq, Or.inr (Or.inr h)⟩ hCpq
  5. The total number of vertices (8 * n + 4)² is bounded above by m * (8 * n + 3).

    Partitioning the vertex set G × G into the m color classes of C, the sum of their cardinalities equals |G × G| = (8 * n + 4)² by Finset.card_eq_sum_card_fiberwise and Fintype.card_prod. Since each of the m color classes has size at most 8 * n + 3, the sum is bounded above by m * (8 * n + 3) using Finset.sum_le_sum and Finset.sum_const.

    lines 74–90

    uses Finset.card_eq_sum_card_fiberwise, Finset.sum_const, Fintype.card_prod, Finset.sum_le_sum

      have hsum : ∑ i : Fin m,
          (Finset.univ.filter (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) =>
            C p = i)).card
          = Fintype.card (QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1)) := by
        rw [← Finset.card_univ]
        exact (Finset.card_eq_sum_card_fiberwise (f := C) (s := Finset.univ) (t := Finset.univ)
          (fun x _ => Finset.mem_univ _)).symm
      have h2 : ∑ _i : Fin m, (8 * n + 3) = m * (8 * n + 3) := by
        simp [Finset.sum_const, Finset.card_univ]
      have hle : (8 * n + 4) * (8 * n + 4) ≤ m * (8 * n + 3) := by
        have hGF : Fintype.card (QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1))
            = (8 * n + 4) * (8 * n + 4) := by rw [Fintype.card_prod, hcard]
        calc (8 * n + 4) * (8 * n + 4)
            = Fintype.card (QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1)) := hGF.symm
          _ = ∑ i : Fin m, (Finset.univ.filter (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => C p = i)).card := hsum.symm
          _ ≤ ∑ _i : Fin m, (8 * n + 3) := Finset.sum_le_sum (fun i _ => hfiber i)
          _ = m * (8 * n + 3) := h2
  6. Every valid coloring must use at least 8 * n + 6 colors (m ≥ 8 * n + 6).

    The algebraic inequality (8 * n + 5) * (8 * n + 3) = (8 * n + 4)² - 1 < (8 * n + 4)² is proved by nlinarith. Chaining this with (8 * n + 4)² ≤ m * (8 * n + 3) via lt_of_lt_of_le yields (8 * n + 5) * (8 * n + 3) < m * (8 * n + 3). Dividing both sides by 8 * n + 3 using Nat.lt_of_mul_lt_mul_right gives 8 * n + 5 < m, and omega concludes 8 * n + 6 ≤ m.

    lines 91–93

    uses Nat.lt_of_mul_lt_mul_right, lt_of_lt_of_le

      have hlt : (8 * n + 5) * (8 * n + 3) < (8 * n + 4) * (8 * n + 4) := by nlinarith
      have h5 : 8 * n + 5 < m := Nat.lt_of_mul_lt_mul_right (lt_of_lt_of_le hlt hle)
      omega
  7. The chromatic number of the Cayley table graph is at least 8 * n + 6.

    By SimpleGraph.le_chromaticNumber_iff_colorable, showing that the chromatic number is at least 8 * n + 6 is equivalent to showing that any graph coloring with m colors satisfies m ≥ 8 * n + 6. Given any such coloring C, this bound is precisely established by cayley_table_graph_quaternion_chromatic_number_ge_colorable_bound.

    lines 98–102

    uses SimpleGraph.le_chromaticNumber_iff_colorable, cayley_table_graph_quaternion_chromatic_number_ge_colorable_bound

      rw [show (8 * ↑n + 6 : ℕ∞) = ((8 * n + 6 : ℕ) : ℕ∞) by push_cast; ring]
      rw [SimpleGraph.le_chromaticNumber_iff_colorable]
      intro m hm
      obtain ⟨C⟩ := hm
      exact cayley_table_graph_quaternion_chromatic_number_ge_colorable_bound n m C
quaternion_group_card
The generalized quaternion group QuaternionGroup (2 * n + 1) has cardinality 8 * n + 4.
Finset.card_image_of_injOn
If a function is injective on a finite set s, its image has the same cardinality as s.
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the cardinality of the type.
Finset.eq_univ_of_card
A finite subset of a finite type whose cardinality equals that of the type is the whole type (univ).
Finite.injective_iff_surjective.1
An injective function from a finite type to another of the same cardinality is surjective.
quaternion_odd_has_no_complete_mapping
The generalized quaternion group QuaternionGroup (2 * n + 1) admits no complete mapping.
cayley_table_graph_quaternion_chromatic_number_ge_pt_card_le
Every partial transversal of the Cayley table of QuaternionGroup (2 * n + 1) has size at most 8 * n + 3.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set equals the sum of the cardinalities of the fibers of any map on that set.
Finset.sum_const
The sum of a constant value over a finite set equals the size of the set multiplied by the constant.
Fintype.card_prod
The cardinality of the Cartesian product of two finite types is the product of their cardinalities.
Finset.sum_le_sum
If f(x) ≤ g(x) for all elements x in a finite set, then the sum of f is at most the sum of g.
Nat.lt_of_mul_lt_mul_right
For natural numbers, if b * a < c * a, then b < c.
lt_of_lt_of_le
If a < b and b ≤ c in a preorder, then a < c.
SimpleGraph.le_chromaticNumber_iff_colorable
The chromatic number of a graph is at least n if and only if every valid m-coloring satisfies n ≤ m.
cayley_table_graph_quaternion_chromatic_number_ge_colorable_bound
Every valid m-coloring of the Cayley table graph of QuaternionGroup (2 * n + 1) satisfies 8 * n + 6 ≤ m.

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

open scoped Classical/-- A color class of a coloring of the Cayley table graph is a partial transversal, so has at most`|G| - 1 = 8n + 3` cells (a full one would be a complete mapping). -/private lemma cayley_table_graph_quaternion_chromatic_number_ge_pt_card_le (n : ℕ)    (S : Finset (QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1)))    (hS : ∀ p ∈ S, ∀ q ∈ S, p ≠ q → p.1 ≠ q.1 ∧ p.2 ≠ q.2 ∧ p.1 * p.2 ≠ q.1 * q.2) :    S.card ≤ 8 * n + 3 := by  have hcard : Fintype.card (QuaternionGroup (2 * n + 1)) = 8 * n + 4 := quaternion_group_card n  have hinjfst : Set.InjOn (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => p.1) ↑S := by    intro p hp q hq hpq    by_contra hne    exact (hS p hp q hq hne).1 hpq  have hSle : S.card ≤ Fintype.card (QuaternionGroup (2 * n + 1)) := by    calc S.card = (S.image (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => p.1)).card :=          (Finset.card_image_of_injOn hinjfst).symm      _ ≤ Fintype.card (QuaternionGroup (2 * n + 1)) := Finset.card_le_univ _  have key : S.card ≠ 8 * n + 4 := by    intro hseq    have huniv : S.image (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => p.1) = Finset.univ := by      apply Finset.eq_univ_of_card      rw [Finset.card_image_of_injOn hinjfst, hseq, hcard]    have hex : ∀ x : QuaternionGroup (2 * n + 1), ∃ y, (x, y) ∈ S := by      intro x      have hx : x ∈ S.image (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => p.1) := by        rw [huniv]; exact Finset.mem_univ x      obtain ⟨p, hp, hpx⟩ := Finset.mem_image.1 hx      exact ⟨p.2, by simpa [← hpx] using hp⟩    let θ : QuaternionGroup (2 * n + 1) → QuaternionGroup (2 * n + 1) :=      fun x => if h : ∃ y, (x, y) ∈ S then h.choose else 1    have hθ : ∀ x : QuaternionGroup (2 * n + 1), (x, θ x) ∈ S := by      intro x      have h := hex x      simp only [θ, dif_pos h]      exact h.choose_spec    have hne_pair : ∀ x y : QuaternionGroup (2 * n + 1), x ≠ y → (x, θ x) ≠ (y, θ y) := by      intro x y hxy hcon      exact hxy (by simpa using congrArg Prod.fst hcon)    have hinj : Function.Injective θ := by      intro x y hxy      by_contra hne      exact (hS _ (hθ x) _ (hθ y) (hne_pair x y hne)).2.1 hxy    have hbijθ : Function.Bijective θ := ⟨hinj, Finite.injective_iff_surjective.1 hinj⟩    have hinjmul : Function.Injective (fun x : QuaternionGroup (2 * n + 1) => x * θ x) := by      intro x y hxy      by_contra hne      exact (hS _ (hθ x) _ (hθ y) (hne_pair x y hne)).2.2 hxy    have hbijmul : Function.Bijective (fun x : QuaternionGroup (2 * n + 1) => x * θ x) :=      ⟨hinjmul, Finite.injective_iff_surjective.1 hinjmul⟩    exact quaternion_odd_has_no_complete_mapping n ⟨θ, hbijθ, hbijmul⟩  omega/-- Counting bound: every coloring of the Cayley table graph of `QuaternionGroup (2n+1)` uses atleast `8n + 6` colors. -/private lemma cayley_table_graph_quaternion_chromatic_number_ge_colorable_bound (n m : ℕ)    (C : (cayley_table_graph (QuaternionGroup (2 * n + 1))).Coloring (Fin m)) :    8 * n + 6 ≤ m := by  have hcard : Fintype.card (QuaternionGroup (2 * n + 1)) = 8 * n + 4 := quaternion_group_card n  have hfiber : ∀ i : Fin m,      (Finset.univ.filter (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) =>        C p = i)).card ≤ 8 * n + 3 := by    intro i    apply cayley_table_graph_quaternion_chromatic_number_ge_pt_card_le n    intro p hp q hq hpq    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp hq    have hCpq : C p = C q := by rw [hp, hq]    refine ⟨?_, ?_, ?_⟩    · intro h      exact C.valid ⟨hpq, Or.inl h⟩ hCpq    · intro h      exact C.valid ⟨hpq, Or.inr (Or.inl h)⟩ hCpq    · intro h      exact C.valid ⟨hpq, Or.inr (Or.inr h)⟩ hCpq  have hsum : ∑ i : Fin m,      (Finset.univ.filter (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) =>        C p = i)).card      = Fintype.card (QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1)) := by    rw [← Finset.card_univ]    exact (Finset.card_eq_sum_card_fiberwise (f := C) (s := Finset.univ) (t := Finset.univ)      (fun x _ => Finset.mem_univ _)).symm  have h2 : ∑ _i : Fin m, (8 * n + 3) = m * (8 * n + 3) := by    simp [Finset.sum_const, Finset.card_univ]  have hle : (8 * n + 4) * (8 * n + 4) ≤ m * (8 * n + 3) := by    have hGF : Fintype.card (QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1))        = (8 * n + 4) * (8 * n + 4) := by rw [Fintype.card_prod, hcard]    calc (8 * n + 4) * (8 * n + 4)        = Fintype.card (QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1)) := hGF.symm      _ = ∑ i : Fin m, (Finset.univ.filter (fun p : QuaternionGroup (2 * n + 1) × QuaternionGroup (2 * n + 1) => C p = i)).card := hsum.symm      _ ≤ ∑ _i : Fin m, (8 * n + 3) := Finset.sum_le_sum (fun i _ => hfiber i)      _ = m * (8 * n + 3) := h2  have hlt : (8 * n + 5) * (8 * n + 3) < (8 * n + 4) * (8 * n + 4) := by nlinarith  have h5 : 8 * n + 5 < m := Nat.lt_of_mul_lt_mul_right (lt_of_lt_of_le hlt hle)  omega/-- Lower bound of 8n + 6 on the chromatic number of the Cayley table graph of QuaternionGroup (2 * n + 1). -/theorem cayley_table_graph_quaternion_chromatic_number_ge (n : ℕ) (hn : 1 ≤ n) :    (8 * n + 6 : ℕ∞) ≤ (cayley_table_graph (QuaternionGroup (2 * n + 1))).chromaticNumber := by  rw [show (8 * ↑n + 6 : ℕ∞) = ((8 * n + 6 : ℕ) : ℕ∞) by push_cast; ring]  rw [SimpleGraph.le_chromaticNumber_iff_colorable]  intro m hm  obtain ⟨C⟩ := hm  exact cayley_table_graph_quaternion_chromatic_number_ge_colorable_bound n m C
See it in the graphDiscuss this resultChallenge it