§2.4, p.5 — the fiber , shattered sets, exact extensions, and the inputs of Theorem 2.3
DefinitionPairwiseRealize_Supplement_Fiberboolean-statisticsp2o-gran-per-chapterp2o-plan-paperp2o-v1shatteringturing-machine
Let be the cube of rows and , , the pairwise statistics of a row. For an integer target the fiber is
Each is identified with the set , so is the family of exact realizations of by distinct rows of the full cube.
- Given and an assignment , a set is an exact extension of if and, for every , exactly when .
- is shattered by if every assignment has an exact extension. The positions of are rows (entries of a truth table), not the input coordinates.
- The construction input for , , is and in binary followed by the coordinates of as signed binary numerals; the extension input appends the membership table of .
These objects state Theorem 2.3: a single set of positions on which every bit pattern can be completed to an exact realization.
Formalization Note An assignment is a function on all rows of which only the values on matter. The encodings reuse encodeNat, encodeInt (ContingencyTables) and featList, tableCode (PairwiseRealize.Model, PairwiseRealize.Machine).
Definition code
import Mathlib
import Definitions.Def_ContingencyTables
import Definitions.Def_PairwiseRealize_Model
import Definitions.Def_PairwiseRealize_Machine
namespace PairwiseRealize.Supplement
/-!
# The fiber `F(b)`, shattered sets, exact extensions, and the inputs of Theorem 2.3
K. Shi, H. Sun, *Robust Exact Realization of Pairwise Boolean Statistics*, STOC 2027 submission
(manuscript sha256 62090516…), §2.4 "Prescribed entries and fiber size", printed p.5 (PDF p.6):
"Let F(b) = {F : V → {0,1} : Σ_x F(x) w_x = b}. A set Q ⊆ V is shattered by this fiber if every
assignment Q → {0,1} occurs as the restriction of one of its members. Here a position in Q is one of
the N possible input rows of a truth table, not one of its n input coordinates." Theorem 2.3, p.5:
"Given b and an integer promised lower bound δ, a deterministic algorithm constructs Q … Given any
assignment α : Q → {0,1}, the algorithm finds an exact extension".
**Formalization Note** A member `F : V → {0,1}` of the fiber is identified with the set
`S = F⁻¹(1) ⊆ V`, so `F(b)` is the finset of all `S` with `Σ_{x∈S} w_x = b`, i.e. the exact
realizations of `b` in the full cube (`IsRealization n univ b S` of the published
`PairwiseRealize.Model`). An assignment `α : Q → {0,1}` is a function `Row n → Bool` of which only the
values on `Q` matter. The algorithm inputs reuse the published encodings of `PairwiseRealize.Machine`
and `ContingencyTables`: `n` and `δ` in binary, the coordinates of `b` as signed binary numerals in the
order `featList n`, and the assignment `α` as the membership table of `{x ∈ Q : α x = 1}`.
-/
open OAI.MatchingFPRAS
/-- The fiber `F(b) = {F : V → {0,1} : Σ_x F(x) w_x = b}` (§2.4, p.5), each `F` identified with
`S = F⁻¹(1)`: the finset of exact realizations of `b` by distinct rows of the full cube `V`. -/
noncomputable def fiber (n : ℕ) (b : Feat n → ℤ) : Finset (Finset (Row n)) := by
classical
exact Finset.univ.filter fun S => IsRealization n Finset.univ b S
/-- `S` is an exact extension of the assignment `α` on `Q` for the target `b`: `S` is a member of
the fiber `F(b)` (`Σ_{x∈S} w_x = b`) whose indicator agrees with `α` at every position `x ∈ Q`. -/
def IsExtension (n : ℕ) (b : Feat n → ℤ) (Q : Finset (Row n)) (α : Row n → Bool)
(S : Finset (Row n)) : Prop :=
IsRealization n Finset.univ b S ∧ ∀ x ∈ Q, (x ∈ S ↔ α x = true)
/-- `Q ⊆ V` is shattered by the fiber `F(b)` (§2.4, p.5): every assignment `Q → {0,1}` is the
restriction to `Q` of some member of `F(b)`. Positions are rows `x ∈ V`, not input coordinates. -/
def IsShattered (n : ℕ) (b : Feat n → ℤ) (Q : Finset (Row n)) : Prop :=
∀ α : Row n → Bool, ∃ S, IsExtension n b Q α S
/-- The input of the construction algorithm of Theorem 2.3: `n` and the integer promised lower bound
`δ` in binary, then the coordinates of the integer target `b` in the order `featList n`. -/
def promiseInput (n δ : ℕ) (b : Feat n → ℤ) : List Symbol :=
encodeNat n ++ encodeNat δ ++ ((featList n).map fun f => encodeInt (b f)).flatten
/-- The input of the extension algorithm of Theorem 2.3: the construction input followed by the
assignment `α : Q → {0,1}`, written as the membership table of `{x ∈ Q : α x = 1}`. -/
def extensionInput (n δ : ℕ) (b : Feat n → ℤ) (Q : Finset (Row n)) (α : Row n → Bool) :
List Symbol :=
promiseInput n δ b ++ tableCode n (Q.filter fun x => α x = true)
end PairwiseRealize.Supplement
Source
Shi, Sun, Robust Exact Realization of Pairwise Boolean Statistics, STOC 2027 submission (sha256 62090516…), §2.4, p.5 (PDF p.6), definition of F(b) and of shattering; Theorem 2.3, p.5 (PDF p.6), the algorithm inputs