AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

Lean source view module on GitHub

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)
See it in the graphDiscuss this resultChallenge it