cubic_paley_graph_zmod_nineteen_achromatic_number
The cubic Paley graph G_3(19) has achromatic number 9 = (19 − 1)/2, the upper bound, above the value (19 + 2)/3 = 7 conjectured for large q.
Statement
theorem cubic_paley_graph_zmod_nineteen_achromatic_number :
simple_graph_achromatic_number (cubic_paley_graph (ZMod 19)) = 9- Related work
- arXiv:2610.27510 (The achromatic number of Paley graphs, Peisert graphs, and related Cayley graphs): the paper's bounds (q+2)/3 ≤ χ_a(G_3(q)) ≤ (q−1)/2; this is the exact value at q = 19, found by computation (experiment 2294).
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- simple_graph_achromatic_numberχ_a(G) is the maximum number of colours in an achromatic colouring of G.
- cubic_paley_graphG_3(q): vertex set F_q, with distinct x, y adjacent iff x − y ∈ (F_q^×)^3. Defined over any commutative ring; the difference of distinct…
- cubic_paley_graph_decidable_adjAdjacency in the cubic Paley graph over a finite ring with decidable equality is decidable.
- le_simple_graph_achromatic_numberAn achromatic colouring with k colours shows χ_a(G) ≥ k (the set of such k is bounded by |V| since achromatic colourings are surjective).
- simple_graph_achromatic_number_le_max_degree_or_halfFor every finite graph, χ_a(G) ≤ max{Δ(G) + 1, ⌊n/2⌋}: if some colour class is a single vertex, that vertex has a neighbour in each of the…
- simple_graph_coloring_is_achromaticA proper vertex colouring with k colours is achromatic if all k colours are used and there is at least one edge between each pair of…
The proof, explained
The achromatic number of the cubic Paley graph on ℤ/19ℤ is shown to be 9 by establishing matching upper and lower bounds. The upper bound follows from the general bound that the achromatic number is at most max(Δ + 1, ⌊|V| / 2⌋), which evaluates to max(6 + 1, ⌊19 / 2⌋) = 9 because the graph is 6-regular on 19 vertices. The lower bound is established by constructing an explicit 9-coloring of the 19 vertices and verifying by finite exhaustion that it is a valid achromatic coloring. By antisymmetry of the ordering on natural numbers, these two bounds force the achromatic number to be exactly 9.
The explicit color assignment from ℤ/19ℤ to {0, …, 8} is a proper vertex coloring of the cubic Paley graph. automation
Using the constructor `SimpleGraph.Coloring.mk`, constructing a coloring requires showing that adjacent vertices receive different colors. The automated tactic `decide` verifies this by checking every edge of the finite graph.
uses
SimpleGraph.Coloring.mkSimpleGraph.Coloring.mk cubic_paley_graph_zmod_nineteen_achromatic_number_color (by decide)
The 9-coloring of the cubic Paley graph is achromatic. automation
We simplify by unfolding the definition of an achromatic coloring (which requires surjectivity and that every pair of distinct colors is joined by at least one edge) along with the definitions of the coloring and the color table. The automated decision procedure `decide` then verifies this condition by exhaustive search over all colors and pairs of colors.
dsimp [simple_graph_coloring_is_achromatic, cubic_paley_graph_zmod_nineteen_achromatic_number_coloring, SimpleGraph.Coloring.mk, cubic_paley_graph_zmod_nineteen_achromatic_number_color] decide
The upper bound parameter max(Δ + 1, ⌊19/2⌋) evaluates to 9 for the cubic Paley graph on ℤ/19ℤ. automation
The cubic Paley graph on ℤ/19ℤ is 6-regular, so its maximum degree is Δ = 6, yielding Δ + 1 = 7. Half the number of vertices is ⌊19/2⌋ = 9. The tactic `decide` computes both quantities and verifies max(7, 9) = 9.
decideTo show the achromatic number is 9, it suffices to prove both the upper bound ≤ 9 and the lower bound ≥ 9.
By antisymmetry of the partial order on natural numbers (`le_antisymm`), establishing both inequalities proves equality.
uses
le_antisymmrefine le_antisymm ?_ ?_The achromatic number of the cubic Paley graph on ℤ/19ℤ is at most 9.
We instantiate the general bound `simple_graph_achromatic_number_le_max_degree_or_half`, which states that the achromatic number of any graph is at most max(Δ + 1, ⌊|V| / 2⌋). We then rewrite using the equality `cubic_paley_graph_zmod_nineteen_achromatic_number_max` to conclude the achromatic number is at most 9.
uses
simple_graph_achromatic_number_le_max_degree_or_half,cubic_paley_graph_zmod_nineteen_achromatic_number_max· have h := simple_graph_achromatic_number_le_max_degree_or_half (cubic_paley_graph (ZMod 19)) rwa [cubic_paley_graph_zmod_nineteen_achromatic_number_max] at h
The achromatic number of the cubic Paley graph on ℤ/19ℤ is at least 9.
We apply `le_simple_graph_achromatic_number` to the previously established fact that our explicit 9-coloring is achromatic (`cubic_paley_graph_zmod_nineteen_achromatic_number_achromatic`), which implies the achromatic number is at least 9.
uses
le_simple_graph_achromatic_number,cubic_paley_graph_zmod_nineteen_achromatic_number_achromatic· exact le_simple_graph_achromatic_number _ cubic_paley_graph_zmod_nineteen_achromatic_number_achromatic
SimpleGraph.Coloring.mk- A vertex labeling by colors defines a valid graph coloring if adjacent vertices always receive distinct colors.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
simple_graph_achromatic_number_le_max_degree_or_half- For any finite graph G, its achromatic number is at most max(Δ(G) + 1, ⌊|V| / 2⌋).
cubic_paley_graph_zmod_nineteen_achromatic_number_max- For the cubic Paley graph on ℤ/19ℤ, the quantity max(Δ + 1, ⌊|V| / 2⌋) equals 9.
le_simple_graph_achromatic_number- If a finite graph admits an achromatic coloring with k colors, then its achromatic number is at least k.
cubic_paley_graph_zmod_nineteen_achromatic_number_achromatic- The explicit 9-coloring of the cubic Paley graph on ℤ/19ℤ is an achromatic coloring.
- The validity of the 9-coloring (that adjacent vertices receive distinct colors), its achromaticity (surjectivity and edge coverage across all color pairs), and the graph's maximum degree computation are all proved by computational reflection (`decide`) over the finite graph on 19 vertices, rather than through pencil-and-paper graph-theoretic deduction.
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.
/-- Colour table for the achromatic 9-colouring of the cubic Paley graph on `ZMod 19`. -/def cubic_paley_graph_zmod_nineteen_achromatic_number_color : ZMod 19 → Fin 9 := ![0, 8, 3, 2, 8, 1, 0, 1, 7, 4, 7, 6, 2, 4, 8, 5, 6, 5, 3]/-- The 9-colouring of the cubic Paley graph on `ZMod 19` given by the colour table above. -/def cubic_paley_graph_zmod_nineteen_achromatic_number_coloring : (cubic_paley_graph (ZMod 19)).Coloring (Fin 9) := SimpleGraph.Coloring.mk cubic_paley_graph_zmod_nineteen_achromatic_number_color (by decide)/-- The colouring is achromatic: surjective, with an edge between every pair of classes. -/theorem cubic_paley_graph_zmod_nineteen_achromatic_number_achromatic : simple_graph_coloring_is_achromatic cubic_paley_graph_zmod_nineteen_achromatic_number_coloring := by dsimp [simple_graph_coloring_is_achromatic, cubic_paley_graph_zmod_nineteen_achromatic_number_coloring, SimpleGraph.Coloring.mk, cubic_paley_graph_zmod_nineteen_achromatic_number_color] decide/-- The cubic Paley graph on `ZMod 19` is 6-regular, so `max (Δ+1) ⌊19/2⌋ = 9`. -/theorem cubic_paley_graph_zmod_nineteen_achromatic_number_max : max ((cubic_paley_graph (ZMod 19)).maxDegree + 1) (Fintype.card (ZMod 19) / 2) = 9 := by decidetheorem cubic_paley_graph_zmod_nineteen_achromatic_number : simple_graph_achromatic_number (cubic_paley_graph (ZMod 19)) = 9 := by refine le_antisymm ?_ ?_ · have h := simple_graph_achromatic_number_le_max_degree_or_half (cubic_paley_graph (ZMod 19)) rwa [cubic_paley_graph_zmod_nineteen_achromatic_number_max] at h · exact le_simple_graph_achromatic_number _ cubic_paley_graph_zmod_nineteen_achromatic_number_achromatic