Lemma 5.4 (Polynomial realization): and
ProvedTreeEquivalenceHORS.Equivalence.lemma_5_4church-numeralslogical-relationsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
In every compiled scheme :
- the seeds satisfy ;
- for every and all closed ,
Here (Equation (19)) quantifies over all , including , and all numeral representations of them. The stored polynomial terms therefore track , whose difference is .
Differences from the source:
- encoding: Num(t, n) and Pol_m(p, q) are defined for closed terms t : N and p, q : P →
NumandPolinclude the conjunctstypeOf [] t = some N(resp.P); reason: the source defines the relations only on closed typed terms; the conjunct records that domain
Preamble
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_Compiler
Formal statement
namespace TreeEquivalenceHORS.Equivalence
/-- **Lemma 5.4 (Polynomial realization)** (printed p. 18 / PDF p. 20), in every compiled scheme:
the seeds satisfy `Pol₀(Seed₊, Seed₋)`, and `Pol_m(p, q) ⟹ Pol_{m+1}(Next₊ p q, Next₋ p q)`. -/
theorem lemma_5_4 (side : Side) (M : Machine) :
let G := compile side M
Pol G 0 (.nt iSeedP) (.nt iSeedM) ∧
∀ (m : ℕ) (p q : Tm), Pol G m p q →
Pol G (m + 1) (Tm.apps (.nt iNextP) [p, q]) (Tm.apps (.nt iNextM) [p, q]) := 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 5.4, printed p. 18 / PDF p. 20
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.