AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_pow_of_communicationComplexity_le

theoremverifiedimported Lean

Rank bound from communication complexity. Let $X$ and $Y$ be finite types and let $f : X \to Y \to \mathrm{Bool}$ be a two-party Boolean function, whose rank $\mathrm{rank}(f)$ is the $\bbr$-rank of the $0/1$ matrix $M_f \in \bbr^{X \times Y}$ with $(M_f)_{x,y} = 1$ exactly when $f\,x\,y = \mathrm{true}$. If the deterministic communication complexity $D(f)$ is at most $n$ for some $n \in \bbn$, then $\mathrm{rank}(f) \le 2^n$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open CommunicationComplexity.Rectangle in
theorem CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_pow_of_communicationComplexity_le
    {X Y : Type*} [Finite X] [Fintype Y]
    (f : X → Y → Bool) (n : ℕ)
    (h : Deterministic.communicationComplexity f ≤ n) :
    boolFunctionRank f ≤ 2 ^ n
Source
TCSlib, `CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_pow_of_communicationComplexity_le`
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.
What was changed in CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_pow_of_communicationComplexity_le
--- TCSlib/CommunicationComplexity/DeterministicCC/Rank.lean:190 (CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_pow_of_communicationComplexity_le)
+++ as compiled here
@@ -1,6 +1,5 @@
-open Rectangle in
-/-- If the deterministic communication complexity of `f` is at most `n`, then the rank of
-`f` is at most `2 ^ n` [RY20, Lemma 2.10]: a protocol of complexity `n` induces a
-monochromatic rectangle partition with at most `2 ^ n` parts [RY20, Thm 1.7]. -/
-theorem boolFunctionRank_le_pow_of_communicationComplexity_le
+set_option relaxedAutoImplicit false in
+set_option autoImplicit false in
+open CommunicationComplexity.Rectangle in
+theorem CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_pow_of_communicationComplexity_le
     {X Y : Type*} [Finite X] [Fintype Y]
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen CommunicationComplexity.Rectangle in/-- If the deterministic communication complexity of `f` is at most `n`, then the rank of `f` is at most `2 ^ n` [RY20, Lemma 2.10]: a protocol of complexity `n` induces a monochromatic rectangle partition with at most `2 ^ n` parts [RY20, Thm 1.7]. -/theorem CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_pow_of_communicationComplexity_le    {X Y : Type*} [Finite X] [Fintype Y]    (f : X → Y → Bool) (n : ℕ)    (h : Deterministic.communicationComplexity f ≤ n) :    boolFunctionRank f ≤ 2 ^ n := by  obtain ⟨Part, hPart, hCard⟩ := Deterministic.mono_partition_of_communicationComplexity_le f n h  exact (boolFunctionRank_le_ncard f Part hPart).trans hCard
See it in the graphDiscuss this resultChallenge it