AFTD Auto-Formalizing Theoretical Domains

min_leaf_count

def

Given types $X$, $Y$, and $\alpha$ and a function $f : X \to Y \to \alpha$, the minimum protocol leaf count $\mathrm{min\_leaf\_count}(f)$ is the extended natural number in $\mathrm{ENat}$ defined as the infimum of $\mathrm{protocol\_leaf\_count}(p)$ over all deterministic communication protocols $p : \mathrm{CommunicationComplexity.Deterministic.Protocol}\;X\;Y\;\alpha$ satisfying $p.\mathrm{Computes}\;f$.

Statement

noncomputable def min_leaf_count {X Y α : Type*} (f : X → Y → α) : ENat
Defined in
arXiv:2611.11488, Section 1.1 and Section 5.1
Verified
10 Nov 2026
Axioms
none listed
Built on 3

Read back from the Lean

For types X, Y, and α, and a function f : X → Y → α, min_leaf_count f is defined as the infimum in ENat (the extended natural numbers $\mathbb{N} \cup \{\infty\}$) of (protocol_leaf_count p : ENat) taken over all deterministic communication protocols p : CommunicationComplexity.Deterministic.Protocol X Y α satisfying p.Computes f.

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 minimum number of leaves in any correct deterministic protocol computing f. -/
noncomputable def min_leaf_count {X Y α : Type*} (f : X → Y → α) : ENat := ⨅ (p : CommunicationComplexity.Deterministic.Protocol X Y α) (_ : p.Computes f), (protocol_leaf_count p : ENat)
See it in the graphDiscuss this resultChallenge it