Lemma 4.1 (Witness invariant): for every candidate
ProvedTreeEquivalenceHORS.Equivalence.lemma_4_1counter-machinesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1witness
Let be a two-counter program and a finite candidate prefix, with guard weight (Equation (13)). Then
that is, the weight is nonzero exactly when every guessed guard along is correct. Illegal candidates, including those whose virtual counters have become negative, have weight zero.
This is the first-error argument that lets the compiled trees detect illegal guesses arithmetically.
Differences from the source:
- encoding: candidate words over {1, 2}; virtual configurations in ℕ × ℤ² →
List ChoicewithChoice.one= 1,Choice.two= 2, read left to right; configurationsℕ × ℤ × ℤ; δ (undefined outside I_M) returns its argument there; reason: the value of δ outside I_M is never used on candidates, which extend only active prefixes
Preamble
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_Machines
Formal statement
namespace TreeEquivalenceHORS.Equivalence
/-- **Lemma 4.1 (Witness invariant)** (printed p. 13 / PDF p. 15). For every candidate prefix
`v ∈ C_M`, the guard weight is nonzero exactly on legal prefixes: `W_M(v) ≠ 0 ⟺ v ∈ L_M`. -/
theorem lemma_4_1 (M : Machine) (v : List Choice) (hv : M.IsCand v) :
M.weight v ≠ 0 ↔ M.IsLegal v := by sorry
end TreeEquivalenceHORS.Equivalence
Source
Mingkun Xiao, Yixuan Sun, Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable, STOC 2027 submission #421 (October 2026), source.pdf SHA-256 e875d09ced029e3f5cb114abba049e4a2b1bdaa9b064c98b0d71f2ec7451c7af, Lemma 4.1, printed p. 13 / PDF p. 15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.