Lemma 3.20 (used in the proof of Theorem 3.4) — uniform full-residue decoder
OpenCatalyticTreeEval.Main.Supplement.lemma_3_20complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1tree-evaluation
For every odd prime supplied as input, there are shifts and term functions forming a decoder for the entire residue set , with a single term printer, uniform over , using
For every nonzero and every , its terms obey , while . The printer outputs both and on request. This full-residue decoder supports the squared-distance ordinary-space construction.
Differences from the source:
- encoding: asymptotic algorithmic resource bounds → a finite binary machine and positive uniform constants, with fixed polynomial degrees where needed; reason: expands O/poly using actual transitions and visited work cells; constants precede varying inputs and tapes
- encoding: binary parameters and one-based finite indices → self-delimiting binary headers, zero-based Fin indices and the published printer requests; reason: encodes the same finite data with linear bit-length overhead and no change to the space class
- encoding: log m → L(m); reason: equivalent up to an absolute constant on odd primes m≥3
Preamble
import Definitions.Def_CatalyticTreeEval_Main_Decoder set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main.Supplement
theorem lemma_3_20 :
∃ (MD : Machine) (C : ℝ), 0 < C ∧
∀ m : ℕ, Nat.Prime m → Odd m → ∃ k : ℕ, k ≤ m ∧
∃ D : Decoder m k, IsDecoder Set.univ D ∧
DecoderAccess MD (natCode m) D (C * lg m) := by sorry
end CatalyticTreeEval.Main.Supplement
Source
Alexandra Henzinger, Edward Pyne, Seyoon Ragavan, Catalytic Tree Evaluation from Matching Vectors, STOC 2027 submission #533 (October 2026), canonical source.pdf SHA-256 17c3a71f0fb5afe2456558477e16fbac4200191e6e68f0facf212e24cb4ef238, Lemma 3.20, printed p. 20 (PDF p. 22)