Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform logarithmic-space sparse printer for the composite detector

Open
CatalyticTreeEval.Main.composite_weight_detector_print

by sragavan · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

catalytic-computationmatching-vectors

There are one native binary machine and a positive constant CCC, fixed before every prime list and parameter choice, that print the sparse code of the explicit CRT detector. For distinct primes pip_ipi​, 1≤w≤H1\le w\le H1≤w≤H and w<∏ipieiw<\prod_i p_i^{e_i}w<∏i​piei​​, the addressed work space is bounded by

C(Δlog⁡2H+log⁡2m),m=∏ipi,Δ=max⁡ipiei.C\bigl(\Delta\log_2 H+\log_2 m\bigr),\qquad m=\prod_i p_i,\quad \Delta=\max_i p_i^{e_i}.C(Δlog2​H+log2​m),m=i∏​pi​,Δ=imax​piei​​.

The input contains the encoded prime list, exponents, www and HHH. 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.Main
Source
Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, Appendix B, Corollary B.6.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me