CRT combination of prime-power weight detectors
DefinitionCatalyticTreeEval_CompositeDetectorcatalytic-computationtree-evaluation
For distinct primes and prime-coefficient polynomials , form a polynomial modulo by lifting every coefficient through the Chinese remainder map. The composite weight detector applies this construction to the explicit prime-power detectors. The support is contained in the union of their supports; its evaluation and degree properties are proved separately.
Definition code
import Definitions.Def_CatalyticTreeEval_WeightDetector
import Definitions.Def_CatalyticTreeEval_CRT
set_option autoImplicit false
namespace CatalyticTreeEval.Main
/-- Lift a family of prime-coefficient polynomials coefficient by coefficient. -/
noncomputable def crtPolynomial {t H : ℕ} (p : Fin t → ℕ) (hp : PrimeData p)
(f : (i : Fin t) → Poly (p i) H) : Poly (modulus p) H := by
classical
exact ∑ v ∈ Finset.univ.biUnion (fun i => (f i).support),
MvPolynomial.monomial v (CRT.crtLift p hp (fun i => MvPolynomial.coeff v (f i)))
/-- Composite detector obtained by CRT from the explicit prime-power detectors. -/
noncomputable def compositeWeightDetector {t : ℕ} (p e : Fin t → ℕ)
(hp : PrimeData p) (w H : ℕ) : Poly (modulus p) H :=
crtPolynomial p hp (fun i => weightDetector (p i) (e i) w H)
end CatalyticTreeEval.Main
Source
Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, Appendix B, Corollary B.6.