Explicit canonical-sumset decoder: full algebraic correctness
ProvedCatalyticTreeEval.Main.canonical_decoder_propertiescatalytic-computationmatching-vectors
Let be distinct odd primes and . The explicit decoder indexed by base-3 vectors has exactly terms. This theorem proves its cancellation and normalization, identifies the canonical sumset with residues whose projections all lie in , and proves that the original canonical set is noncancelling. The decoder is the fixed construction in Def_CatalyticTreeEval_DecoderCRT; uniform native term access is a separate child.
Preamble
import Definitions.Def_CatalyticTreeEval_DecoderCRT set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main
theorem canonical_decoder_properties {t : ℕ} (p : Fin t → ℕ) (hp : OddPrimeData p) :
(∀ z : ZMod (modulus p), z ∈ sumset (canonical p (modulus p)) ↔
∀ i, z.val % p i = 0 ∨ z.val % p i = 1 ∨ z.val % p i = 2) ∧
IsDecoder (sumset (canonical p (modulus p)))
(DecoderConstruction.canonicalDecoder p hp.1) ∧
Noncancelling (canonical p (modulus p)) := 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.