cubic_paley_graph_zmod_thirteen_achromatic_number
The cubic Paley graph G_3(13) has achromatic number 6 = (13 − 1)/2, the upper bound, above the value (13 + 2)/3 = 5 conjectured for large q.
Statement
theorem cubic_paley_graph_zmod_thirteen_achromatic_number :
simple_graph_achromatic_number (cubic_paley_graph (ZMod 13)) = 6- 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 = 13, 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 $G_3(13)$ is proved to be 6 by matching upper and lower bounds. The lower bound $\psi(G_3(13)) \ge 6$ is established by exhibiting an explicit 6-coloring on $\mathbb{Z}/13\mathbb{Z}$ and verifying by finite computation (`decide`) that it is both proper and achromatic. The upper bound $\psi(G_3(13)) \le 6$ follows from the general bound $\psi(G) \le \max(\Delta(G) + 1, \lfloor |V| / 2 \rfloor)$ combined with $\Delta(G_3(13)) \le 4$ and $\lfloor 13 / 2 \rfloor = 6$. Linear arithmetic (`omega`) combines both bounds to conclude that $\psi(G_3(13)) = 6$.
The explicit assignment `val` of 6 colors to $\mathbb{Z}/13\mathbb{Z}$ is a proper coloring of the cubic Paley graph $G_3(13)$.
We define `val` by assigning colors in $\{0, \dots, 5\}$ to the elements $0, \dots, 12$ of $\mathbb{Z}/13\mathbb{Z}$ via the vector `![0, 3, 2, 3, 4, 2, 1, 5, 4, 2, 0, 5, 1]`. The lemma `cubic_paley_graph_zmod_thirteen_achromatic_number_proper` states that if two vertices are adjacent (their difference is a non-zero cube modulo 13), their colors differ. Since $\mathbb{Z}/13\mathbb{Z}$ is finite, the `decide` tactic checks this universal condition by exhaustive computation over all pairs of vertices.
def cubic_paley_graph_zmod_thirteen_achromatic_number_val : ZMod 13 → Fin 6 := ![(0:Fin 6), 3, 2, 3, 4, 2, 1, 5, 4, 2, 0, 5, 1] lemma cubic_paley_graph_zmod_thirteen_achromatic_number_proper : ∀ {v w : ZMod 13}, (cubic_paley_graph (ZMod 13)).Adj v w → cubic_paley_graph_zmod_thirteen_achromatic_number_val v ≠ cubic_paley_graph_zmod_thirteen_achromatic_number_val w := by decide
The coloring packages into an achromatic coloring of $G_3(13)$ with 6 colors.
Using `SimpleGraph.Coloring.mk` and the properness lemma `cubic_paley_graph_zmod_thirteen_achromatic_number_proper`, we package `val` into a formal coloring `cubic_paley_graph_zmod_thirteen_achromatic_number_coloring`. Unfolding the definition of an achromatic coloring (`simple_graph_coloring_is_achromatic`) requires two properties: that the coloring is surjective onto $\{0, \dots, 5\}$, and that every pair of distinct colors $i \ne j$ is connected by at least one edge. The tactic `constructor` splits these two requirements, and each is verified by exhaustive finite check using `decide`.
uses
SimpleGraph.Coloring.mk,cubic_paley_graph_zmod_thirteen_achromatic_number_properdef cubic_paley_graph_zmod_thirteen_achromatic_number_coloring : (cubic_paley_graph (ZMod 13)).Coloring (Fin 6) := SimpleGraph.Coloring.mk cubic_paley_graph_zmod_thirteen_achromatic_number_val cubic_paley_graph_zmod_thirteen_achromatic_number_proper lemma cubic_paley_graph_zmod_thirteen_achromatic_number_achromatic : simple_graph_coloring_is_achromatic cubic_paley_graph_zmod_thirteen_achromatic_number_coloring := by dsimp [simple_graph_coloring_is_achromatic] constructor <;> decide
The maximum degree of $G_3(13)$ is at most 4.
Applying `SimpleGraph.maxDegree_le_of_forall_degree_le` reduces bounding the maximum degree $\Delta \le 4$ to showing that the degree of every vertex is at most 4. Since there are only 13 vertices, `decide` checks this condition by finite enumeration (each vertex is connected to the 4 cubic residues $\{1, 5, 8, 12\}$ modulo 13).
uses
SimpleGraph.maxDegree_le_of_forall_degree_lelemma cubic_paley_graph_zmod_thirteen_achromatic_number_maxDegree_le : (cubic_paley_graph (ZMod 13)).maxDegree ≤ 4 := by apply SimpleGraph.maxDegree_le_of_forall_degree_le decide
The achromatic number of $G_3(13)$ is at least 6.
By `le_simple_graph_achromatic_number`, exhibiting an achromatic coloring with $k$ colors proves that the achromatic number is at least $k$. Applying this lemma to the constructed 6-coloring and the lemma `cubic_paley_graph_zmod_thirteen_achromatic_number_achromatic` yields $6 \le \psi(G_3(13))$.
uses
le_simple_graph_achromatic_number,cubic_paley_graph_zmod_thirteen_achromatic_number_achromatictheorem cubic_paley_graph_zmod_thirteen_achromatic_number : simple_graph_achromatic_number (cubic_paley_graph (ZMod 13)) = 6 := by have h_lower : 6 ≤ simple_graph_achromatic_number (cubic_paley_graph (ZMod 13)) := le_simple_graph_achromatic_number cubic_paley_graph_zmod_thirteen_achromatic_number_coloring cubic_paley_graph_zmod_thirteen_achromatic_number_achromatic
The achromatic number of $G_3(13)$ is at most 6.
The general upper bound `simple_graph_achromatic_number_le_max_degree_or_half` gives $\psi(G) \le \max(\Delta(G) + 1, \lfloor |V| / 2 \rfloor)$. We instantiate this theorem for $G_3(13)$ (`h_upper`), use the maximum degree bound $\Delta \le 4$ from `cubic_paley_graph_zmod_thirteen_achromatic_number_maxDegree_le` (`h_deg`), and evaluate $\lfloor 13 / 2 \rfloor = 6$ by `decide` (`h_card`).
uses
simple_graph_achromatic_number_le_max_degree_or_half,cubic_paley_graph_zmod_thirteen_achromatic_number_maxDegree_lehave h_upper := simple_graph_achromatic_number_le_max_degree_or_half (cubic_paley_graph (ZMod 13)) have h_deg := cubic_paley_graph_zmod_thirteen_achromatic_number_maxDegree_le have h_card : Fintype.card (ZMod 13) / 2 = 6 := by decide
The achromatic number of $G_3(13)$ is equal to 6.
We have $6 \le \psi(G_3(13))$ and $\psi(G_3(13)) \le \max(\Delta + 1, 6)$ with $\Delta \le 4$. Since $\Delta + 1 \le 5$, the maximum is 6, which leaves $6 \le \psi(G_3(13)) \le 6$. The `omega` tactic solves this system of linear integer arithmetic constraints to conclude that $\psi(G_3(13)) = 6$.
omega
SimpleGraph.Coloring.mk- Constructs a proper vertex coloring of a graph from a coloring function and a proof that adjacent vertices receive distinct colors.
SimpleGraph.maxDegree_le_of_forall_degree_le- If every vertex in a finite graph has degree at most $k$, then the graph's maximum degree is at most $k$.
cubic_paley_graph_zmod_thirteen_achromatic_number_achromatic- The constructed 6-coloring on the cubic Paley graph over $\mathbb{Z}/13\mathbb{Z}$ is achromatic: it is surjective and every pair of distinct colors is joined by at least one edge.
cubic_paley_graph_zmod_thirteen_achromatic_number_maxDegree_le- The maximum degree of the cubic Paley graph on $\mathbb{Z}/13\mathbb{Z}$ is at most 4.
cubic_paley_graph_zmod_thirteen_achromatic_number_proper- Adjacent vertices in the cubic Paley graph on $\mathbb{Z}/13\mathbb{Z}$ receive distinct values under the explicit coloring vector.
le_simple_graph_achromatic_number- If a finite graph admits an achromatic coloring with $k$ colors, then its achromatic number is at least $k$.
simple_graph_achromatic_number_le_max_degree_or_half- The achromatic number of any finite graph is at most $\max(\Delta + 1, \lfloor |V| / 2 \rfloor)$, where $\Delta$ is the maximum degree and $|V|$ is the number of vertices.
- The properness and achromaticity of the explicit coloring (Steps 1 and 2), as well as the vertex degree bounds (Step 3) and cardinality division (Step 5), are discharged by the kernel using `decide` via exhaustive finite computation on $\mathbb{Z}/13\mathbb{Z}$ rather than symbolic derivations.
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_thirteen_achromatic_number_val : ZMod 13 → Fin 6 := ![(0:Fin 6), 3, 2, 3, 4, 2, 1, 5, 4, 2, 0, 5, 1]lemma cubic_paley_graph_zmod_thirteen_achromatic_number_proper : ∀ {v w : ZMod 13}, (cubic_paley_graph (ZMod 13)).Adj v w → cubic_paley_graph_zmod_thirteen_achromatic_number_val v ≠ cubic_paley_graph_zmod_thirteen_achromatic_number_val w := by decidedef cubic_paley_graph_zmod_thirteen_achromatic_number_coloring : (cubic_paley_graph (ZMod 13)).Coloring (Fin 6) := SimpleGraph.Coloring.mk cubic_paley_graph_zmod_thirteen_achromatic_number_val cubic_paley_graph_zmod_thirteen_achromatic_number_properlemma cubic_paley_graph_zmod_thirteen_achromatic_number_achromatic : simple_graph_coloring_is_achromatic cubic_paley_graph_zmod_thirteen_achromatic_number_coloring := by dsimp [simple_graph_coloring_is_achromatic] constructor <;> decidelemma cubic_paley_graph_zmod_thirteen_achromatic_number_maxDegree_le : (cubic_paley_graph (ZMod 13)).maxDegree ≤ 4 := by apply SimpleGraph.maxDegree_le_of_forall_degree_le decidetheorem cubic_paley_graph_zmod_thirteen_achromatic_number : simple_graph_achromatic_number (cubic_paley_graph (ZMod 13)) = 6 := by have h_lower : 6 ≤ simple_graph_achromatic_number (cubic_paley_graph (ZMod 13)) := le_simple_graph_achromatic_number cubic_paley_graph_zmod_thirteen_achromatic_number_coloring cubic_paley_graph_zmod_thirteen_achromatic_number_achromatic have h_upper := simple_graph_achromatic_number_le_max_degree_or_half (cubic_paley_graph (ZMod 13)) have h_deg := cubic_paley_graph_zmod_thirteen_achromatic_number_maxDegree_le have h_card : Fintype.card (ZMod 13) / 2 = 6 := by decide omega