AFTD Auto-Formalizing Theoretical Domains

pure_path_automaton_nonpositive

theoremverified

For every four-color word, the signed sum of seven greedy path-edge matching counts is nonpositive.

Statement

open scoped BigOperators in
theorem pure_path_automaton_nonpositive (a : Fin 4) (xs : List (Fin 4)) :
    (pathCertRun a 0 xs).2.2 ≤ 0
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
  • pathCertRunBoundThe accumulated signed greedy count is bounded by the finite-state potential.
  • pathCertReachableThe 44 states reachable by the greedy matching automaton on four-color words.
  • pathCertPotentialAn integer potential for the finite-state path certificate.
  • pathCertRunRun the seven simultaneous greedy matching counters on a colored path suffix.
Used by 1
  • pathCertOddRunIneqFor any four-color path word, the signed sum of odd crossing-run counts for the seven masks is nonpositive.

Lean source view module on GitHub

open scoped BigOperators in
theorem pure_path_automaton_nonpositive (a : Fin 4) (xs : List (Fin 4)) :
    (pathCertRun a 0 xs).2.2 ≤ 0 := by
  have hr : pathCertReachable a 0 := by fin_cases a <;> decide
  have h := pathCertRunBound xs a 0 hr
  have hp : pathCertPotential (pathCertRun a 0 xs).2.1 ≤ 0 := by
    unfold pathCertPotential
    split_ifs <;> omega
  have h0 : pathCertPotential 0 = 0 := by decide
  omega
See it in the graphDiscuss this resultChallenge it