AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it