Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.1 — Pair avoidance under fixed-size sampling

Proved
BirthdayEntropy.Soundness.pair_avoidance

by mikedeng1 · Nov 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theoryinformation-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Let UUU be a finite ground set of size mmm and PPP a nonempty set of distinct unordered two-element subsets of UUU. Suppose every point is incident to at most qqq pairs. For 2≤ℓ≤m2\le\ell\le m2≤ℓ≤m, a uniform ℓ\ellℓ-subset SSS satisfies

Pr⁡[∀e∈P, e⊈S]≤exp⁡ ⁣(−∣P∣ℓ24qm2).\Pr[\forall e\in P,\ e\nsubseteq S]\le\exp\!\left(-\frac{|P|\ell^2}{4qm^2}\right).Pr[∀e∈P, e⊈S]≤exp(−4qm2∣P∣ℓ2​).

Nonemptiness and the two-element condition imply q≥1q\ge1q≥1, 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
  • Endorsed by Shuze Chen · Nov 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me