AFTD Auto-Formalizing Theoretical Domains

mutual_f_information_subadditive

def

A function f is a subadditive generator for mutual f-information if for all finite random variables X, Y, Z forming a Markov chain Y -> X -> Z (p_{XYZ} = p_X p_{Y|X} p_{Z|X}), the mutual f-information satisfies Ĩ_f(X; YZ) ≤ Ĩ_f(X; Y) + Ĩ_f(X; Z).

Statement

def mutual_f_information_subadditive (f : ℝ → ℝ) : Prop
Defined in
arXiv:2610.21231, Definition 1
Verified
22 Oct 2026
Axioms
none listed
Built on 1
  • mutual_f_informationFor a joint probability mass function p_{XY} on finite sets, the mutual f-information is Ĩ_f(X; Y) = D_f(p_{XY} ‖ p_X p_Y) = Σ_{x,y}…
Used by 4

Read back from the Lean

The definition mutual_f_information_subadditive defines a predicate on a function f : ℝ → ℝ. It asserts that for all finite types X, Y, and Z, and for all functions pX : X → ℝ, PY : X → Y → ℝ, and PZ : X → Z → ℝ, if: 1. pX is non-negative everywhere (∀ x, 0 ≤ pX x), 2. pX sums to 1 (∑ x, pX x = 1), 3. PY is non-negative everywhere (∀ x y, 0 ≤ PY x y), 4. For every x, PY x sums to 1 (∀ x, ∑ y, PY x y = 1), 5. PZ is non-negative everywhere (∀ x z, 0 ≤ PZ x z), and 6. For every x, PZ x sums to 1 (∀ x, ∑ z, PZ x z = 1), then the mutual f-information between X and Y × Z under the conditionally independent joint distribution p(x, (y, z)) = pX x * PY x y * PZ x z is less than or equal to the sum of the mutual f-information between X and Y (under p(x, y) = pX x * PY x y) and the mutual f-information between X and Z (under p(x, z) = pX x * PZ x z): mutual_f_information f (fun x (yz : Y × Z) => pX x * PY x yz.1 * PZ x yz.2) ≤ mutual_f_information f (fun x y => pX x * PY x y) + mutual_f_information f (fun x z => pX x * PZ x z).

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

/-- Subadditivity of mutual f-information under conditionally independent observations Y -> X -> Z. -/
def mutual_f_information_subadditive (f : ℝ → ℝ) : Prop := ∀ (X Y Z : Type) [Fintype X] [Fintype Y] [Fintype Z]
    (pX : X → ℝ) (PY : X → Y → ℝ) (PZ : X → Z → ℝ),
    (∀ x, 0 ≤ pX x) → (∑ x, pX x = 1) →
    (∀ x y, 0 ≤ PY x y) → (∀ x, ∑ y, PY x y = 1) →
    (∀ x z, 0 ≤ PZ x z) → (∀ x, ∑ z, PZ x z = 1) →
    mutual_f_information f (fun x (yz : Y × Z) => pX x * PY x yz.1 * PZ x yz.2) ≤
      mutual_f_information f (fun x y => pX x * PY x y) +
        mutual_f_information f (fun x z => pX x * PZ x z)
See it in the graphDiscuss this resultChallenge it