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