AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.Protocol.leafRectangles_isMonoPartition

theoremverifiedimported Lean

Leaf rectangles of a protocol form a monochromatic partition. Let $p$ be a deterministic two-party communication protocol over input types $X$ and $Y$ producing outputs in $\alpha$, and let $g : X \to Y \to \alpha$. If $p$ computes $g$, then the collection of leaf rectangles of $p$ is a monochromatic rectangle partition of $X \times Y$ for $g$: every leaf rectangle is a rectangle and is monochromatic for $g$, the leaf rectangles cover all of $X \times Y$, and any two distinct leaf rectangles are disjoint.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
theorem CommunicationComplexity.Deterministic.Protocol.leafRectangles_isMonoPartition
    (p : Protocol X Y α) (g : X → Y → α)
    (h_comp : Computes p g) :
    Rectangle.IsMonoPartition (leafRectangles p) g
Source
TCSlib, `CommunicationComplexity.Deterministic.Protocol.leafRectangles_isMonoPartition`
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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
Used by 3

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
/-- If `p` computes `g`, then the leaf rectangles of `p` form a monochromatic rectangle partition of `X × Y` for `g`: every member is a rectangle, `g` is constant on every member, the members cover `X × Y`, and distinct members are disjoint [RY20, Lemma 1.6] (also [Rou16, Lemma 4.1, Lemma 4.2]). -/
theorem CommunicationComplexity.Deterministic.Protocol.leafRectangles_isMonoPartition
    (p : Protocol X Y α) (g : X → Y → α)
    (h_comp : Computes p g) :
    Rectangle.IsMonoPartition (leafRectangles p) g :=
  ⟨fun R hR => leafRectangles_isRectangle p R hR,
   fun R hR => leafRectangles_mono p g h_comp R hR,
   leafRectangles_cover p,
   fun R S hR hS hne =>
     leafRectangles_disjoint p R S hR hS hne⟩
See it in the graphDiscuss this resultChallenge it