Uniform polynomial-time access to the explicit canonical decoder
OpenCatalyticTreeEval.Main.canonical_decoder_accesscatalytic-computationmatching-vectors
There exist a single finite binary machine , positive constants , and a positive integer , all fixed before the prime list. For every list of distinct odd primes, , decoder index , and query residue , the machine prints the two scalar fields of the already fixed canonical decoder. Its full addressed work prefix is at most and its number of actual transitions is at most . The request uses exactly decoderRequest (primeCode p) j.val z.val, with the published binary encodings. This is the native computational obligation remaining in Lemma 3.19; no per-parameter machine, advice, assumed arithmetic oracle, or arbitrary enumeration is supplied.
Preamble
import Definitions.Def_CatalyticTreeEval_DecoderCRT set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main
theorem canonical_decoder_access :
∃ (M : Machine) (Cs Ct : ℝ) (q : ℕ), 0 < Cs ∧ 0 < Ct ∧ 0 < q ∧
∀ (t : ℕ) (p : Fin t → ℕ) (hp : OddPrimeData p),
∀ j z, PrintsIn M (decoderRequest (primeCode p) j.val z.val)
(decoderOutput (DecoderConstruction.canonicalDecoder p hp.1) j z)
(Cs * log₂ (modulus p)) (Ct * (1 + log₂ (modulus p)) ^ q) := by sorry
end CatalyticTreeEval.MainSource
Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, Section 3.4, Lemma 3.19.