cayley_table_graph_quaternion_chromatic_number_ge
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.
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).
uses
quaternion_group_card,Finset.card_image_of_injOn,Finset.card_le_univhave 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 _
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.
uses
Finset.eq_univ_of_card,Finite.injective_iff_surjective.1,quaternion_odd_has_no_complete_mappinghave 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⟩
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.
omegaEach 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.
uses
quaternion_group_card,cayley_table_graph_quaternion_chromatic_number_ge_pt_card_lehave 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
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.
uses
Finset.card_eq_sum_card_fiberwise,Finset.sum_const,Fintype.card_prod,Finset.sum_le_sumhave 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
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.
uses
Nat.lt_of_mul_lt_mul_right,lt_of_lt_of_lehave 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
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.
uses
SimpleGraph.le_chromaticNumber_iff_colorable,cayley_table_graph_quaternion_chromatic_number_ge_colorable_boundrw [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.
- The step showing (8 * n + 5) * (8 * n + 3) < (8 * n + 4) * (8 * n + 4) relies on nonlinear integer arithmetic (nlinarith), using the identity (8n+5)(8n+3) = (8n+4)^2 - 1.
- The conversion between ℕ and WithTop ℕ (ℕ∞) in the main theorem is handled via push_cast and ring before applying the chromatic number equivalence.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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