Parent-independent inclusion, its minimum, and Hamming error probabilities
DefinitionAgreementTop736_Exact_Supplement_HammingLet be a finite set, a finite alphabet, and the published sampling scheme: is a probability law on -element top sets , and samples -element subsets of . The published functions and have Hamming error .
Parent-independent inclusion means that for every element of positive top marginal mass and that for every supported . Define
For any real , the approximate disagreement probability is
Theorem 9 uses this event for every . The family need not be constant across elements.
These definitions add the quantities needed for the average Hamming theorem while reusing the published sampling, Hamming count and majority definitions.
Formalization Note The finite minimum is computed from the image of the positive element support. Its empty-support default is zero, but valid sampling with makes that support nonempty. The top size is then positive, so normalized error never divides by zero in the theorem.
import Mathlib
import Definitions.Def_AgreementTop736_Exact_Regularized
/-! Kaufman–Pham, STOC 2027 submission #736, §2 p.7 and Theorem 9 p.12.
Only the additional objects for heterogeneous inclusion and Hamming error are defined here.
The sampling scheme, majority and conditioned Poincaré gap are the published objects. -/
namespace AgreementTop736.Exact.Supplement
open Finset
noncomputable section
variable {V : Type*} [Fintype V] [DecidableEq V]
variable {α : Type*} [Fintype α] [DecidableEq α]
/-- Theorem 9: positive inclusion on the element support, independent of its parent.
No equality between different elements' inclusion probabilities is required. -/
def ParentIndependentInclusion (S : Scheme V) (a : V → ℝ) : Prop :=
(∀ x, 0 < S.pointMass x → 0 < a x) ∧
(∀ K, 0 < S.μ K → ∀ x ∈ K, S.incl K x = a x)
/-- The actual minimum ξ of the a_x on positive-marginal elements.
The empty-support value is 0; Scheme.IsValid rules that case out. -/
def inclusionMinimum (S : Scheme V) (a : V → ℝ) : ℝ :=
let values := (univ.filter (fun x => 0 < S.pointMass x)).image a
if h : values.Nonempty then values.min' h else 0
/-- Absolute expected Hamming error on a top face, using the published error count. -/
def averageError (S : Scheme V) (F : Finset V → V → α) (g : V → α) : ℝ :=
∑ K, S.μ K * (errCount F g K : ℝ)
/-- Expected relative Hamming error. N is positive whenever Scheme.IsValid holds. -/
def normalizedAverageError (S : Scheme V) (F : Finset V → V → α) (g : V → α) : ℝ :=
∑ K, S.μ K * ((errCount F g K : ℝ) / (S.N : ℝ))
/-- The event of §2: d(F_K,g|_K) ≥ δ q_k, including equality at the threshold. -/
def approximateDisagreementProb (S : Scheme V) (F : Finset V → V → α)
(g : V → α) (δ : ℝ) : ℝ :=
∑ K, S.μ K * (if δ * (S.N : ℝ) ≤ (errCount F g K : ℝ) then 1 else 0)
end
end AgreementTop736.Exact.Supplement