CommunicationComplexity.Functions.Disjointness.communicationComplexity_eq
theoremverifiedformalizationimported Lean
Deterministic complexity of set disjointness. Let $n \geq 1$, and let $\mathrm{disjointness}(n, \cdot, \cdot)$ denote the two-party Boolean function that, given subsets $X, Y \subseteq [n]$ held by Alice and Bob respectively, returns $\mathtt{true}$ exactly when $X \cap Y = \emptyset$. Then the deterministic communication complexity of this function is exactly $n + 1$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open CommunicationComplexity.Rectangle in open scoped symmDiff in theorem CommunicationComplexity.Functions.Disjointness.communicationComplexity_eq (n : ℕ) (hn : 1 ≤ n) : Deterministic.communicationComplexity (disjointness n) = n + 1
- Formalizes
- Deterministic complexity of set disjointness, as formalized in TCSlib (`CommunicationComplexity.Functions.Disjointness.communicationComplexity_eq`)
- 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.communicationComplexity_eq← CommunicationComplexity.Functions.Disjointness.communicationComplexity_eq (TCSlib/CommunicationComplexity/DeterministicCC/FuncDisjointness.lean:236): 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.communicationComplexity_leUpper bound on the communication complexity of disjointness. Fix $n \in \bbn$, and let both players' inputs range over subsets of…
- CommunicationComplexity.Deterministic.communicationComplexityThe deterministic communication complexity of $f : X \to Y \to \alpha$ is defined as…
- 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/-- For `n ≥ 1`, the deterministic communication complexity of disjointness on subsets of `[n]` is exactly `n + 1` [RY20, Thm 1.25]. Deviation: [RY20] states the lower bound `≥ n + 1`; combined with the trivial upper bound this gives the exact value ([Rou16, Cor 4.8] only gives `≥ n`). -/theorem CommunicationComplexity.Functions.Disjointness.communicationComplexity_eq (n : ℕ) (hn : 1 ≤ n) : Deterministic.communicationComplexity (disjointness n) = n + 1 := by apply le_antisymm (communicationComplexity_le n) exact le_communicationComplexity n hn