Lemma A.2 — Incidence and conditional-entropy budget
OpenBirthdayEntropy.Soundness.Supplement.lemma_A_2Let , , , and let be a set of exactly distinct Boolean labelled views. Sample selected vertices independently and uniformly with replacement. Write , , and let choose any majority bit on every heavy coordinate with , where is its incidence in the original . Let be the original-family fraction disagreeing with on at least one heavy coordinate, the strict low-incidence complement, and .
Assume regime (20): and . Let be the actual surviving subfamily agreeing with on heavy coordinates. Then is nonempty, . Sample uniformly from , let be its view marginal and uniform on all views, and put . All three conclusions hold:
This exact identity retains the conditional answer entropy and accounts for missing views and distinctness of the surviving labelled pairs.
Differences from the source:
- encoding: a set of K distinct Boolean labelled views → a Finset of published Vertex (Fin n coordinates) with card = choose n ell; reason: finite sets enforce distinctness and represent every source selection; normalization is unchanged
- encoding: a partial majority assignment on heavy coordinates → a total Boolean assignment constrained only on heavy coordinates; reason: every partial assignment extends; all extensions give the same survivor family and heavy error
- encoding: uniform survivor law after (20) establishes m>0 → existence of a nonempty-survivor certificate followed by the bounds; signed labels encode A given S; reason: no positivity assumption is added; within a view the signed representation is injective
import Mathlib import Definitions.Def_BirthdayEntropy_Soundness_Supplement_Agreement
namespace BirthdayEntropy.Soundness.Supplement
/-- Lemma A.2, (21)–(23), PDF p19 / printed p18. Nonemptiness of G is
concluded, not assumed. The signed representation preserves A conditional on S. -/
theorem lemma_A_2 (n ℓ : ℕ) (hn : 1 ≤ n) (hℓ : 1 ≤ ℓ) (hℓn : ℓ ≤ n)
(H : Finset (Vertex n ℓ)) (hH : H.card = Nat.choose n ℓ)
(g : Fin n → Bool) (hg : IsMajority H g) (hsmall : SmallError H g) :
∃ hG : (survivors H g).Nonempty,
let ε := heavyError H g
let lam := lowFraction H
let μ := survivorViews H g hG
let x := lowIncidence μ (low H)
let ha := answerEntropy H g hG
let kl := μ.relativeEntropy (allViewLaw n ℓ hℓn)
((survivors H g).card : ℝ) = (1 - ε) * Nat.choose n ℓ ∧
(0 ≤ x ∧ x ≤ lam / (8 * (1 - ε)) ∧ lam / (8 * (1 - ε)) ≤ lam / 4) ∧
ha ≤ (ℓ : ℝ) * x * Real.log 2 ∧
kl = Real.log ((Nat.choose n ℓ : ℝ) / (survivors H g).card) + ha ∧
kl ≤ -Real.log (1 - ε) + (ℓ : ℝ) * x * Real.log 2 := by sorry
end BirthdayEntropy.Soundness.Supplement