pathCertOddRunIneq
theoremverified
For any four-color path word, the signed sum of odd crossing-run counts for the seven masks is nonpositive.
Statement
open scoped BigOperators in theorem pathCertOddRunIneq (a : Fin 4) (xs : List (Fin 4)) : (∑ j : Fin 7, pathCertSign j * (odd_run_count (pathCertWord a xs j) : ℤ)) ≤ 0
- 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
- pathCertWordThe sequence of cut-crossing flags for one party-union mask along a colored vertex word.
- pathCertSignThe signs of the seven terms in the tripartite cut-rank sum.
- pathCertRun_eq_greedyThe automaton output equals the signed sum of seven greedy edge counts.
- pure_path_automaton_nonpositiveFor every four-color word, the signed sum of seven greedy path-edge matching counts is nonpositive.
- pathCertWordCountCancelAcross a four-color word the signed sum of the seven crossing-edge counts vanishes.
- pathGreedyRun_eq_count_and_oddTwice the greedy count equals the number of true edges plus the number of odd true runs.
- odd_run_count
odd_run_count lis the number of maximal runs oftruein the boolean wordlwhose length is odd. The finalfalseis appended so… - pathGreedyRunGreedily count disjoint true edges in a Boolean edge word.
- pathCertRunRun the seven simultaneous greedy matching counters on a colored path suffix.
- Used by 1
- path_cut_word_odd_run_ineqFor a four-partition A,B,C,D of the vertices of the path P_n, the sum of the numbers of maximal odd-length crossing runs for A, B, C and D…
Lean source view module on GitHub
open scoped BigOperators in theorem pathCertOddRunIneq (a : Fin 4) (xs : List (Fin 4)) : (∑ j : Fin 7, pathCertSign j * (odd_run_count (pathCertWord a xs j) : ℤ)) ≤ 0 := by have hbound : (∑ j : Fin 7, pathCertSign j * (pathGreedyRun false (pathCertWord a xs j) : ℤ)) ≤ 0 := by simpa [pathCertRun_eq_greedy] using pure_path_automaton_nonpositive a xs have hcount := pathCertWordCountCancel a xs have hid : (2 : ℤ) * (∑ j : Fin 7, pathCertSign j * (pathGreedyRun false (pathCertWord a xs j) : ℤ)) = (∑ j : Fin 7, pathCertSign j * ((pathCertWord a xs j).countP id : ℤ)) + (∑ j : Fin 7, pathCertSign j * (odd_run_count (pathCertWord a xs j) : ℤ)) := by rw [Finset.mul_sum, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro j hj have h := pathGreedyRun_eq_count_and_odd (pathCertWord a xs j) have hz : (2 : ℤ) * (pathGreedyRun false (pathCertWord a xs j) : ℤ) = ((pathCertWord a xs j).countP id : ℤ) + (odd_run_count (pathCertWord a xs j) : ℤ) := by exact_mod_cast h calc _ = pathCertSign j * (2 * (pathGreedyRun false (pathCertWord a xs j) : ℤ)) := by ring _ = pathCertSign j * (((pathCertWord a xs j).countP id : ℤ) + (odd_run_count (pathCertWord a xs j) : ℤ)) := by rw [hz] _ = _ := by ring omega