pathCertRunBound
theoremverified
The accumulated signed greedy count is bounded by the finite-state potential.
Statement
open scoped BigOperators in theorem pathCertRunBound (xs : List (Fin 4)) (a : Fin 4) (s : Fin 128) (h : pathCertReachable a s) : pathCertPotential s + (pathCertRun a s xs).2.2 ≤ pathCertPotential (pathCertRun a s xs).2.1
- 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 8
- pathCertRunRun the seven simultaneous greedy matching counters on a colored path suffix.
- pathCertStepEach reachable transition remains reachable and respects the path certificate potential.
- pathCertPotentialAn integer potential for the finite-state path certificate.
- pathCertDeltaThe signed change of the seven greedy matching counts for one appended vertex.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - pathCertReachableThe 44 states reachable by the greedy matching automaton on four-color words.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - pathCertNextThe seven greedy-matching flags after appending a colored vertex.
- Used by 1
- pure_path_automaton_nonpositiveFor every four-color word, the signed sum of seven greedy path-edge matching counts is nonpositive.
Lean source view module on GitHub
open scoped BigOperators in theorem pathCertRunBound (xs : List (Fin 4)) (a : Fin 4) (s : Fin 128) (h : pathCertReachable a s) : pathCertPotential s + (pathCertRun a s xs).2.2 ≤ pathCertPotential (pathCertRun a s xs).2.1 := by set_option maxHeartbeats 5000000 in induction xs generalizing a s with | nil => simp [pathCertRun] | cons b bs ih => have hstep := pathCertStep a b s h have hrest := ih b (pathCertNext a b s) hstep.1 change pathCertPotential s + (pathCertDelta a b s + (pathCertRun b (pathCertNext a b s) bs).2.2) ≤ pathCertPotential (pathCertRun b (pathCertNext a b s) bs).2.1 calc _ = (pathCertPotential s + pathCertDelta a b s) + (pathCertRun b (pathCertNext a b s) bs).2.2 := by ring _ ≤ pathCertPotential (pathCertNext a b s) + (pathCertRun b (pathCertNext a b s) bs).2.2 := by have hh := hstep.2 omega _ ≤ _ := hrest