CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncard
theoremverifiedimported Lean
Rank bounded by monochromatic partition size. Let $X$ be a finite set, $Y$ a finite set, and $f : X \to Y \to \mathrm{Bool}$ a Boolean function. If $\mathcal{P}$ is a monochromatic rectangle partition of $X \times Y$ for $f$, then the rank of $f$ is at most the number of members of $\mathcal{P}$: \[ \mathrm{rank}(f) \le \abs{\mathcal{P}}. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open CommunicationComplexity.Rectangle in theorem CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncard {X Y : Type*} [Finite X] [Fintype Y] (f : X → Y → Bool) (Part : Set (Set (X × Y))) (hPart : Rectangle.IsMonoPartition Part f) : boolFunctionRank f ≤ Set.ncard Part
- Source
- TCSlib, `CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncard`
- 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.Deterministic.Rank.boolFunctionRank_le_ncard← CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncard (TCSlib/CommunicationComplexity/DeterministicCC/Rank.lean:143): adapted
What was changed in
CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncard--- TCSlib/CommunicationComplexity/DeterministicCC/Rank.lean:143 (CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncard) +++ as compiled here @@ -1,17 +1,5 @@ -open Rectangle in -/-- The rank of a Boolean function `f` is at most the number of rectangles in any -monochromatic rectangle partition of its input space [RY20, Lemma 2.10]. Deviation: [RY20] -states the bound `≤ 2 ^ c` for a partition into `2 ^ c` parts; here the bound is the number -of parts itself, for an arbitrary finite partition. - -**Proof sketch.** Step 1: let `trueRects` be the parts of the partition that contain some -input on which `f` is `true`; by monochromaticity `f` is `true` throughout each of them. -Step 2: the communication matrix `M_f` equals the sum of the indicator matrices of the parts -in `trueRects`. Entrywise, the input `(x, y)` lies in exactly one part `R₀`, so all other -indicator matrices vanish at `(x, y)`: if `f x y = false` then `R₀` is not in `trueRects` -and every term is `0`; if `f x y = true` then `R₀` is in `trueRects` and contributes `1`. -Step 3: rank is subadditive over the sum (`Matrix.rank_sum_le`), each rectangle indicator -matrix has rank at most `1` (`rank_rectMatrix_le_one`), and `trueRects` is a subset of the -partition, so `rank(M_f) ≤ |trueRects| ≤ |Part|`. -/ -theorem boolFunctionRank_le_ncard +set_option relaxedAutoImplicit false in +set_option autoImplicit false in +open CommunicationComplexity.Rectangle in +theorem CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncard {X Y : Type*} [Finite X] [Fintype Y] - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- CommunicationComplexity.Deterministic.Rank.rectMatrixFor a subset $R \subseteq X \times Y$, the matrix $M_R \in \mathbb{R}^{X \times Y}$ is defined by $(M_R)_{x,y} = 1$ if $(x,y) \in R$ and…
- CommunicationComplexity.Rectangle.monoPartition_part_uniqueUniqueness of the part containing a point. Let $\mathcal{P}$ be a monochromatic rectangle partition for a function…
- CommunicationComplexity.Rectangle.monoPartition_values_eqConstant values within a part. Let $\mathcal{P}$ be a monochromatic rectangle partition for a function $g : X \to Y \to \alpha$, and let…
- CommunicationComplexity.Rectangle.monoPartition_point_memEvery point lies in some part of a partition. Let $g : X \times Y \to \alpha$ and let $\mathcal{P}$ be a monochromatic rectangle partition…
- CommunicationComplexity.Deterministic.Rank.boolFunctionRankThe rank of a Boolean function $f : X \to Y \to \mathrm{Bool}$ is the $\mathbb{R}$-rank of its $0/1$ matrix $M_f$, i.e.\…
- CommunicationComplexity.Rectangle.IsMonoPartitionA collection $\mathcal{P}$ of subsets of $X \times Y$ is a monochromatic rectangle partition for $g : X \to Y \to \alpha$ if every…
- CommunicationComplexity.Deterministic.Rank.rank_rectMatrix_le_oneCombinatorial rectangles have rank-one indicator matrices. Let $X$ be any set and $Y$ a finite set, and let $R \subseteq X \times Y$ be a…
- Matrix.rank_sum_leSubadditivity of matrix rank over finite sums. Let $s$ be a finite subset of an index set, and let $(A_i)_{i \in s}$ be a family of real…
- CommunicationComplexity.Deterministic.Rank.boolFunctionMatrixGiven a Boolean function $f : X \to Y \to \mathrm{Bool}$, the matrix $M_f \in \mathbb{R}^{X \times Y}$ is defined by $(M_f)_{x,y} = 1$ if…
- Used by 1
- CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_pow_of_communicationComplexity_leRank 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…
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 in/-- The rank of a Boolean function `f` is at most the number of rectangles in any monochromatic rectangle partition of its input space [RY20, Lemma 2.10]. Deviation: [RY20] states the bound `≤ 2 ^ c` for a partition into `2 ^ c` parts; here the bound is the number of parts itself, for an arbitrary finite partition. **Proof sketch.** Step 1: let `trueRects` be the parts of the partition that contain some input on which `f` is `true`; by monochromaticity `f` is `true` throughout each of them. Step 2: the communication matrix `M_f` equals the sum of the indicator matrices of the parts in `trueRects`. Entrywise, the input `(x, y)` lies in exactly one part `R₀`, so all other indicator matrices vanish at `(x, y)`: if `f x y = false` then `R₀` is not in `trueRects` and every term is `0`; if `f x y = true` then `R₀` is in `trueRects` and contributes `1`. Step 3: rank is subadditive over the sum (`Matrix.rank_sum_le`), each rectangle indicator matrix has rank at most `1` (`rank_rectMatrix_le_one`), and `trueRects` is a subset of the partition, so `rank(M_f) ≤ |trueRects| ≤ |Part|`. -/theorem CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncard {X Y : Type*} [Finite X] [Fintype Y] (f : X → Y → Bool) (Part : Set (Set (X × Y))) (hPart : Rectangle.IsMonoPartition Part f) : boolFunctionRank f ≤ Set.ncard Part := by classical -- Step 1: the parts containing a `true` input let PF := (Set.toFinite Part).toFinset let trueRects := PF.filter (fun R => ∃ p ∈ R, f p.1 p.2 = true) -- Step 2: M_f = ∑ over true-mono rectangles of rectMatrix R have hsum : boolFunctionMatrix f = ∑ R ∈ trueRects, rectMatrix R := by ext x y simp only [boolFunctionMatrix, rectMatrix, Matrix.of_apply, Matrix.sum_apply] obtain ⟨R₀, hR₀_mem, hR₀_in⟩ := monoPartition_point_mem hPart (x, y) have hother : ∀ R ∈ PF, R ≠ R₀ → (x, y) ∉ R := fun R hR hne hmem => hne (monoPartition_part_unique hPart ((Set.toFinite Part).mem_toFinset.mp hR) hR₀_mem hmem hR₀_in) cases hf : f x y <;> simp only [Bool.false_eq_true, ite_true, ite_false] · -- f x y = false: every term is 0 symm; apply Finset.sum_eq_zero; intro R hR by_cases hne : R = R₀ · subst hne; obtain ⟨⟨x', y'⟩, hpin, hftrue⟩ := (Finset.mem_filter.mp hR).2 have hmono := monoPartition_values_eq hPart hR₀_mem hR₀_in hpin rw [hf] at hmono; simp [← hmono] at hftrue · simp [hother R (Finset.mem_filter.mp hR).1 hne] · -- f x y = true: only R₀ contributes 1 symm; rw [Finset.sum_eq_single R₀ (fun R hR hne => by simp [hother R (Finset.mem_filter.mp hR).1 hne]) (fun h => absurd (Finset.mem_filter.mpr ⟨(Set.toFinite Part).mem_toFinset.mpr hR₀_mem, ⟨x, y⟩, hR₀_in, hf⟩) h)] simp [hR₀_in] -- Step 3: rank(M_f) ≤ ∑ rank(rectMatrix R) ≤ ∑ 1 = |trueRects| ≤ |Part| calc boolFunctionRank f = (∑ R ∈ trueRects, rectMatrix R).rank := by unfold boolFunctionRank; rw [← hsum] _ ≤ ∑ R ∈ trueRects, (rectMatrix R).rank := Matrix.rank_sum_le _ _ _ ≤ ∑ _R ∈ trueRects, 1 := Finset.sum_le_sum fun R hR => rank_rectMatrix_le_one R (hPart.1 R ((Set.toFinite Part).mem_toFinset.mp (Finset.mem_filter.mp hR).1)) _ = trueRects.card := by simp _ ≤ PF.card := Finset.card_filter_le _ _ _ = Set.ncard Part := (Set.ncard_eq_toFinset_card Part (Set.toFinite Part)).symm