digraph_safe17_shift
The displayed cyclic graph is invariant under translating both endpoints.
Statement
theorem digraph_safe17_shift (a b t : Fin 17) :
digraph_safe17_graph.Adj (a+t) (b+t) ↔ digraph_safe17_graph.Adj a b- Source
- Finite safe-cycle obstruction for OP-110; experiment 13260.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_safe17_graphThe seventeen-vertex cyclic digraph with the displayed seven out-steps.
- Used by 2
- digraph_safe17_triangle_unsafeEvery directed triangle in the displayed graph has an outside vertex pointing to all three of its vertices.
- digraph_safe17_four_unsafeEvery directed four-cycle in the displayed graph has an outside vertex pointing to at least three of its vertices.
The proof, explained
The directed graph on $\mathrm{Fin}\; 17$ has an edge from $u$ to $v$ if and only if the difference $(v - u).\mathrm{val}$ belongs to a fixed subset of $\{1, 2, 3, 5, 6, 7, 13\}$. Because translation by $t$ preserves differences in the additive group $\mathrm{Fin}\; 17$ via $(b + t) - (a + t) = b - a$, shifting both endpoints leaves the adjacency condition unchanged. An auxiliary instance also establishes that adjacency is decidable.
Adjacency between any two vertices in the graph is decidable. automation
For arbitrary vertices $u$ and $v$, unfolding the definition of the graph expresses adjacency as membership of the difference $(v - u).\mathrm{val}$ in the explicit finite set $\{1, 2, 3, 5, 6, 7, 13\}$. Lean's typeclass resolution automatically synthesizes the decidability of this finite set membership.
intro u v unfold digraph_safe17_graph infer_instance
Adjacency of $a + t$ to $b + t$ and of $a$ to $b$ can be restated directly in terms of differences.
By definition of `digraph_safe17_graph`, a directed edge from $u$ to $v$ exists precisely when $(v - u).\mathrm{val} \in \{1, 2, 3, 5, 6, 7, 13\}$. The goal is thus rewritten to comparing whether $((b + t) - (a + t)).\mathrm{val}$ and $(b - a).\mathrm{val}$ belong to this set.
change ((b+t)-(a+t)).val ∈ ({1,2,3,5,6,7,13} : Finset ℕ) ↔ (b-a).val ∈ ({1,2,3,5,6,7,13} : Finset ℕ)Adjacency is invariant under shifting both vertices by $t$.
In the additive group $\mathrm{Fin}\; 17$, the shift $t$ cancels in the subtraction: $(b + t) - (a + t) = b - a$ by `add_sub_add_right_eq_sub`. Rewriting by this identity makes both sides of the equivalence identical, completing the proof.
uses
add_sub_add_right_eq_subrw [add_sub_add_right_eq_sub]
add_sub_add_right_eq_sub- In any additive group, subtracting two elements shifted by the same value is equal to their difference: $(a + c) - (b + c) = a - b$.
- The source file includes an auxiliary instance `in504_safe17_decAdj_4` establishing the decidability of graph adjacency before the shift theorem itself.
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.
private instance in504_safe17_decAdj_4 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instancetheorem digraph_safe17_shift (a b t : Fin 17) : digraph_safe17_graph.Adj (a+t) (b+t) ↔ digraph_safe17_graph.Adj a b := by change ((b+t)-(a+t)).val ∈ ({1,2,3,5,6,7,13} : Finset ℕ) ↔ (b-a).val ∈ ({1,2,3,5,6,7,13} : Finset ℕ) rw [add_sub_add_right_eq_sub]