AFTD Auto-Formalizing Theoretical Domains

cubic_paley_graph_zmod_thirteen_achromatic_number

theoremverifiedoriginal

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

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

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

    lines 1–8

    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
  2. 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`.

    lines 9–21

    uses SimpleGraph.Coloring.mk, cubic_paley_graph_zmod_thirteen_achromatic_number_proper

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

    lines 22–26

    uses SimpleGraph.maxDegree_le_of_forall_degree_le

    lemma 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
    
  4. 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))$.

    lines 27–32

    uses le_simple_graph_achromatic_number, cubic_paley_graph_zmod_thirteen_achromatic_number_achromatic

    theorem 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
  5. 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`).

    lines 33–35

    uses simple_graph_achromatic_number_le_max_degree_or_half, cubic_paley_graph_zmod_thirteen_achromatic_number_maxDegree_le

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

    line 36

      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.

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