AFTD Auto-Formalizing Theoretical Domains

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_countodd_run_count l is the number of maximal runs of true in the boolean word l whose length is odd. The final false is 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
See it in the graphDiscuss this resultChallenge it