AFTD Auto-Formalizing Theoretical Domains

cubic_paley_graph_zmod_seven_adj_iff

theoremverified

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.

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

    line 3

      revert x y; decide

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

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