is_monochromatic_cover
Given types $X$ and $Y$, a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, and a Boolean value $b : \mathrm{Bool}$, a collection $C : \mathrm{Set}\;(\mathrm{Set}\;(X \times Y))$ is a $b$-monochromatic rectangle cover of $f^{-1}(b)$ if every $R \in C$ satisfies $\mathrm{CommunicationComplexity.Rectangle.IsRectangle}\;R$, for every $R \in C$ and $(x,y) \in R$ we have $f\;x\;y = b$, and $\{p : X \times Y \mid f\;p.1\;p.2 = b\} \subseteq \bigcup C$.
Statement
def is_monochromatic_cover {X Y : Type*} (C : Set (Set (X × Y))) (f : X → Y → Bool) (b : Bool) : Prop
- Defined in
- arXiv:2611.11488, Section 1.1
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 1
- CommunicationComplexity.Rectangle.IsRectangleA subset $S \subseteq X \times Y$ is a rectangle if it factors as a product $A \times B$ for some $A \subseteq X$ and…
- Used by 1
- cover_numberThe $b$-monochromatic cover number $\mathrm{cover\_number}(f, b)$ of a curried Boolean function $f : X \to Y \to \mathrm{Bool}$ is the…
Read back from the Lean
Given types X and Y, a family of subsets C : Set (Set (X × Y)), a function f : X → Y → Bool, and a boolean b : Bool, is_monochromatic_cover C f b is defined as the conjunction of three conditions:
1. Every element R ∈ C satisfies CommunicationComplexity.Rectangle.IsRectangle R.
2. Every element R ∈ C is monochromatic with value b: for all R ∈ C and all x : X and y : Y, if (x, y) ∈ R, then f x y = b.
3. The sets in C cover all inputs where f evaluates to b: the set {p : X × Y | f p.1 p.2 = b} is a subset of the union ⋃₀ C (that is, every (x, y) with f x y = b belongs to at least one R ∈ C).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Predicate stating that C is a collection of b-monochromatic rectangles covering f⁻¹(b). -/ def is_monochromatic_cover {X Y : Type*} (C : Set (Set (X × Y))) (f : X → Y → Bool) (b : Bool) : Prop := (∀ R ∈ C, CommunicationComplexity.Rectangle.IsRectangle R) ∧ (∀ R ∈ C, ∀ x y, (x, y) ∈ R → f x y = b) ∧ {p : X × Y | f p.1 p.2 = b} ⊆ ⋃₀ C