The uniformly extended distributions and
DefinitionLiftSAParity_Supplement_extProbLet be a family of distributions on blockwise partial assignments over blocks of variables, and let .
The distribution over total assignments samples and sets every remaining variable uniformly at random. Thus
For a blockwise partial assignment with , the distribution is conditioned on agreeing with . It is well-defined when and some with agrees with . The distribution extends uniformly, so
These are the sampling laws in the definition of fooling distributions (Definition 5.3) and of the measure of §5.3.
Formalization Note extFrac τ A is the fraction of the extensions of that lie in ; extProb D I A and condExtProb D I σ A are the two probabilities above, and CondWellDefined d D I σ is the well-definedness condition. The conditional probability is used only under that condition, where its denominator is positive.
import Mathlib
import Definitions.Def_LiftSAParity_Supplement_IsBlockLocalDist
namespace LiftSAParity
namespace Supplement
open Classical
/-- The probability that the **uniform extension** of the blockwise partial assignment `τ` to a
total assignment lies in `A`: `|{x ∈ A : x ⊇ τ}| / |{x : x ⊇ τ}|`. -/
noncomputable def extFrac {n ℓ : ℕ} {I : Finset (Fin n)} (τ : BlockAssign n ℓ I)
(A : Set (Fin n × Fin ℓ → ZMod 2)) : ℝ :=
((Finset.univ.filter (fun x => x ∈ A ∧ Agrees x τ)).card : ℝ) /
((Finset.univ.filter (fun x : Fin n × Fin ℓ → ZMod 2 => Agrees x τ)).card : ℝ)
/-- `Pr_{x ∼ D̃_I}[x ∈ A]` (de Rezende–Engström–Shekhovtsov, *Lifting Sherali-Adams Degree to
Unary Sherali-Adams over Parities Size*, manuscript (sha256 cab5a032…), §5.2, p.18): "We define
D̃_I to be the distribution over total assignments achieved by sampling a partial assignment from
D_I and extending it, setting the remaining variables uniformly at random". So
`Pr_{x∼D̃_I}[x ∈ A] = ∑_τ D_I(τ) · |{x ∈ A : x ⊇ τ}| / 2^{(n−|I|)ℓ}`. -/
noncomputable def extProb {n ℓ : ℕ} (D : (I : Finset (Fin n)) → BlockAssign n ℓ I → ℝ)
(I : Finset (Fin n)) (A : Set (Fin n × Fin ℓ → ZMod 2)) : ℝ :=
∑ τ : BlockAssign n ℓ I, D I τ * extFrac τ A
/-- `D_I[σ]` **is well-defined** (§5.2, pp.17–18): for `supp(σ) ⊆ I`, "The distribution
D_I[σ] is well-defined only if |I| ≤ d and if there is at least one x ∈ supp(D_I) that agrees
with σ." -/
def CondWellDefined {n ℓ : ℕ} (d : ℕ) (D : (I : Finset (Fin n)) → BlockAssign n ℓ I → ℝ)
(I : Finset (Fin n)) {S : Finset (Fin n)} (σ : BlockAssign n ℓ S) : Prop :=
S ⊆ I ∧ I.card ≤ d ∧ ∃ τ : BlockAssign n ℓ I, Compat τ σ ∧ 0 < D I τ
/-- `Pr_{x ∼ D̃_I[σ]}[x ∈ A]` (§5.2, pp.17–18): `D_I[σ]` is "the distribution of a random variable
x ∼ D_I conditioned on x agreeing with σ", and `D̃_I[σ]` extends it uniformly to a total
assignment. Equals
`∑_{τ ⊇ σ} D_I(τ) · Pr[uniform extension of τ ∈ A] / ∑_{τ ⊇ σ} D_I(τ)`.
**Formalization Note** Meaningful when `CondWellDefined d D I σ` holds (then the denominator is
positive); every use is guarded by that predicate. -/
noncomputable def condExtProb {n ℓ : ℕ} (D : (I : Finset (Fin n)) → BlockAssign n ℓ I → ℝ)
(I : Finset (Fin n)) {S : Finset (Fin n)} (σ : BlockAssign n ℓ S)
(A : Set (Fin n × Fin ℓ → ZMod 2)) : ℝ :=
(∑ τ ∈ Finset.univ.filter (fun τ : BlockAssign n ℓ I => Compat τ σ), D I τ * extFrac τ A) /
(∑ τ ∈ Finset.univ.filter (fun τ : BlockAssign n ℓ I => Compat τ σ), D I τ)
end Supplement
end LiftSAParity