AFTD Auto-Formalizing Theoretical Domains

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 than LinearOrder — it does NOT require antisymmetry or…
  • pathCertReachableThe 44 states reachable by the greedy matching automaton on four-color words.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • pathCertNextThe seven greedy-matching flags after appending a colored vertex.
Used by 1

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