Lemma 4.6 — correctness of the actual one-level algorithm
ProvedCatalyticTreeEval.Main.lemma_4_6Let a frame satisfy the section-four algebraic setting: positive label length, , a noncancelling score set containing zero, an -matching family, an -decoder and the stated access-space scale bound. Let be any output vector family, any two-input label table, fixed hidden labels, any scalar and 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
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
import Definitions.Def_CatalyticTreeEval_Main_Framework set_option autoImplicit false
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.