CommunicationComplexity.Functions.Equality.communicationComplexity_eq
theoremverifiedformalizationimported Lean
Exact deterministic complexity of equality. For a natural number $n$, let $\mathrm{equality}_n$ denote the two-party Boolean function on $n$-bit strings that returns $\mathtt{true}$ precisely when Alice's input $x \in \mathrm{BoolInput}(n)$ equals Bob's input $y \in \mathrm{BoolInput}(n)$. Its deterministic communication complexity, measured in $\bbn_\infty$ as the least worst-case number of bits exchanged by any deterministic protocol computing it, is \[ D(\mathrm{equality}_n) \;=\; \begin{cases} 0 & \text{if } n = 0,\\ n + 1 & \text{otherwise.} \end{cases} \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in theorem CommunicationComplexity.Functions.Equality.communicationComplexity_eq (n : ℕ) : Deterministic.communicationComplexity (equality n) = if n = 0 then 0 else n + 1
- Formalizes
- Exact deterministic complexity of equality, as formalized in TCSlib (`CommunicationComplexity.Functions.Equality.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.Equality.communicationComplexity_eq← CommunicationComplexity.Functions.Equality.communicationComplexity_eq (TCSlib/CommunicationComplexity/DeterministicCC/FuncEquality.lean:167): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- CommunicationComplexity.Functions.Equality.le_communicationComplexityDeterministic complexity lower bound for equality. For every natural number $n \ge 1$, the deterministic communication complexity of the…
- CommunicationComplexity.Deterministic.communicationComplexityThe deterministic communication complexity of $f : X \to Y \to \alpha$ is defined as…
- CommunicationComplexity.Functions.Equality.communicationComplexity_leDeterministic complexity upper bound for equality. For every natural number $n$, the deterministic communication complexity of the $n$-bit…
- CommunicationComplexity.Functions.Equality.equalityFor a natural number $n$,
CommunicationComplexity.Functions.Equality.equalityis the Boolean function… - CommunicationComplexity.Functions.Equality.communicationComplexity_zeroDeterministic complexity of equality at $n = 0$. Let…
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 MeasureTheory in/-- The exact deterministic communication complexity of equality on `n`-bit strings is `0` when `n = 0` and `n + 1` otherwise; the lower bound is [RY20, Thm 1.14] and the upper bound is the trivial protocol. Deviation: [RY20] only states the lower bound `≥ n + 1`; here the exact value is given, including the degenerate case `n = 0`. -/theorem CommunicationComplexity.Functions.Equality.communicationComplexity_eq (n : ℕ) : Deterministic.communicationComplexity (equality n) = if n = 0 then 0 else n + 1 := by split · next h => subst h; exact communicationComplexity_zero · next h => apply le_antisymm (communicationComplexity_le n) exact le_communicationComplexity n (by omega)