rectangle_size_bound
For finite types $X$ and $Y$ and a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, the prior-free rectangle-size bound $\mathrm{rectangle\_size\_bound}(f) \in \mathbb{R}$ is the supremum over all probability mass functions $\mu : X \times Y \to \mathbb{R}$ (satisfying $\forall p, 0 \le \mu(p)$ and $\sum_{p : X \times Y} \mu(p) = 1$) of $-\log_2$ of the supremum of $\sum_{p \in R} \mu(p)$ over all subsets $R \subseteq X \times Y$ satisfying $\mathrm{CommunicationComplexity.Rectangle.IsRectangle}\;R$ and $\mathrm{CommunicationComplexity.Rectangle.IsMonochromatic}\;R\;f$.
Statement
noncomputable def rectangle_size_bound {X Y : Type*} [Fintype X] [Fintype Y] (f : X → Y → Bool) : ℝ
- Defined in
- arXiv:2611.11488, Section 1.2, Equation (1.2)
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 2
- CommunicationComplexity.Rectangle.IsMonochromaticA set $S \subseteq X \times Y$ is monochromatic for a function $g : X \to Y \to \alpha$ if $g$ is constant on $S$, i.e.,…
- 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…
Read back from the Lean
For types X and Y with finite type instances [Fintype X] and [Fintype Y], and a function f : X → Y → Bool, rectangle_size_bound f is the real number defined as:
The supremum over all functions μ : X × Y → ℝ satisfying:
1. ∀ p : X × Y, 0 ≤ μ p, and
2. ∑ p : X × Y, μ p = 1 (i.e., μ is a probability distribution on X × Y)
of the quantity:
-Real.logb 2 of the supremum over all subsets R : Set (X × Y) satisfying:
1. CommunicationComplexity.Rectangle.IsRectangle R, and
2. CommunicationComplexity.Rectangle.IsMonochromatic R f
of:
∑ p ∈ Finset.univ.filter (fun q => q ∈ R), μ p (the measure of R under μ).
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
/-- The prior-free rectangle-size bound RS₀(f) for finite input spaces. -/ noncomputable def rectangle_size_bound {X Y : Type*} [Fintype X] [Fintype Y] (f : X → Y → Bool) : ℝ := open Classical in ⨆ (μ : X × Y → ℝ) (_ : (∀ p, 0 ≤ μ p) ∧ ∑ p : X × Y, μ p = 1), -Real.logb 2 (⨆ (R : Set (X × Y)) (_ : CommunicationComplexity.Rectangle.IsRectangle R ∧ CommunicationComplexity.Rectangle.IsMonochromatic R f), ∑ p ∈ Finset.univ.filter (fun q => q ∈ R), μ p)