Uniform sparse printing of the explicit prime-power weight detector
OpenCatalyticTreeEval.Main.weight_detector_printOne finite binary machine prints a sparse presentation of the specified prime-power weight detector for every prime, exponent, target weight and positive variable count. Its work prefix is bounded by a uniform constant times p^e log2(H+1) plus log2 p. The printer must output the explicit detector used by the algebraic correctness theorem. This is the computational component of Lemma B.5.
Preamble
import Definitions.Def_CatalyticTreeEval_WeightDetector set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main
/-- Uniform sparse printing is separate from the verified detector's algebraic properties. -/
theorem weight_detector_print :
∃ (M : Machine) (C : ℝ), 0 < C ∧
∀ (p e w H : ℕ), Nat.Prime p → 1 ≤ H →
PolyPrint M (natsCode [p,e,w,H]) (weightDetector p e w H)
(C * ((p ^ e : ℕ) * log₂ (H + 1) + log₂ p)) := by sorry
end CatalyticTreeEval.Main
Source
Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, Appendix B, Lemmas B.4 and B.5.