AFTD Auto-Formalizing Theoretical Domains

jensen_shannon_binary_cid_not_subadditive

theoremverified

There exists a binary Markov chain with conditionally identically distributed observations Y, Z given X where the unregularized Jensen-Shannon mutual information strictly violates subadditivity.

Statement

theorem jensen_shannon_binary_cid_not_subadditive :
    ∃ (pX : Fin 2 → ℝ) (P : Fin 2 → Fin 2 → ℝ),
      (∀ x, 0 ≤ pX x) ∧ (∑ x, pX x = 1) ∧
      (∀ x y, 0 ≤ P x y) ∧ (∀ x, ∑ y, P x y = 1) ∧
      2 * mutual_f_information jensen_shannon_generator (fun x y => pX x * P x y) <
        mutual_f_information jensen_shannon_generator
          (fun x (yz : Fin 2 × Fin 2) => pX x * P x yz.1 * P x yz.2)
Source
arXiv:2610.21231
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • jensen_shannon_generatorThe f-divergence generator for Jensen-Shannon divergence is f(x) = (1/2) x log x - ((x + 1)/2) log((x + 1)/2).
  • 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}…

Read back from the Lean

There exist a probability mass function $pX : \text{Fin } 2 \to \mathbb{R}$ and a transition kernel $P : \text{Fin } 2 \to \text{Fin } 2 \to \mathbb{R}$—meaning that: 1. $0 \le pX(x)$ for all $x \in \text{Fin } 2$, 2. $\sum_{x \in \text{Fin } 2} pX(x) = 1$, 3. $0 \le P(x, y)$ for all $x, y \in \text{Fin } 2$, and 4. $\sum_{y \in \text{Fin } 2} P(x, y) = 1$ for all $x \in \text{Fin } 2$— such that twice the Jensen-Shannon mutual $f$-information of the joint distribution $(x, y) \mapsto pX(x) P(x, y)$ on $\text{Fin } 2 \times \text{Fin } 2$ is strictly less than the Jensen-Shannon mutual $f$-information of the joint distribution $(x, (y_1, y_2)) \mapsto pX(x) P(x, y_1) P(x, y_2)$ on $\text{Fin } 2 \times (\text{Fin } 2 \times \text{Fin } 2)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem is proved by constructing an explicit counterexample: a binary source X with distribution pX = (0.99, 0.01) and a transition channel P with conditional probabilities P(· | 0) = (0.99, 0.01) and P(· | 1) = (0.7, 0.3). After verifying that pX and P define valid probability distributions, the mutual information expressions are expanded into explicit sums and simplified to an inequality between linear combinations of logarithms. This strict transcendental inequality is then verified numerically by the `num_ineq` decision procedure.

  1. There exist candidate distributions pX on {0, 1} and channel transition matrix P on {0, 1} × {0, 1}.

    We instantiate the existential quantifier with explicit witnesses: the prior distribution pX(0) = 99/100, pX(1) = 1/100, and the transition probabilities P(0 | 0) = 99/100, P(1 | 0) = 1/100, P(0 | 1) = 7/10, P(1 | 1) = 3/10. This leaves five obligations: non-negativity and normalization of pX, non-negativity and row normalization of P, and the strict inequality 2 * I_JS(X; Y) < I_JS(X; Y, Z).

    lines 9–11

      refine ⟨fun x => if x = 0 then (99:ℝ)/100 else 1/100,
              fun x y => if x = 0 then (if y = 0 then (99:ℝ)/100 else 1/100) else (if y = 0 then 7/10 else 3/10),
              ?_, ?_, ?_, ?_, ?_⟩
  2. The prior probabilities are non-negative: pX(x) ≥ 0 for all x ∈ {0, 1}.

    We perform a case exhaustion on x ∈ Fin 2 (covering x = 0 and x = 1) using `fin_cases` and check that 99/100 ≥ 0 and 1/100 ≥ 0 by numerical normalization (`norm_num`).

    line 12

      · intro x; fin_cases x <;> norm_num
  3. The prior probabilities sum to 1: ∑ x, pX(x) = 1.

    We expand the sum over the two elements of Fin 2 into pX(0) + pX(1) using `Fin.sum_univ_two`, reducing the goal to 99/100 + 1/100 = 1, which `norm_num` verifies.

    line 13

    uses Fin.sum_univ_two

      · simp only [Fin.sum_univ_two]; norm_num
  4. The channel transition probabilities are non-negative: P(x, y) ≥ 0 for all x, y ∈ {0, 1}.

    We exhaust all four combinations (x, y) ∈ {0, 1}² using `fin_cases` on both variables and check that each value (99/100, 1/100, 7/10, 3/10) is non-negative via `norm_num`.

    line 14

      · intro x y; fin_cases x <;> fin_cases y <;> norm_num
  5. The transition probabilities from each state sum to 1: ∑ y, P(x, y) = 1 for each x ∈ {0, 1}.

    We split into cases on x ∈ Fin 2, expand each sum over y ∈ Fin 2 into the sum of two terms using `Fin.sum_univ_two`, and verify that 99/100 + 1/100 = 1 and 7/10 + 3/10 = 1 using `norm_num`.

    line 15

    uses Fin.sum_univ_two

      · intro x; fin_cases x <;> simp only [Fin.sum_univ_two] <;> norm_num
  6. The unregularized Jensen-Shannon mutual information strictly violates subadditivity: 2 * I_JS(X; Y) < I_JS(X; Y, Z). automation

    We expand the definitions of mutual f-information (`mutual_f_information`) and the Jensen-Shannon generator (`jensen_shannon_generator`), rewriting the sums over Fin 2 and Fin 2 × Fin 2 into explicit summations via `Fin.sum_univ_two` and `Fintype.sum_prod_type`. The simplifier resolves conditional expressions with `if_true` and `if_false`, and `norm_num` computes all rational arithmetic. This reduces the problem to an explicit numerical inequality between linear combinations of natural logarithms, which is closed by the automated decision procedure `num_ineq`.

    lines 16–19

    uses Fin.sum_univ_two, Fintype.sum_prod_type, if_true, if_false

      · simp only [mutual_f_information, jensen_shannon_generator, Fin.sum_univ_two, Fintype.sum_prod_type]
        simp only [Fin.isValue, if_true, if_false, Fin.reduceEq]
        norm_num
        num_ineq
Fin.sum_univ_two
A summation over the two elements of `Fin 2` evaluates to the sum of the terms at 0 and 1: ∑ i, f i = f 0 + f 1.
Fintype.sum_prod_type
A summation over the product of two finite types equals the iterated summation: ∑ x, f x = ∑ x₁, ∑ x₂, f (x₁, x₂).
if_true
An if-then-else expression whose condition is True simplifies to the then-branch: (if True then t else e) = t.
if_false
An if-then-else expression whose condition is False simplifies to the else-branch: (if False then t else e) = e.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The unregularized Jensen-Shannon mutual information is not subadditive on binary Markov chains with conditionally identically distributed observations. -/theorem jensen_shannon_binary_cid_not_subadditive :    ∃ (pX : Fin 2 → ℝ) (P : Fin 2 → Fin 2 → ℝ),      (∀ x, 0 ≤ pX x) ∧ (∑ x, pX x = 1) ∧      (∀ x y, 0 ≤ P x y) ∧ (∀ x, ∑ y, P x y = 1) ∧      2 * mutual_f_information jensen_shannon_generator (fun x y => pX x * P x y) <        mutual_f_information jensen_shannon_generator          (fun x (yz : Fin 2 × Fin 2) => pX x * P x yz.1 * P x yz.2) := by  refine ⟨fun x => if x = 0 then (99:ℝ)/100 else 1/100,          fun x y => if x = 0 then (if y = 0 then (99:ℝ)/100 else 1/100) else (if y = 0 then 7/10 else 3/10),          ?_, ?_, ?_, ?_, ?_⟩  · intro x; fin_cases x <;> norm_num  · simp only [Fin.sum_univ_two]; norm_num  · intro x y; fin_cases x <;> fin_cases y <;> norm_num  · intro x; fin_cases x <;> simp only [Fin.sum_univ_two] <;> norm_num  · simp only [mutual_f_information, jensen_shannon_generator, Fin.sum_univ_two, Fintype.sum_prod_type]    simp only [Fin.isValue, if_true, if_false, Fin.reduceEq]    norm_num    num_ineq
See it in the graphDiscuss this resultChallenge it