AFTD Auto-Formalizing Theoretical Domains

pathCertStep

theoremverified

Each reachable transition remains reachable and respects the path certificate potential.

Statement

open scoped BigOperators in
theorem pathCertStep (a b : Fin 4) (s : Fin 128) (h : pathCertReachable a s) :
    pathCertReachable b (pathCertNext a b s) ∧
    pathCertPotential s + pathCertDelta a b s ≤ pathCertPotential (pathCertNext a b s)
Source
Finite-state path cut-matching certificate for OP-827; exhaustive transition check in experiment 22529.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • pathCertNextThe seven greedy-matching flags after appending a colored vertex.
  • pathCertDeltaThe signed change of the seven greedy matching counts for one appended vertex.
  • pathCertReachableThe 44 states reachable by the greedy matching automaton on four-color words.
  • pathCertPotentialAn integer potential for the finite-state path certificate.
Used by 1
  • pathCertRunBoundThe accumulated signed greedy count is bounded by the finite-state potential.

Lean source view module on GitHub

open scoped BigOperators in
theorem pathCertStep (a b : Fin 4) (s : Fin 128) (h : pathCertReachable a s) :
    pathCertReachable b (pathCertNext a b s) ∧
    pathCertPotential s + pathCertDelta a b s ≤ pathCertPotential (pathCertNext a b s) := by
  set_option maxHeartbeats 5000000 in
    set_option maxRecDepth 100000 in
      revert a b s
      decide
See it in the graphDiscuss this resultChallenge it