AFTD Auto-Formalizing Theoretical Domains

cubic_paley_graph_zmod_thirty_one_achromatic_number

theoremverifiedoriginal

The cubic Paley graph G_3(31) has achromatic number 15 = (31 − 1)/2, the upper bound, above the value (31 + 2)/3 = 11 conjectured for large q.

Statement

theorem cubic_paley_graph_zmod_thirty_one_achromatic_number :
    simple_graph_achromatic_number (cubic_paley_graph (ZMod 31)) = 15
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; exact value at q = 31, found by computation (experiment 2314).
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6

The proof, explained

The achromatic number of the cubic Paley graph G₃(31) is shown to be 15 by proving matching lower and upper bounds. For the lower bound, an explicit 15-coloring of the 31 vertices is defined and checked by computation to be both proper and achromatic. For the upper bound, the general inequality ψ(G) ≤ max(Δ(G) + 1, ⌊|V| / 2⌋) is applied with Δ ≤ 10 and |V| = 31, giving max(11, 15) = 15. Together, these bounds force the achromatic number to be exactly 15.

  1. The explicit 15-coloring on the cubic Paley graph G₃(31) is a proper coloring.

    The properness condition asserts that adjacent vertices in G₃(31) receive distinct colors under the candidate coloring. Because ℤ/31ℤ has only 31 elements, this universal statement over all pairs of adjacent vertices is decidable, and Lean's kernel verifies it by exhaustive computation.

    line 8

      decide +kernel
  2. The candidate 15-coloring is achromatic.

    Unfolding the definition `simple_graph_coloring_is_achromatic` reduces the goal to two requirements: surjectivity onto the 15 colors, and completeness (every pair of distinct colors is joined by at least one edge). The tactic `constructor` splits the conjunction into these two goals, and `decide +kernel` closes each by exhaustive finite computation.

    lines 19–20

      dsimp [simple_graph_coloring_is_achromatic]
      constructor <;> decide +kernel
  3. The maximum degree of G₃(31) is at most 10.

    Applying `SimpleGraph.maxDegree_le_of_forall_degree_le` reduces bounding the maximum degree to verifying that every individual vertex has degree at most 10. The kernel checks this degree inequality for each of the 31 vertices by exhaustive computation.

    lines 24–25

    uses SimpleGraph.maxDegree_le_of_forall_degree_le

      apply SimpleGraph.maxDegree_le_of_forall_degree_le
      decide +kernel
  4. The achromatic number of G₃(31) is at least 15.

    By `le_simple_graph_achromatic_number`, any graph admitting an achromatic coloring with k colors has achromatic number at least k. Applying this lemma to the packaged 15-coloring and its proof of achromaticity establishes that the achromatic number is at least 15.

    lines 29–32

    uses le_simple_graph_achromatic_number, cubic_paley_graph_zmod_thirty_one_achromatic_number_achromatic

      have h_lower : 15 ≤ simple_graph_achromatic_number (cubic_paley_graph (ZMod 31)) :=
        le_simple_graph_achromatic_number
          cubic_paley_graph_zmod_thirty_one_achromatic_number_coloring
          cubic_paley_graph_zmod_thirty_one_achromatic_number_achromatic
  5. The achromatic number of G₃(31) is at most 15, and hence equals 15.

    By `simple_graph_achromatic_number_le_max_degree_or_half`, the achromatic number of any graph is at most max(Δ + 1, ⌊|V| / 2⌋). Using the bound Δ ≤ 10 from `cubic_paley_graph_zmod_thirty_one_achromatic_number_maxDegree_le` and the computation 31 / 2 = 15, the upper bound evaluates to max(11, 15) = 15. Linear integer arithmetic (`omega`) combines this upper bound with the lower bound 15 ≤ ψ(G₃(31)) to conclude that the achromatic number is exactly 15.

    lines 33–36

    uses simple_graph_achromatic_number_le_max_degree_or_half, cubic_paley_graph_zmod_thirty_one_achromatic_number_maxDegree_le

      have h_upper := simple_graph_achromatic_number_le_max_degree_or_half (cubic_paley_graph (ZMod 31))
      have h_deg := cubic_paley_graph_zmod_thirty_one_achromatic_number_maxDegree_le
      have h_card : Fintype.card (ZMod 31) / 2 = 15 := by decide
      omega
SimpleGraph.maxDegree_le_of_forall_degree_le
If every vertex in a finite graph G has degree at most k, then the maximum degree of G is at most k.
le_simple_graph_achromatic_number
If a finite graph G admits an achromatic coloring with k colors, then the achromatic number of G is at least k.
cubic_paley_graph_zmod_thirty_one_achromatic_number_achromatic
The candidate 15-coloring of the cubic Paley graph on ℤ/31ℤ is achromatic.
simple_graph_achromatic_number_le_max_degree_or_half
For any finite graph G, its achromatic number is at most max(Δ(G) + 1, ⌊|V(G)| / 2⌋), where Δ(G) is the maximum degree of G.
cubic_paley_graph_zmod_thirty_one_achromatic_number_maxDegree_le
The maximum degree of the cubic Paley graph on ℤ/31ℤ is at most 10.

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

def cubic_paley_graph_zmod_thirty_one_achromatic_number_val : ZMod 31 → Fin 15 :=  ![(0:Fin 15), 5, 1, 12, 10, 7, 3, 1, 8, 0, 14, 13, 5, 10, 4, 11, 12, 3, 9, 6, 14, 13, 0, 7, 2, 4, 8, 9, 11, 2, 6]lemma cubic_paley_graph_zmod_thirty_one_achromatic_number_proper :    ∀ {v w : ZMod 31}, (cubic_paley_graph (ZMod 31)).Adj v w →      cubic_paley_graph_zmod_thirty_one_achromatic_number_val v ≠        cubic_paley_graph_zmod_thirty_one_achromatic_number_val w := by  decide +kerneldef cubic_paley_graph_zmod_thirty_one_achromatic_number_coloring :    (cubic_paley_graph (ZMod 31)).Coloring (Fin 15) :=  SimpleGraph.Coloring.mk    cubic_paley_graph_zmod_thirty_one_achromatic_number_val    cubic_paley_graph_zmod_thirty_one_achromatic_number_properlemma cubic_paley_graph_zmod_thirty_one_achromatic_number_achromatic :    simple_graph_coloring_is_achromatic      cubic_paley_graph_zmod_thirty_one_achromatic_number_coloring := by  dsimp [simple_graph_coloring_is_achromatic]  constructor <;> decide +kernellemma cubic_paley_graph_zmod_thirty_one_achromatic_number_maxDegree_le :    (cubic_paley_graph (ZMod 31)).maxDegree ≤ 10 := by  apply SimpleGraph.maxDegree_le_of_forall_degree_le  decide +kerneltheorem cubic_paley_graph_zmod_thirty_one_achromatic_number :    simple_graph_achromatic_number (cubic_paley_graph (ZMod 31)) = 15 := by  have h_lower : 15 ≤ simple_graph_achromatic_number (cubic_paley_graph (ZMod 31)) :=    le_simple_graph_achromatic_number      cubic_paley_graph_zmod_thirty_one_achromatic_number_coloring      cubic_paley_graph_zmod_thirty_one_achromatic_number_achromatic  have h_upper := simple_graph_achromatic_number_le_max_degree_or_half (cubic_paley_graph (ZMod 31))  have h_deg := cubic_paley_graph_zmod_thirty_one_achromatic_number_maxDegree_le  have h_card : Fintype.card (ZMod 31) / 2 = 15 := by decide  omega
See it in the graphDiscuss this resultChallenge it