AFTD Auto-Formalizing Theoretical Domains

cubic_paley_graph_zmod_nineteen_achromatic_number

theoremverifiedoriginal

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

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.

  1. 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.

    line 8

    uses SimpleGraph.Coloring.mk

      SimpleGraph.Coloring.mk cubic_paley_graph_zmod_nineteen_achromatic_number_color (by decide)
  2. 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.

    lines 14–17

      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
  3. 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.

    line 22

      decide
  4. To 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.

    line 26

    uses le_antisymm

      refine le_antisymm ?_ ?_
  5. 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.

    lines 27–28

    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
  6. 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.

    line 29

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it