AFTD Auto-Formalizing Theoretical Domains

pathCertRun_eq_greedy

theoremverified

The automaton output equals the signed sum of seven greedy edge counts.

Statement

open scoped BigOperators in
theorem pathCertRun_eq_greedy (a : Fin 4) (s : Fin 128) (xs : List (Fin 4)) :
    (pathCertRun a s xs).2.2 = ∑ j : Fin 7, pathCertSign j * (pathGreedyRun (Nat.testBit s.val j.val) (pathCertWord a xs j) : ℤ)
Source
Four-color word certificate for path cut-rank inequalities, using the transition table of experiment 22529.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • pathCertRunRun the seven simultaneous greedy matching counters on a colored path suffix.
  • pathCertSignThe signs of the seven terms in the tripartite cut-rank sum.
  • pathGreedyRunGreedily count disjoint true edges in a Boolean edge word.
  • pathCertWordThe sequence of cut-crossing flags for one party-union mask along a colored vertex word.
  • pathCertNext_bitEach bit of the automaton state records the corresponding greedy matching choice.
  • pathCertTakeGreedy matching choice for one cut when a path edge is appended.
  • pathCertNextThe seven greedy-matching flags after appending a colored vertex.
  • pathCertDeltaThe signed change of the seven greedy matching counts for one appended vertex.
  • pathCertMaskThe seven party-union masks for a four-color path word.
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 pathCertRun_eq_greedy (a : Fin 4) (s : Fin 128) (xs : List (Fin 4)) :
    (pathCertRun a s xs).2.2 = ∑ j : Fin 7, pathCertSign j * (pathGreedyRun (Nat.testBit s.val j.val) (pathCertWord a xs j) : ℤ) := by
  set_option maxHeartbeats 5000000 in
    induction xs generalizing a s with
    | nil => simp [pathCertRun, pathCertWord, pathGreedyRun]
    | cons b bs ih =>
      change pathCertDelta a b s + (pathCertRun b (pathCertNext a b s) bs).2.2 = _
      rw [ih]
      simp only [pathCertDelta, ← Finset.sum_add_distrib]
      apply Finset.sum_congr rfl
      intro j hj
      simp only [pathCertWord, pathGreedyRun, pathCertNext_bit, Nat.cast_add]
      simp only [Nat.cast_ite, Nat.cast_one, Nat.cast_zero]
      change (if pathCertTake a b s j then pathCertSign j else 0) + pathCertSign j * (pathGreedyRun (pathCertTake a b s j) (pathCertWord b bs j) : ℤ) = pathCertSign j * ((if pathCertTake a b s j then (1 : ℤ) else 0) + (pathGreedyRun (pathCertTake a b s j) (pathCertWord b bs j) : ℤ))
      split_ifs <;> ring
See it in the graphDiscuss this resultChallenge it