cubic_paley_graph_zmod_seven_adj_iff
In F_7 the nonzero cubes are ±1, so G_3(7) is the 7-cycle.
Statement
theorem cubic_paley_graph_zmod_seven_adj_iff (x y : ZMod 7) :
(cubic_paley_graph (ZMod 7)).Adj x y ↔ x - y = 1 ∨ x - y = 6- Source
- sanity lemma for cubic_paley_graph; serves OP-442
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
The proof, explained
The claim is proved by finite exhaustive computation. By generalizing over the vertices $x, y \in \mathbb{Z}/7\mathbb{Z}$, the statement becomes a decidable universal proposition over the finite ring $\mathbb{Z}/7\mathbb{Z}$, which Lean settles directly by evaluating all 49 pairs.
For all $x, y \in \mathbb{Z}/7\mathbb{Z}$, $x$ and $y$ are adjacent in the cubic Paley graph if and only if $x - y = 1$ or $x - y = 6$. automation
Reverting $x$ and $y$ turns the goal into a universally quantified statement $\forall x, y \in \mathbb{Z}/7\mathbb{Z}$. Because $\mathbb{Z}/7\mathbb{Z}$ is a finite ring with 7 elements and both the adjacency relation (defined via an existential quantifier over $\mathbb{Z}/7\mathbb{Z}$) and equality are decidable, the `decide` tactic checks the equivalence by exhaustive computation over all $7 \times 7 = 49$ pairs.
revert x y; decide
- The proof is carried out purely by computational reflection (`decide`), which verifies the equivalence by exhaustive evaluation over all 49 pairs in $(\mathbb{Z}/7\mathbb{Z})^2$, rather than by symbolically computing the set of cubes in $\mathbb{Z}/7\mathbb{Z}$.
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.
theorem cubic_paley_graph_zmod_seven_adj_iff (x y : ZMod 7) : (cubic_paley_graph (ZMod 7)).Adj x y ↔ x - y = 1 ∨ x - y = 6 := by revert x y; decide