Lemma 3.12 (used in the proof of Theorem 3.4) — uniform squared-distance matching vectors
OpenCatalyticTreeEval.Main.Supplement.lemma_3_12complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1tree-evaluation
Let be positive integers and an odd prime, all supplied as input. Put and . There is an -matching-vector family of exact size in dimension , and a single fixed printer, uniform over all these parameters, with
The printer receives the parameters and the requested indices and outputs both full vectors. This squared-distance construction supports the ordinary-space algorithms. The domain includes and does not impose the stronger inequality .
Differences from the source:
- encoding: asymptotic algorithmic resource bounds → a finite binary machine and positive uniform constants, with fixed polynomial degrees where needed; reason: expands O/poly using actual transitions and visited work cells; constants precede varying inputs and tapes
- encoding: binary parameters and one-based finite indices → self-delimiting binary headers, zero-based Fin indices and the published printer requests; reason: encodes the same finite data with linear bit-length overhead and no change to the space class
- encoding: log N+log m → L(N)+L(m); reason: the positive-log convention includes the singleton family M=1 with the same O(log N+log m) bound since m≥3
Preamble
import Definitions.Def_CatalyticTreeEval_Main_Supplement_UniformConstructions set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main.Supplement
theorem lemma_3_12 :
∃ (MV : Machine) (C : ℝ), 0 < C ∧
∀ M w m : ℕ, 0 < M → 0 < w → Nat.Prime m → Odd m → w * M ^ 2 < m →
∃ U V : Fin (M ^ w) → Vec m (w + 2),
SMatching (intervalScores m (w * M ^ 2)) U V ∧
VectorAccess MV (natsCode [M,w]) U V (C * (lg (M ^ w) + lg m)) := by sorry
end CatalyticTreeEval.Main.Supplement
Source
Alexandra Henzinger, Edward Pyne, Seyoon Ragavan, Catalytic Tree Evaluation from Matching Vectors, STOC 2027 submission #533 (October 2026), canonical source.pdf SHA-256 17c3a71f0fb5afe2456558477e16fbac4200191e6e68f0facf212e24cb4ef238, Lemma 3.12, printed p. 17 (PDF p. 19)