AFTD Auto-Formalizing Theoretical Domains

rectangle_size_bound

def

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

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