AFTD Auto-Formalizing Theoretical Domains

path_cert_word_eq_cut_word

theoremverified

The Boolean edge word used by the finite-state certificate is the ordinary path cut word of the corresponding color mask.

Statement

open scoped Classical in
theorem path_cert_word_eq_cut_word (n : ℕ) (hn : 0 < n) (color : Fin n → Fin 4) (j : Fin 7) : pathCertWord (color ⟨0, hn⟩) (List.ofFn fun k : Fin (n - 1) => color ⟨k.val + 1, by omega⟩) j = path_cut_word n (Finset.univ.filter fun v => Nat.testBit (pathCertMask j) (color v).val)
Source
List-index bridge from the Lean-checked word inequality to the pure-path cut-rank route for OP-827.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • pathCertWordThe sequence of cut-crossing flags for one party-union mask along a colored vertex word.
  • pathCertMaskThe seven party-union masks for a four-color path word.
  • path_cut_wordpath_cut_word n S is the length-(n-1) boolean word whose j-th letter records whether the j-th edge of the path pathGraph n (i.e. the…
Used by 2
  • 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…
  • path_cut_word_count_cancelFor a four-partition A,B,C,D of the vertices of the path P_n, the total number of edges crossing the cuts defined by A, B, C, D equals the…

The proof, explained

The Boolean edge word used by the finite-state certificate is shown to equal the ordinary path cut word of the corresponding color mask. This is proved first by induction on the path length m in a helper lemma, where unfolding the definitions of pathCertWord and List.ofFn reduces the step to the induction hypothesis. The main theorem then follows immediately by case analysis on n > 0 and applying the helper lemma with the definition of path_cut_word.

  1. The lemma statement sets up index bounds.

    Bound checks for the lemma statement.

    lines 3–7

    lemma cert_word_of_fn_scratch (m : ℕ) (f : Fin (m+1) → Fin 4) (j : Fin 7) :
        pathCertWord (f ⟨0, by omega⟩) (List.ofFn fun k : Fin m => f ⟨k.val+1, by omega⟩) j =
          List.ofFn (fun k : Fin m =>
            (Nat.testBit (pathCertMask j) (f ⟨k.val, by omega⟩).val !=
              Nat.testBit (pathCertMask j) (f ⟨k.val+1, by omega⟩).val)) := by
  2. Base case m = 0.

    Simp.

    lines 8–9

      induction m with
      | zero => simp [pathCertWord]
  3. Inductive step.

    Inductive step.

    lines 10–13

      | succ m ih =>
        rw [List.ofFn_succ, pathCertWord, List.ofFn_succ]
        congr 1
        simpa using ih (fun k : Fin (m+1) => f ⟨k.val+1, by omega⟩)
  4. Main theorem bounds and cases.

    Cases on n.

    lines 15–18

    open scoped Classical in
    theorem path_cert_word_eq_cut_word (n : ℕ) (hn : 0 < n) (color : Fin n → Fin 4) (j : Fin 7) : pathCertWord (color ⟨0, hn⟩) (List.ofFn fun k : Fin (n - 1) => color ⟨k.val + 1, by omega⟩) j = path_cut_word n (Finset.univ.filter fun v => Nat.testBit (pathCertMask j) (color v).val) := by
      cases n with
      | zero => omega
  5. Inductive case of the main theorem.

    Simpa.

    lines 19–20

      | succ m =>
        simpa [path_cut_word] using cert_word_of_fn_scratch m color j

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open scoped Classicallemma cert_word_of_fn_scratch (m : ℕ) (f : Fin (m+1) → Fin 4) (j : Fin 7) :    pathCertWord (f ⟨0, by omega⟩) (List.ofFn fun k : Fin m => f ⟨k.val+1, by omega⟩) j =      List.ofFn (fun k : Fin m =>        (Nat.testBit (pathCertMask j) (f ⟨k.val, by omega⟩).val !=          Nat.testBit (pathCertMask j) (f ⟨k.val+1, by omega⟩).val)) := by  induction m with  | zero => simp [pathCertWord]  | succ m ih =>    rw [List.ofFn_succ, pathCertWord, List.ofFn_succ]    congr 1    simpa using ih (fun k : Fin (m+1) => f ⟨k.val+1, by omega⟩)open scoped Classical intheorem path_cert_word_eq_cut_word (n : ℕ) (hn : 0 < n) (color : Fin n → Fin 4) (j : Fin 7) : pathCertWord (color ⟨0, hn⟩) (List.ofFn fun k : Fin (n - 1) => color ⟨k.val + 1, by omega⟩) j = path_cut_word n (Finset.univ.filter fun v => Nat.testBit (pathCertMask j) (color v).val) := by  cases n with  | zero => omega  | succ m =>    simpa [path_cut_word] using cert_word_of_fn_scratch m color j
See it in the graphDiscuss this resultChallenge it