AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_shift

theoremverified

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
Used by 2

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.

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

    lines 2–4

      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. 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.

    lines 8–9

      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 ℕ)
  3. 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.

    line 10

    uses add_sub_add_right_eq_sub

      rw [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$.

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

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