Theorem 9.1 — deterministic sparse signed-integer recovery
OpenHypRecov.Supplement.theorem_9_1hypergraphslinear-sketchingp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-recoverystreaming-algorithms
Fix and , and put
There is one uniform deterministic additive sketch of an integer -fragment stream whose terminal vector is . Whenever and , it returns every nonzero -set coordinate and its exact signed value.
State, deterministic description, output and decoding workspace use bits; initialization, unit updates and decoding are polynomial in , and a general increment adds polynomial dependence on its bit length. Since , the stated simplified space bound follows. For , is the least possible order even for zero-one -sparse vectors.
Differences from the source:
- encoding: an integer vector indexed by -subsets → a total function on vertex subsets required to vanish off the -uniform slice; reason: the two representations have exactly the same coordinates
- encoding: deterministic additive sketch and big-O/polynomial bounds → uniform TM2 machines, binary increment/output encodings, explicit absolute constants and all-stack bounds; reason: this makes the paper's resource claims and per-unit/general-increment distinction kernel-auditable without changing an instance
Preamble
import Mathlib import Definitions.Def_HypRecov_Supplement_QuerySketchGuarantee set_option autoImplicit false
Formal statement
namespace HypRecov.Supplement
/-- **Theorem 9.1 (Sparse integer recovery from anonymous projections).** Zhang, Chen, Shen,
*Hypergraph Recovery from Anonymous Projection Streams*, STOC 2027 submission (manuscript sha256
719dcfff…), Theorem 9.1, p.22 (PDF p.23).
At order `q=min{r,1+floor(log₂ K)}`, one uniform deterministic additive sketch exactly recovers
every signed integer vector on `r`-sets with support at most `K` and coefficient magnitude at most
`W`. With `L=ceil(log₂(2W+1))` and the displayed 2-adic precision `a`, all state, deterministic
description, output and workspace use `O(K r log(n+1) (a+L))` bits; initialization, unit updates and
decoding are uniformly polynomial, and a general increment is polynomial also in its bit length.
The clause `a ≤ floor(log₂ r)` gives the theorem's simplified space bound. For `n ≥ 2r`, `q` is
the least possible order even on zero-one vectors.
**Formalization Note.** The latent vector is not restricted to a hypergraph: it is an arbitrary
integer-valued function, zero off the `r`-uniform slice. `VectorSketchGuarantee` includes state
subtraction, so it also covers reconciliation of two dense inputs. -/
theorem theorem_9_1 :
∃ (A : HypRecov.LinearSketch) (C c : ℕ),
∀ (n r K W : ℕ), r ≤ n → 1 ≤ r → 1 ≤ K → 1 ≤ W →
let q := sparseOrder r K
let L := Nat.clog 2 (2 * W + 1)
let a := projectionPrecision r q
VectorSketchGuarantee A C c n r K W q a L ∧
a ≤ Nat.log 2 r ∧
(2 * r ≤ n →
IsLeast {q' : ℕ | 1 ≤ q' ∧ q' ≤ r ∧ DeterminesSparseInteger n r K q'} q)
:= by sorry
end HypRecov.Supplement
Source
Zhang, Chen, Shen, Hypergraph Recovery from Anonymous Projection Streams, STOC 2027 submission (manuscript sha256 719dcfff4dc2eba2d8c5a3c51679a08cfb11f076546dea963c6376a2b9da2c82), Theorem 9.1, p.22 (PDF p.23)