Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.6 — correctness of the actual one-level algorithm

Proved
CatalyticTreeEval.Main.lemma_4_6

by mikedeng1 · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

catalytic-computingcomplexity-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let a frame satisfy the section-four algebraic setting: positive label length, m>1m>1m>1, a noncancelling score set containing zero, an SSS-matching family, an (S+S)(S+S)(S+S)-decoder and the stated access-space scale bound. Let WWW be any output vector family, fff any two-input label table, x0,x1x_0,x_1x0​,x1​ fixed hidden labels, α\alphaα any scalar and RRR any initial register state.

The explicitly defined Section 4.2 program, including the four-query inner-product prefix and every term and candidate-pair iteration, has the net effect

R⟼R with position 2 replaced by R2+αWf(x0,x1).R\longmapsto R\text{ with position 2 replaced by }R_2+\alpha W_{f(x_0,x_1)}.R⟼R with position 2 replaced by R2​+αWf(x0​,x1​)​.

Both child registers remain unchanged at termination. Its child-operation list admits exact inverse pairs. No arbitrary transformation assumed to have this effect is substituted for the actual algorithm. This is its algebraic correctness assertion; charged implementation and resources are supplied by Theorem 4.4.

Differences from the source:

  • encoding: finite binary labels, tuples and printing algorithms with O/poly resource notation → Fin indices, fixed self-delimiting binary encodings and charged finite-machine runs with positive uniform constants; reason: these encode the same objects; constants precede all varying construction parameters and all runs
  • generalization: the uniform setting above the algorithm → the same algebraic setting without computational-access hypotheses; reason: only algebraic correctness is asserted here; the literal operation list is defined even without efficient printers, and Theorem 4.4 retains all access hypotheses
Preamble
import Definitions.Def_CatalyticTreeEval_Main_Framework

set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main

theorem lemma_4_6 (F : Frame) (hF : F.valid)
    (W : Label F.l → Vec F.m F.d) (f : Label F.l → Label F.l → Label F.l)
    (x : Fin 2 → Label F.l) (α : ZMod F.m) (R : Registers F.m F.d) :
    execute F.U F.V x R (oneLevelProgram F.U F.V W F.D f x α R) =
      addAt R 2 (α • W (f (x 0) (x 1))) ∧
    InversePairs (oneLevelProgram F.U F.V W F.D f x α R) := by sorry

end CatalyticTreeEval.Main
Source
Alexandra Henzinger, Edward Pyne, Seyoon Ragavan, Catalytic Tree Evaluation from Matching Vectors, STOC 2027 submission #533 (October 2026), Lemma 4.6, printed p. 24 (PDF p. 26); source.pdf SHA-256 17c3a71f0fb5afe2456558477e16fbac4200191e6e68f0facf212e24cb4ef238
Human review
  • Endorsed by Shuze Chen · Nov 12, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 12, 2026

    Confirmed by the mission captain (proposal self-audit).

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