Isotropic noise, spanning forests and the planted likelihood ratio on a finite multigraph
DefinitionInducedExpanderTest989_Structural_Supplement_NoisyLabelsLet , let be the group of -bit vectors under coordinatewise addition and . Isotropic noise of rate is the law on with
A finite multigraph has a finite vertex set , a finite set of edge occurrences and an endpoint map; loops and parallel edges are allowed. A set is a spanning forest if it contains no cycle (a loop, or two parallel edges, is a cycle) and has the same connected components as . The forest distance is the least number of edges of on a walk from to , and when lie in different trees.
For labels , the planted law draws independent uniform potentials and independent isotropic noises , and sets for :
The uniform law gives each probability , and the likelihood ratio is
These objects state Lemma 6.8, the analytic core of the indistinguishability argument behind Theorem 6.1.
Formalization Note is Fin r → ZMod 2. A multigraph is a pair of finite types with ends : E → V × V; orientation is irrelevant since in , and a loop contributes . Acyclicity of is stated as: no edge of has its endpoints joined by the other edges of . nonforestEndpoint lists the endpoint occurrences of the nonforest edges.
import Mathlib
set_option autoImplicit false
open scoped BigOperators ENNReal NNReal
noncomputable section
namespace InducedExpanderTest989.Structural.Supplement
/-- The label group `K = F₂^r` (§6.1); its order is `q = 2^r`. -/
abbrev LabelGroup (r : ℕ) := Fin r → ZMod 2
/-- Isotropic noise (23): mass `1 − p` at `0` and `p/(q − 1)` at each nonzero element. -/
def isoNoise (r : ℕ) (p : ℝ) (z : LabelGroup r) : ℝ :=
if z = 0 then 1 - p else p / ((2 : ℝ) ^ r - 1)
/-- The character bias `ρ = 1 − q p/(q − 1)` of (23). -/
def noiseBias (r : ℕ) (p : ℝ) : ℝ := 1 - (2 : ℝ) ^ r * p / ((2 : ℝ) ^ r - 1)
section Multigraph
variable {V E : Type}
/-- A finite multigraph is a finite vertex type `V`, a finite type `E` of edge occurrences and
an endpoint map `ends : E → V × V`; loops and parallel edges are allowed. `x` and `y` are
joined by an edge of the set `F`. -/
def edgeAdj (ends : E → V × V) (F : Finset E) (x y : V) : Prop :=
∃ e ∈ F, ends e = (x, y) ∨ ends e = (y, x)
/-- `F` is acyclic: no edge of `F` has its endpoints joined by the other edges of `F`. A loop,
or two parallel edges, in `F` is a cycle. -/
def IsAcyclicEdgeSet [DecidableEq E] (ends : E → V × V) (F : Finset E) : Prop :=
∀ e ∈ F, ¬ Relation.ReflTransGen (edgeAdj ends (F.erase e)) (ends e).1 (ends e).2
/-- `F ⊆ E` is a spanning forest: acyclic, with the same connected components as the whole
multigraph. -/
def IsSpanningForest [DecidableEq E] [Fintype E] (ends : E → V × V) (F : Finset E) : Prop :=
IsAcyclicEdgeSet ends F ∧
∀ x y : V, Relation.ReflTransGen (edgeAdj ends Finset.univ) x y →
Relation.ReflTransGen (edgeAdj ends F) x y
/-- There is a walk of exactly `k` edges of `F` from `x` to `y`. -/
def WalkIn (ends : E → V × V) (F : Finset E) : ℕ → V → V → Prop
| 0, x, y => x = y
| k + 1, x, y => ∃ z, WalkIn ends F k x z ∧ edgeAdj ends F z y
/-- `dist_F(x, y)`: the least number of edges of `F` on a walk from `x` to `y`, `⊤` (= ∞) for
vertices in different trees. -/
def forestDist (ends : E → V × V) (F : Finset E) (x y : V) : ℕ∞ :=
⨅ (k : ℕ) (_ : WalkIn ends F k x y), (k : ℕ∞)
/-- The `2R` endpoint occurrences of the nonforest edges: `(e, 0)` is the first endpoint of
`e ∉ F`, `(e, 1)` the second. -/
def nonforestEndpoint (ends : E → V × V) (F : Finset E) (a : {e // e ∉ F} × Fin 2) : V :=
if a.2 = 0 then (ends a.1.1).1 else (ends a.1.1).2
/-- `Pr^H_P(y)` of §6.1: potentials `X_v` i.i.d. uniform on `K`, noises `Z_e` i.i.d. isotropic,
and `y_e = X_u + X_v + Z_e` for every edge occurrence `e = uv`. -/
def plantedProb [Fintype V] [Fintype E] (r : ℕ) (p : ℝ) (ends : E → V × V)
(y : E → LabelGroup r) : ℝ := by
classical
exact ∑ X : V → LabelGroup r, (((2 : ℝ) ^ r) ^ Fintype.card V)⁻¹ *
∏ e, isoNoise r p (y e + X (ends e).1 + X (ends e).2)
/-- The likelihood ratio (34): `D_H(y) = Pr^H_P(y) / Pr^H_U(y) = q^{|E(H)|} Pr^H_P(y)`. -/
def likelihoodRatio [Fintype V] [Fintype E] (r : ℕ) (p : ℝ) (ends : E → V × V)
(y : E → LabelGroup r) : ℝ :=
((2 : ℝ) ^ r) ^ Fintype.card E * plantedProb r p ends y
end Multigraph
end InducedExpanderTest989.Structural.Supplement