Compressed assertions remain close to the canonical completion spaces
ProvedWeldedPath.compressed_assertion_projection_boundcompressed-oraclesincidence-operatorsoperator-norms
Let be nonnegative integers with , and fix a query input . Let project onto databases of size , and let be the canonical completion space. For each response , define the compressed assertion and its component outside by
For every ,
For every family with ,
These column and row estimates control the part of a compressed assertion that leaves the canonical completion spaces. The degree-zero case is included. All operators are the canonical database operators; comparison of the components within the completion spaces is a separate estimate.
Preamble
import Mathlib import Definitions.Def_WeldedPath_exactCpO set_option autoImplicit false open Classical open scoped BigOperators
Formal statement
namespace WeldedPath
theorem compressed_assertion_projection_bound (s r : ℕ) (hsmall : 3*r+2 ≤ s) (x : Fin s) :
let K := fun j : ℕ => (ContinuousLinearMap.adjoint (Gam s j)).range
let L := fun j : ℕ => diagProj (fun I : InjDb s => I.size=j)
let A := fun y : Fin s => (pC s x).comp
((diagProj (fun I : InjDb s => I x=some y)).comp (pC s x))
(∀ a : Hil (InjDb s), a∈K r →
(∑ y : Fin s,
(‖L (r+1) (A y a)-(K (r+1)).starProjection (L (r+1) (A y a))‖^2+
‖L r (A y a)-(K r).starProjection (L r (A y a))‖^2)) ≤
204*((s-r : ℕ) : ℝ)⁻¹*‖a‖^2) ∧
(∀ a : Fin s → Hil (InjDb s), (∀ y,a y∈K r) →
‖(∑ y : Fin s,L (r+1) (A y (a y)))-
(K (r+1)).starProjection (∑ y : Fin s,L (r+1) (A y (a y)))‖^2+
‖(∑ y : Fin s,L r (A y (a y)))-
(K r).starProjection (∑ y : Fin s,L r (A y (a y)))‖^2 ≤
204*((s-r : ℕ) : ℝ)⁻¹*(∑ y : Fin s,‖a y‖^2)) := by
sorry
end WeldedPath
Source
Carolan and Majenz, Compressed Permutation Oracles Revisited, https://arxiv.org/html/2609.28469v1, Lemma 4.13 and the deduction of equation (23), with a relaxed absolute constant. Canonical WeldedPath compression and completion operators are from https://arxiv.org/html/2611.05912v1. This result concerns the component outside the completion range; it does not assert the full exact-versus-compressed query comparison.