path_cert_word_eq_cut_word
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_word
path_cut_word n Sis the length-(n-1) boolean word whose j-th letter records whether the j-th edge of the pathpathGraph 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.
The lemma statement sets up index bounds.
Bound checks for the lemma statement.
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
Base case m = 0.
Simp.
induction m with | zero => simp [pathCertWord]
Inductive step.
Inductive step.
| 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⟩)Main theorem bounds and cases.
Cases on n.
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
Inductive case of the main theorem.
Simpa.
| succ m => simpa [path_cut_word] using cert_word_of_fn_scratch m color j
- Unresolved check: step 3's explanation only repeats its claim: say how it is shown
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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