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