cubic_paley_graph
def
G_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 vertices is nonzero, so it is a nonzero cube.
Statement
def cubic_paley_graph (F : Type*) [CommRing F] : SimpleGraph F
- Defined in
- arXiv:2610.27510 (The achromatic number of Paley graphs, Peisert graphs, and related Cayley graphs), Sec. 1, the k-th power Paley graph G_k(q) for k = 3
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Used by 5
- cubic_paley_graph_zmod_nineteen_achromatic_numberThe 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.
- cubic_paley_graph_decidable_adjAdjacency in the cubic Paley graph over a finite ring with decidable equality is decidable.
- cubic_paley_graph_zmod_seven_adj_iffIn F_7 the nonzero cubes are ±1, so G_3(7) is the 7-cycle.
- cubic_paley_graph_zmod_thirteen_achromatic_numberThe 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.
- cubic_paley_graph_zmod_thirty_one_achromatic_numberThe 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…
Lean source view module on GitHub
/-- The cubic Paley graph G_3(q) on a commutative ring F (the paper's case: F a finite field of order q ≡ 1 mod 6): distinct x, y are adjacent iff x − y is a cube (necessarily a nonzero one). -/ def cubic_paley_graph (F : Type*) [CommRing F] : SimpleGraph F where Adj x y := x ≠ y ∧ ∃ z : F, x - y = z ^ 3 symm := ⟨by rintro x y ⟨hxy, z, hz⟩ exact ⟨fun h => hxy h.symm, -z, by rw [← neg_sub, hz]; ring⟩⟩ loopless := ⟨fun _ h => h.1 rfl⟩