cubic_paley_graph_decidable_adj
instance
Adjacency in the cubic Paley graph over a finite ring with decidable equality is decidable.
Statement
instance cubic_paley_graph_decidable_adj (F : Type*) [CommRing F] [Fintype F] [DecidableEq F] : DecidableRel (cubic_paley_graph F).Adj
- Source
- decidability for cubic_paley_graph; serves OP-442
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 1
- 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…
- Used by 4
- 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_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
instance cubic_paley_graph_decidable_adj (F : Type*) [CommRing F] [Fintype F] [DecidableEq F] : DecidableRel (cubic_paley_graph F).Adj := fun x y => decidable_of_iff (x ≠ y ∧ ∃ z : F, x - y = z ^ 3) Iff.rfl