pathCertNext_bit
theoremverified
Each bit of the automaton state records the corresponding greedy matching choice.
Statement
open scoped BigOperators in theorem pathCertNext_bit (a b : Fin 4) (s : Fin 128) (j : Fin 7) : Nat.testBit (pathCertNext a b s).val j.val = pathCertTake a b s 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 2
- pathCertNextThe seven greedy-matching flags after appending a colored vertex.
- pathCertTakeGreedy matching choice for one cut when a path edge is appended.
- Used by 1
- pathCertRun_eq_greedyThe automaton output equals the signed sum of seven greedy edge counts.
Lean source view module on GitHub
open scoped BigOperators in theorem pathCertNext_bit (a b : Fin 4) (s : Fin 128) (j : Fin 7) : Nat.testBit (pathCertNext a b s).val j.val = pathCertTake a b s j := by set_option maxHeartbeats 10000000 in set_option maxRecDepth 100000 in revert a b s j decide