CommunicationComplexity.Functions.Disjointness.foolingSet_isFoolingSet
theoremverifiedimported Lean
The disjointness fooling set. Fix $n \in \bbn$, and consider the set-disjointness function on subsets of $[n]$, namely the Boolean function $g(X, Y)$ that is $\mathtt{true}$ exactly when $X \cap Y = \emptyset$. Then the collection $\{(X, X^c) \mid X \subseteq [n]\}$ of complementary pairs is a fooling set for $g$: for every rectangle $R = A \times B$ (with $A, B$ families of subsets of $[n]$) that is monochromatic for $g$, the intersection of $R$ with this collection contains at most one point.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open CommunicationComplexity.Rectangle in open scoped symmDiff in theorem CommunicationComplexity.Functions.Disjointness.foolingSet_isFoolingSet (n : ℕ) : IsFoolingSet (foolingSet n) (disjointness n)
- Source
- TCSlib, `CommunicationComplexity.Functions.Disjointness.foolingSet_isFoolingSet`
- Lean proof
- By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.CommunicationComplexity.Functions.Disjointness.foolingSet_isFoolingSet← CommunicationComplexity.Functions.Disjointness.foolingSet_isFoolingSet (TCSlib/CommunicationComplexity/DeterministicCC/FuncDisjointness.lean:85): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- CommunicationComplexity.Functions.Disjointness.disjointnessFor $n \in \mathbb{N}$ and subsets $X, Y \subseteq [n]$, $\mathrm{disjointness}(n, X, Y)$ is the Boolean function that returns…
- CommunicationComplexity.Functions.Disjointness.foolingSetThe candidate fooling set for disjointness is the collection of all pairs $(X, X^c)$ where $X \subseteq [n]$, i.e.\…
- CommunicationComplexity.Rectangle.IsFoolingSetA set $S \subseteq X \times Y$ is a fooling set for $g : X \to Y \to \alpha$ if every monochromatic rectangle with respect to $g$…
- CommunicationComplexity.Rectangle.IsRectangle_iffCross characterization of combinatorial rectangles. A subset $R \subseteq X \times Y$ is a rectangle — that is, $R = A \times B$ for some…
- Used by 1
- CommunicationComplexity.Functions.Disjointness.le_communicationComplexityLower bound on the communication complexity of disjointness. Fix an integer $n \ge 1$, and consider the set-disjointness function on…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen CommunicationComplexity.Rectangle inopen scoped symmDiff in/-- The pairs `(X, Xᶜ)` form a fooling set for disjointness: no monochromatic rectangle contains two distinct pairs `(X, Xᶜ)` and `(X', X'ᶜ)` [RY20, Ch. 1, §Using Fooling Sets]. **Proof sketch.** Let `R` be a monochromatic rectangle containing `(X, Xᶜ)` and `(X', X'ᶜ)`; we show `X = X'`. Step 1: if `X = X'` the two pairs coincide. Step 2: otherwise the cross-membership property of rectangles puts both mixed pairs `(X, X'ᶜ)` and `(X', Xᶜ)` into `R`, and since `X ≠ X'` the symmetric difference `X ∆ X'` contains some element `i`. Step 3: if `i ∈ X \ X'`, then `i ∈ X ∩ X'ᶜ`, so the mixed pair `(X, X'ᶜ)` is intersecting while the diagonal pair `(X, Xᶜ)` is disjoint; monochromaticity of `R` gives `Disj(X, Xᶜ) = Disj(X, X'ᶜ)`, a contradiction. Step 4: if `i ∈ X' \ X` the same argument applies with the roles of `X` and `X'` exchanged. -/theorem CommunicationComplexity.Functions.Disjointness.foolingSet_isFoolingSet (n : ℕ) : IsFoolingSet (foolingSet n) (disjointness n) := by intro R hR hmono p hp q hq rcases p with ⟨X, Y⟩ rcases q with ⟨X', Y'⟩ simp only [foolingSet, Set.mem_inter_iff, Set.mem_setOf_eq] at hp hq rcases hp with ⟨rfl, hpR⟩ rcases hq with ⟨rfl, hqR⟩ by_cases hXX' : X = X' · -- Step 1: equal sets give the same pair. subst hXX' rfl · -- Step 2: the mixed pairs lie in `R`, and some `i` separates `X` from `X'`. have hcross := (IsRectangle_iff R).mp hR X X' Xᶜ X'ᶜ hpR hqR obtain ⟨i, hi⟩ : (X ∆ X').Nonempty := Set.symmDiff_nonempty.mpr hXX' rw [Set.mem_symmDiff] at hi rcases hi with hi | hi · -- Step 3: `i ∈ X \ X'`, so `(X, X'ᶜ)` intersects while `(X, Xᶜ)` is disjoint. have hval := hmono X X Xᶜ X'ᶜ hpR hcross.2 have htrue : disjointness n X Xᶜ = true := by simpa [disjointness] using (disjoint_compl_right : Disjoint X Xᶜ) have hne : disjointness n X X'ᶜ ≠ true := by unfold disjointness simp only [ne_eq, decide_eq_true_eq] intro hdisj rw [Set.disjoint_left] at hdisj exact hdisj hi.1 hi.2 rw [htrue] at hval exact (hne hval.symm).elim · -- Step 4: `i ∈ X' \ X`, the mirror image with `X` and `X'` exchanged. have hval := hmono X' X' X'ᶜ Xᶜ hqR hcross.1 have htrue : disjointness n X' X'ᶜ = true := by simpa [disjointness] using (disjoint_compl_right : Disjoint X' X'ᶜ) have hne : disjointness n X' Xᶜ ≠ true := by unfold disjointness simp only [ne_eq, decide_eq_true_eq] intro hdisj rw [Set.disjoint_left] at hdisj exact hdisj hi.1 hi.2 rw [htrue] at hval exact (hne hval.symm).elim