cubic_paley_graph_zmod_thirty_one_achromatic_number
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
- 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 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.
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.
decide +kernelThe 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.
dsimp [simple_graph_coloring_is_achromatic] constructor <;> decide +kernel
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.
uses
SimpleGraph.maxDegree_le_of_forall_degree_leapply SimpleGraph.maxDegree_le_of_forall_degree_le decide +kernel
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.
uses
le_simple_graph_achromatic_number,cubic_paley_graph_zmod_thirty_one_achromatic_number_achromatichave 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_achromaticThe 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.
uses
simple_graph_achromatic_number_le_max_degree_or_half,cubic_paley_graph_zmod_thirty_one_achromatic_number_maxDegree_lehave 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.
- The properness of the candidate coloring, its achromaticity (surjectivity and completeness of all color pairs), and the maximum degree bound Δ ≤ 10 are all established by Lean's kernel through exhaustive finite computation (`decide +kernel`) rather than by pen-and-paper graph-theoretic arguments.
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.
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