Uniform logarithmic-space sparse printer for the composite detector
OpenCatalyticTreeEval.Main.composite_weight_detector_printcatalytic-computationmatching-vectors
There are one native binary machine and a positive constant , fixed before every prime list and parameter choice, that print the sparse code of the explicit CRT detector. For distinct primes , and , the addressed work space is bounded by
The input contains the encoded prime list, exponents, and . Printing is the native finite-transition-table predicate from the mission, including halting and the full trajectory workspace bound. Together with the algebraic properties this gives the exact uniform construction required in Corollary B.6.
Preamble
import Definitions.Def_CatalyticTreeEval_CompositeDetector set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main
theorem composite_weight_detector_print :
∃ (M : Machine) (C : ℝ), 0 < C ∧
∀ (t : ℕ) (p e : Fin t → ℕ) (w H : ℕ) (hp : PrimeData p),
1 ≤ w → w ≤ H → w < ∏ i, p i ^ e i →
PolyPrint M (primeCode p ++ natsCode ((List.finRange t).map e ++ [w,H]))
(compositeWeightDetector p e hp w H)
(C * (delta p e * log₂ H + log₂ (modulus p))) := by sorry
end CatalyticTreeEval.MainSource
Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, Appendix B, Corollary B.6.