Lemma 4.1 — Pair avoidance under fixed-size sampling
ProvedBirthdayEntropy.Soundness.pair_avoidancegraph-theoryinformation-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be a finite ground set of size and a nonempty set of distinct unordered two-element subsets of . Suppose every point is incident to at most pairs. For , a uniform -subset satisfies
Nonemptiness and the two-element condition imply , even though the bound parameter is real. The avoidance probability is the exact ratio of finite counts. This is the pair-avoidance ingredient for the fixed-flattening estimate.
Differences from the source:
- encoding: uniform fixed-size sampling and unordered pairs → finite-set count ratio and a set of two-element finite subsets; reason: the sample space has nonzero binomial cardinality under 2<=ell<=m; no pairs are counted with multiplicity
Preamble
import Mathlib import Definitions.Def_BirthdayEntropy_Soundness_Counting noncomputable section open scoped Classical
Formal statement
namespace BirthdayEntropy.Soundness
/-- Lemma 4.1, PDF p6 / printed p5. Distinct unordered pairs; q is real. -/
theorem pair_avoidance {U : Type*} [Fintype U] (P : Finset (Finset U))
(hP : P.Nonempty) (hpairs : ∀ e ∈ P, e.card = 2)
(q : ℝ) (hq : ∀ u : U, ((P.filter (fun e => u ∈ e)).card : ℝ) ≤ q)
(ℓ : ℕ) (hℓ : 2 ≤ ℓ) (hℓm : ℓ ≤ Fintype.card U) :
avoidanceProbability P ℓ ≤ Real.exp
(-((P.card : ℝ) * (ℓ : ℝ)^2 / (4 * q * (Fintype.card U : ℝ)^2))) := by sorry
end BirthdayEntropy.Soundness
Source
Alexandru Popa, Entropy-Weighted Soundness for Multi-Answer Birthday Graphs, STOC 2027 submission #907 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/907.pdf, Lemma 4.1, PDF pp6 / printed pp5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.